Contact
CoCalc Logo Icon
StoreFeaturesDocsShareSupport News AboutSign UpSign In
| Download
Views: 111

Montgomery curve group operations

def madd(P,Q,R): """Montgomery addition: returns (x_{m+n},z_{m+n}) given P=(x_m,z_m), Q=(x_n,z_n), and R=(x_{m-n},z_{m-n})""" a = P[0]-P[1]; b=P[0]+P[1]; c=Q[0]-Q[1]; d=Q[0]+Q[1] e=a*d; f=b*c; return (R[1]*(e+f)^2,R[0]*(e-f)^2) def mdbl(P,C): """Montgomery doubling: returns (x_{2n},z_{2n}) given P=(x_n,z_n) and C=(A+2)/4 where By^2=x^3+Ax^2+x is the Montgomery curve equation""" a=P[0]+P[1]; b=P[0]-P[1] c=a^2; d=b^2; e=c-d return (c*d,e*(d+C*e)) def mmul(P,n,C): """Montgomery multiplication: returns (x_n,z_n) given P=(x_1,z_1) and C=(A+2)/4 where By^2=x^3+Ax^2+x is the Montgomery curve equation""" Q = [P,mdbl(P,C)] b=n.digits(2) for i in range(len(b)-2,-1,-1): Q[1-b[i]] = madd(Q[1],Q[0],P) Q[b[i]] = mdbl(Q[b[i]],C) return Q[0]
F=GF(random_prime(2^256,2^255)) A=F.random_element(); B=F.random_element() C=(A+2)/4 while true: x = F.random_element() if ((x^3+A*x^2+x)/B).is_square(): break; P=(x,1); t=cputime() for p in primes(0,10000): P=mmul(P,p,C) print "Montgomery time:", cputime()-t a4=1/B^2-A^2/(3*B^2); a6=-A^3/(27*B^3)-a4*A/(3*B) E=EllipticCurve([a4,a6]) P=E.random_element() t=cputime() for p in primes(0,10000): P=p*P print "Weierstrass time:", cputime()-t
Montgomery time: 0.188 Weierstrass time: 0.772

Single stage ECM using Montgomery curves

