Lenstra Elliptic Curve Factorization - Why Does The Algorithm Work?

Why Does The Algorithm Work?

If p and q are two prime divisors of n, then y2 = x3 + ax + b (mod n) implies the same equation also modulo p and modulo q. These two smaller elliptic curves with the -addition are now genuine groups. If these groups have N_p and N_q elements, respectively, then for any point P on the original curve, by Lagrange's theorem, k>0 is minimal such that on the curve modulo p implies that k divides N_p; moreover, . The analogous statement holds for the curve modulo q. When the elliptic curve is chosen randomly, then N_p and N_q are random numbers close to p+1 and q+1, respectively (see below). Hence it is unlikely that most of the prime factors of N_p and N_q are the same, and it is quite likely that while computing eP, we will encounter some kP that is modulo p but not modulo q, or vice versa. When this is the case, kP does not exist on the original curve, and in the computations we found some v with either gcd(v,p)=p or gcd(v,q)=q, but not both. That is, gcd(v,n) gave a non-trivial factor of n.

ECM is at its core an improvement of the older p − 1 algorithm. The p − 1 algorithm finds prime factors p such that p − 1 is b-powersmooth for small values of b. For any e, a multiple of p − 1, and any a relatively prime to p, by Fermat's little theorem we have ae ≡ 1 (mod p). Then gcd(ae − 1, n) is likely to produce a factor of n. However, the algorithm fails when p-1 has large prime factors, as is the case for numbers containing strong primes, for example.

ECM gets around this obstacle by considering the group of a random elliptic curve over the finite field Z_p, rather than considering the multiplicative group of Z_p which always has order p − 1.

The order of the group of an elliptic curve over Z_p varies (quite randomly) between p + 1 − 2√p and p + 1 + 2√p by Hasse's theorem, and is likely to be smooth for some elliptic curves. Although there is no proof that a smooth group order will be found in the Hasse-interval, by using heuristic probabilistic methods, the Canfield-Erdős-Pomerance theorem with suitably optimized parameter choices, and the L-notation, we can expect to try L curves before getting a smooth group order. This heuristic estimate is very reliable in practice.