CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutSign UpSign In

Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place.

| Download

18.783 Lecture 10: Simple implementation of the elliptic curve factorization method (ECM) using Montgomery curves

Views: 160
License: MIT
Image: ubuntu2004
Kernel: SageMath 9.2

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: %s" % (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: %s" % (cputime()-t))
Montgomery time: 0.13179600000000002 Weierstrass time: 0.3893659999999999

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 = %d" % B) print("Expected number of iterations is about %s " % 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: %s" % (cputime()-t)) print(p)
B = 6340 Expected number of iterations is about 51 1 2^2 * 3^2 * 53 * 83 * 107 * 31021313 2 2^5 * 3^2 * 5^2 * 7 * 10429652971 3 2^3 * 3^3 * 5 * 7 * 751 * 92584589 4 2^2 * 3 * 23 * 31 * 53 * 1159187767 5 2^3 * 3 * 5 * 191 * 22934315101 6 2^2 * 3^3 * 5 * 973434365177 7 2^3 * 3 * 7 * 179 * 8039 * 2174383 8 2^2 * 3^2 * 11 * 13 * 285611 * 357509 9 2^5 * 3^3 * 17 * 41 * 1439 * 606587 10 2^4 * 3^4 * 5 * 248299 * 326701 11 2^5 * 3 * 73 * 457 * 1657 * 99053 12 2^2 * 3 * 13 * 19 * 3539 * 50111993 13 2^3 * 3 * 5^2 * 71 * 1151 * 10720511 14 2^3 * 3 * 383 * 57186086557 15 2^3 * 3^3 * 19 * 23 * 5568846251 16 2^3 * 3^2 * 5 * 53 * 27550026401 17 2^3 * 3^2 * 7300757733821 18 2^3 * 3^5 * 5 * 31 * 1427 * 1222499 19 2^2 * 3^4 * 5 * 7^2 * 13 * 18899 * 26953 20 2^2 * 3^6 * 19 * 4217 * 2249861 21 2^2 * 3^3 * 4867171688773 22 2^2 * 3^2 * 7 * 127 * 239 * 68722387 23 2^9 * 3 * 5 * 7 * 31 * 673 * 468667 24 2^9 * 3^2 * 3187 * 35793643 25 2^6 * 3 * 13 * 18013 * 11691487 26 2^3 * 3^2 * 123637 * 59049937 27 2^4 * 3 * 11 * 995557826719 28 2^3 * 3 * 21902273581427 29 2^7 * 3^4 * 67 * 756711997 30 2^3 * 3^2 * 7 * 13 * 59 * 757 * 839 * 2141 525654532248367 ECM time: 9.709927 525654532248367