def L(a,c,N): z = ceil(exp(c*log(N)^a*log(log(N))^(1-a))) return ceil(z) def ECM_1curve(N,p,M,B1): R=Integers(N) # generate Montgomery curve using parameterization that guarantees a point of order 3 c=R(randint(1,10^10)) a=6*c/(c^2+6) b=R(randint(1,10^10)) A=(-3*a^4-6*a^2+1)/(4*a^3) B=(a^2-1)^2/(4*a*b^2) C=(A+2)/4 P=(3*a/4,1) a4=1/B^2-A^2/(3*B^2); a6=-A^3/(27*B^3)-a4*A/(3*B) F=GF(p) E=EllipticCurve([F(a4.lift()),F(a6.lift())]) print factor(E.cardinality()) m=ceil(M+2*sqrt(M)+1) for p in primes(B1): q = p; r=p*q while r <= m: q=r; r=p*q P=mmul(P,q,C) d=gcd(N,P[1].lift()) if d == N: print "N fail"; return 0 if d > 1: return d return 0
k=50; n=200 q=random_prime(2^(n-k),2^(n-k-1)) p=random_prime(2^k,2^(k-1)) B=2.5*L(1/2,1/sqrt(2),2^k) # includes an empirical fudge factor print "B =",B print "Expected number of iterations is about", L(1/2,1/(2*sqrt(2)),2^k) t=cputime() i=1 while true: print i, d = ECM_1curve(p*q,p,2^50,B) if d: break i += 1 print d print "ECM time:", cputime()-t print p
B = 6340.00000000000 Expected number of iterations is about 51 1 2^3 * 3^3 * 1493382895639 2 2^2 * 3^2 * 7 * 233 * 5493744023 3 2^2 * 3^2 * 5 * 7 * 13 * 31 * 635256749 4 2^2 * 3^2 * 5 * 19 * 787 * 2503 * 47881 5 2^7 * 3 * 1163 * 722293961 6 2^4 * 3^3 * 768107 * 972119 7 2^3 * 3^8 * 5227 * 1175743 8 2^3 * 3^2 * 457 * 9803388229 9 2^4 * 3 * 7 * 64901 * 14792251 10 2^3 * 3^3 * 7 * 17 * 389 * 4127 * 7817 11 2^8 * 3 * 7 * 23 * 7517 * 347051 12 2^2 * 3^2 * 61 * 9629 * 15254971 13 2^3 * 3^3 * 11 * 157 * 10487 * 82457 14 2^3 * 3^2 * 31 * 257017 * 562301 15 2^3 * 3 * 67 * 263 * 27211 * 28031 16 2^5 * 3^2 * 1120037116987 17 2^3 * 3^2 * 5 * 19 * 877 * 53773619 18 2^3 * 3^2 * 5 * 15359 * 58339069 19 2^2 * 3 * 26880890592539 20 2^2 * 3^2 * 5 * 11^2 * 467 * 4409 * 7193 21 2^4 * 3^2 * 47 * 47661159419 22 2^3 * 3^3 * 2357 * 633594757 23 2^5 * 3 * 5 * 2749 * 4297 * 56891 24 2^3 * 3^2 * 5^2 * 5347 * 33515231 25 2^4 * 3^2 * 2240074521221 26 2^4 * 3^3 * 107 * 353 * 19768907 27 2^3 * 3^3 * 29 * 137 * 607 * 619247 28 2^3 * 3 * 199 * 257 * 262801303 29 2^4 * 3 * 5^2 * 7 * 11 * 3491024657 30 2^2 * 3^2 * 13^3 * 17 * 313 * 766477 31 2^3 * 3^2 * 11 * 457 * 891217081 32 2^6 * 3^2 * 7 * 1289 * 1747 * 35527 33 2^3 * 3 * 23 * 584367152573 34 2^3 * 3 * 5^4 * 59 * 364486673 35 2^2 * 3^3 * 11 * 271524189611 36 2^4 * 3^4 * 17 * 14641009771 37 2^2 * 3 * 167 * 331 * 486294311 38 2^4 * 3 * 19 * 509 * 11587 * 59971 39 2^3 * 3^2 * 5 * 103 * 8699317603 40 2^2 * 3 * 367 * 73244934691 41 2^4 * 3 * 7^2 * 2131 * 4051 * 15887 42 2^4 * 3 * 17 * 395307241279 43 2^3 * 3 * 7 * 97 * 19794472909 44 2^3 * 3 * 5 * 17 * 89 * 2381 * 746183 45 2^4 * 3^2 * 29 * 77243939471 46 2^6 * 3 * 13 * 17 * 12071 * 629779 47 2^3 * 3 * 13440446543933 48 2^2 * 3 * 5 * 7 * 83 * 9253319107 49 2^3 * 3 * 11 * 1221858739963 50 2^4 * 3^4 * 167 * 1490402041 51 2^7 * 3^3 * 93336421571 52 2^3 * 3^2 * 2141 * 2092549643 53 2^3 * 3^2 * 5 * 19 * 5413 * 8712259 54 2^3 * 3^2 * 4480148382251 55 2^5 * 3 * 5^2 * 13 * 10338805019 56 2^5 * 3^10 * 53^2 * 60773 57 2^4 * 3 * 269 * 2843 * 8787281 58 2^2 * 3 * 7 * 11 * 61 * 5722991717 59 2^2 * 3 * 17 * 1581228851131 60 2^3 * 3^2 * 7^2 * 240371 * 380377 61 2^4 * 3 * 19 * 43 * 8225487187 62 2^3 * 3^4 * 17 * 367 * 3931 * 20297 63 2^2 * 3^3 * 11 * 18049 * 15043723 64 2^2 * 3^2 * 11^2 * 13 * 29 * 196424537 65 2^2 * 3^5 * 5 * 66372574237 66 2^2 * 3 * 5 * 218401 * 24616087 67 2^3 * 3^2 * 5^2 * 71 * 2524027361 68 2^6 * 3^3 * 191 * 197 * 4961141 69 2^2 * 3 * 26880892779331 70 2^2 * 3 * 5 * 11 * 547 * 709 * 1260223 71 2^6 * 3 * 231877 * 7245461 72 2^4 * 3 * 179 * 13613 * 2757889 73 2^3 * 3^2 * 1328387 * 3372623 74 2^3 * 3^2 * 13 * 31 * 103 * 271 * 398273 75 2^3 * 3^3 * 19 * 617 * 127389133 76 2^7 * 3 * 3583 * 5231 * 44819 77 2^2 * 3^4 * 17 * 58564033903 78 2^5 * 3^3 * 13 * 181 * 158667973 79 2^3 * 3 * 47 * 179 * 4591 * 347981 80 2^2 * 3^4 * 773 * 2797 * 460477 81 2^2 * 3^7 * 34543 * 1067471 82 2^2 * 3^3 * 5 * 38791 * 15399271 83 2^3 * 3 * 5 * 7 * 17 * 2011 * 11232713 84 2^4 * 3 * 5 * 339247 * 3961847 85 2^3 * 3^2 * 7 * 19 * 137 * 245878309 86 2^4 * 3^2 * 75431 * 29696999 87 2^6 * 3 * 67 * 25075459351 88 2^3 * 3^6 * 43 * 1286290307 89 2^2 * 3^3 * 13 * 229751219549 90 2^3 * 3^3 * 1493382929461 91 2^3 * 3 * 23 * 3257 * 179418851 92 2^3 * 3^2 * 11 * 17 * 293 * 827 * 98873 93 2^6 * 3 * 7 * 179 * 613 * 2187319 94 2^3 * 3 * 11 * 19 * 64308348343 95 2^2 * 3 * 11 * 2443717685677 96 2^8 * 3^3 * 185429 * 251677 97 2^9 * 3^2 * 5^2 * 59 * 2053 * 23117 98 2^4 * 3^3 * 17 * 43923025841 99 2^4 * 3 * 107 * 3391 * 18521329 100 2^3 * 3 * 3301 * 4071628529 101 2^4 * 3^2 * 17 * 131769089057 102 2^2 * 3 * 313 * 85881436651 103 2^4 * 3^3 * 5 * 23 * 409 * 997 * 15923 104 2^4 * 3^3 * 5 * 17 * 8784604523 105 2^6 * 3 * 59 * 1373 * 3541 * 5857 322570703372719 ECM time: 57.652 322570703372719