Lenstra elliptic-curve factorization

The Lenstra elliptic-curve factorization or the elliptic-curve factorization method (ECM) is a fast, sub-<a href="/facts/Exponential_running_time/GbTmY8t5">exponential running time</a>, algorithm for <a href="/facts/Integer_factorization/EjMCTz2t">integer factorization</a>, which employs <a href="/facts/Elliptic_curve/60jvaHSA">elliptic curves</a>. For <a href="/facts/General-purpose_computer/SQe1aK05">general-purpose</a> factoring, ECM is the third-fastest known factoring method. The second-fastest is the <a href="/facts/Quadratic_sieve/xDrfU9xl">multiple polynomial quadratic sieve</a>, and the fastest is the <a href="/facts/General_number_field_sieve/elC06ARC">general number field sieve</a>. The Lenstra elliptic-curve factorization is named after <a href="/facts/Hendrik_Lenstra/8XQ4Izlf">Hendrik Lenstra</a>.
Practically speaking, ECM is considered a special-purpose factoring algorithm, as it is most suitable for finding small factors. Currently<a href="https://en.wikipedia.org/w/index.php?title=Lenstra_elliptic-curve_factorization&action=edit">[update]</a>, it is still the best algorithm for <a href="/facts/Divisor/DKNa2GvC">divisors</a> not exceeding 50 to 60 <a href="/facts/Decimal/7omfVNIM">digits</a>, 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. Increasing the number of curves tested improves the chances of finding a factor, but they are not <a href="/facts/Linear/fChtg3KC">linear</a> with the increase in the number of digits.

Lenstra elliptic-curve factorization open-in-new

Lenstra elliptic-curve factorization