Lenstra elliptic-curve factorization: Difference between revisions

Revision as of 16:01, 23 September 2022

Revision as of 16:14, 23 September 2022

Line 2:

{{technical|date=December 2020}}

The '''Lenstra elliptic-curve factorization''' or the '''elliptic-curve factorization method''' ('''ECM''') is a fast, sub-[[exponential running time]], algorithm for [[integer factorization]], which employs [[elliptic curve]]s. For [[general-purpose computer|general-purpose]] factoring, ECM is the third-fastest known factoring method. The second-fastest is the [[quadratic sieve|multiple polynomial quadratic sieve]], and the fastest is the [[general number field sieve]]. The Lenstra elliptic-curve factorization is named after [[Hendrik Lenstra]].

Practically speaking, ECM is considered a special-purpose factoring algorithm, as it is most suitable for finding small factors. {{As of|2006|alt=Currently}}, it is still the best algorithm for [[divisor]]s not exceeding 50 to 60 [[decimal|digits]], as its running time is dominated by the size of the smallest factor ''p'' rather than by the size of the number ''n'' to be factored. Frequently, ECM is used to remove small factors from a very large integer with many factors; if the remaining integer is still composite, then it has only large factors and is factored using general-purpose techniques. The largest factor found using ECM so far has 83 decimal digits and was discovered on 7 September 2013 by R. Propper.<ref>[http://www.loria.fr/~zimmerma/records/top50.html 50 largest factors found by ECM].</ref> Increasing the number of curves tested improves the chances of finding a factor, but they are not [[linear]] with the increase in the number of digits.