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 curves. For general-purpose factoring, ECM is the third-fastest known factoring method. The second-fastest is the multiple polynomial quadratic sieve, and the fastest is the general number field sieve. The Lenstra elliptic-curve factorization is named after Hendrik Lenstra. It is an algebraic-group factorisation algorithm. Practically speaking, ECM is considered a special-purpose factoring algorithm, as it is most suitable for finding small factors. Currently, it is still the best algorithm for divisors not exceeding 50 to 60 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. 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.
Algorithm
Background Lenstra elliptic-curve factorization method uses a elliptic curve mod n (i.e. the number to be factored) and multiplies a random point P on it. The multiplication is based on elliptic curve point multiplication, which in turn is just the repeated addition of elliptic curve points, described in the article on elliptic curves. This addition would form a group in the non-modular case and in the case when n is prime, because Z / n Z {\displaystyle \mathbb {Z} /n\mathbb {Z} } (the integers modulo n {\displaystyle n} ) forms a group when n is prime. When modular numbers are used instead of the whole range of integers, the addition of two points on the same elliptic curve would involve taking the modular slope of a chord joining P {\displaystyle P} and Q {\displaystyle Q} , and thus division between residue classes modulo n {\displaystyle n} , performed using the extended Euclidean algorithm. In particular, division by some v mod n {\displaystyle v{\bmod {n}}} includes calculation of the gcd ( v , n ) {\displaystyle \gcd(v,n)} . Assuming we calculate a slope of the form u / v {\displaystyle u/v} with gcd ( u , v ) = 1 {\displaystyle \gcd(u,v)=1} , then if v = 0 mod n {\displaystyle v=0{\bmod {n}}} , the result of the point addition will be ∞ {\displaystyle \infty } , the point "at infinity" corresponding to the intersection of the "vertical" line joining P ( x , y ) , P ′ ( x , − y ) {\displaystyle P(x,y),P'(x,-y)} and the curve. However, if gcd ( v , n ) ≠ 1 , n {\displaystyle \gcd(v,n)\neq 1,n} , then the point addition will not produce a meaningful point on the curve; but, more importantly, gcd ( v , n ) {\displaystyle \gcd(v,n)} is a non-trivial factor of n {\displaystyle n} : meaning that we have successfully factored the number. The usual multiplication methods such as multiplication by doubling still apply. Naive successive addition is not required.
Process The Lenstra elliptic-curve factorization method to find a factor of a given natural number n {\displaystyle n} works as follows:
… excerpt ends here. Continue reading the full article.
