发表于 2023-8-16 13:19:28
本帖最后由 nyy 于 2023-8-16 13:21 编辑 |
THE ELLIPTIC CURVE METHOD
The Elliptic Curve Method (ECM for short) was invented in 1985 by H. W. Lenstra,
Jr. . It is suited to find small — say 9 to 30 digits — prime factors of large numbers.
Among the different factorization algorithms whose complexity mainly depends on the size
of the factor searched for (trial division, Pollard rho, Pollard p − 1, Williams p + 1), it is
asymptotically the best method known. ECM can be viewed as a generalization of Pollard’s
p − 1 method, just like ECPP generalizes the n − 1 primality test. ECM relies on Hasse’s
theorem: if p is prime, then an elliptic curve over Z/pZ has group order p + 1 − t with
|t| ≤ 2
√p, where t depends on the curve. If p + 1 − t is a smooth number, then ECM will
— most probably — succeed and reveal the unknown factor p.
Since 1985, many improvements have been proposed to ECM. Lenstra’s original algorithm
had no second phase. Brent proposes in  a “birthday paradox” second phase, and further
more technical refinements. In , Montgomery presents different variants of phase two of
ECM and Pollard p − 1, and introduces a parameterization with homogeneous coordinates,
which avoids inversions modulo n, with only 6 and 5 modular multiplications per addition
and duplication on E, respectively. It is also possible to choose elliptic curves with a group
order divisible by 12 or 16 [7, 8, 1].
Phase one of ECM works as follow