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. , 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.50 largest factors found by ECM. 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 (the integers modulo ) 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 and , and thus division between residue classes modulo , performed using the extended Euclidean algorithm. In particular, division by some includes calculation of the . Assuming we calculate a slope of the form with , then if , the result of the point addition will be , the point "at infinity" corresponding to the intersection of the "vertical" line joining and the curve. However, if , then the point addition will not produce a meaningful point on the curve; but, more importantly, is a non-trivial factor of : 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 works as follows: Pick a random elliptic curve over (the integers modulo ), with equation of the form together with a non-trivial point on it. This can be done by first picking random , and then setting to ensure the point is on the curve. As discussed above, we have defined addition and multiplication of a point on the curve. With enough repeated additions, we should be able to cause a failure to add, thus finding us a factor. As a result, we compute on the elliptic curve (), where is a product of many small numbers. k can be a product of small primes raised to small powers, as in the p-1 algorithm, or the factorial for some not too large . This can be done efficiently, one small factor at a time. Say, to get , first compute , then , then , and so on. is picked to be small enough so that -wise point addition can be performed in reasonable time. Check the result of the addition. If we finish all the calculations above without encountering non-invertible elements (), it means that the elliptic curves' (modulo primes) order is not smooth enough, so we need to try again with a different curve and starting point. If we encounter a we are done: it is a non-trivial factor of .
The time complexity depends on the size of the number's smallest prime factor and can be represented by , where p is the smallest factor of n, or , in L-notation.
Explanation
If p and q are two prime divisors of n, then implies the same equation also and These two smaller elliptic curves with the -addition are now genuine groups. If these groups have Np and Nq elements, respectively, then for any point P on the original curve, by Lagrange's theorem, is minimal such that on the curve modulo p implies that k divides Np; moreover, . The analogous statement holds for the curve modulo q. When the elliptic curve is chosen randomly, then Np and Nq are random numbers close to and respectively (see below). Hence it is unlikely that most of the prime factors of Np and Nq are the same, and it is quite likely that while computing eP, we will encounter some kP that is ∞ but not 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 or but not both. That is, gave a non-trivial factor
ECM is at its core an improvement of the older algorithm. The algorithm finds prime factors p such that is b-powersmooth for small values of b. For any e, a multiple of and any a relatively prime to p, by Fermat's little theorem we have . Then is likely to produce a factor of n. However, the algorithm fails when 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 Zp, rather than considering the multiplicative group of Zp which always has order
The order of the group of an elliptic curve over Zp varies (quite randomly) between and 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 curves before getting a smooth group order. This heuristic estimate is very reliable in practice.
Example usage
The following example is from , with some details added.
We want to factor . Let's choose the elliptic curve , with the point on it, and let's try to compute the point .
The slope of the tangent line at some point on the curve is . Using , we can compute point . If the value of does not exist, as a result of not having a modular inverse, then is a non-trivial factor of .
First, we compute . Using point doubling, we have , so the coordinates of point are
yielding the point .
Next, we compute . We have . Since , the modular inverse of 106 exists. Using the extended Euclidean algorithm, we can obtain that .
Given this, we can compute the coordinates of , just as we did above. The coordinates of point are
This yields .
After this, we can compute using point addition. The line joining and has slope , so the coordinates of are
yielding the point
We can similarly compute points , , and so on, but computing requires inverting , which is not possible because . Thus 599 is a divisor of 455839. After a quick division, we have .
The reason this works is that the curve has points, while it has points. Moreover, 640 and 777 are the smallest positive integers k such that on the curve and respectively. Since is a multiple of 640 but not a multiple of 777, we have on the curve but not on the curve hence the repeated addition broke down here, yielding the factorization.
The algorithm, with projective coordinates
Before considering the projective plane over first consider a 'normal' projective space over : Instead of points, lines through the origin are studied. A line may be represented as a non-zero point , under an equivalence relation ~ given by: ⇔ ∃ c ≠ 0 such that x' = cx, y' = cy and z' = cz. Under this equivalence relation, the space is called the projective plane ; points, denoted by , correspond to lines in a three-dimensional space that pass through the origin. Note that the point does not exist in this space since to draw a line in any possible direction requires at least one of x',y' or z' ≠ 0. Now observe that almost all lines go through any given reference plane - such as the (X,Y,1)-plane, whilst the lines precisely parallel to this plane, having coordinates (X,Y,0), specify directions uniquely, as 'points at infinity' that are used in the affine (X,Y)-plane it lies above.
The coordinate corresponds to in affine space. HAL
In the algorithm, only the group structure of an elliptic curve over the field is used. Since we do not necessarily need the field , a finite field will also provide a group structure on an elliptic curve. However, considering the same curve and operation over with not a prime does not give a group. The Elliptic Curve Method makes use of the failure cases of the addition law.
We now state the algorithm in projective coordinates. The neutral element is then given by the point at infinity . Let be a (positive) integer to be factored and consider the elliptic curve (a set of points with some structure on it) .
Pick with ≠ 0. Calculate . The elliptic curve is then in Weierstrass form given by and by using projective coordinates the elliptic curve is given by the homogeneous equation . It has the point . Choose an upperbound for this elliptic curve. Remark: You will only find factors if the group order of the elliptic curve over (denoted by ) is B-smooth, which means that all prime factors of have to be less or equal to . Calculate . Calculate (multiplication is repeated addition) in the ring . If the calculation successfully returns , it means is not -smooth or is prime. Go back to step 2 to pick another curve. If the calculation fails at some point, it means a non-trivial divisor can be found. It can fail because addition and multiplication are not well-defined if is not prime, but this only occurs when a inversion of a particular residue is tried. In this case the factor is found as as above.
In point 5 it is said that under the right circumstances a non-trivial divisor can be found. As pointed out in Lenstra's article (Factoring Integers with Elliptic Curves) the addition needs the assumption . If are not and distinct (otherwise addition works similarly, but is a little different), then addition works as follows:
To calculate: , , , , .
If addition fails, this will be due to a failure calculating In particular, because can not always be calculated if is not prime (and therefore is not a field). Without making use of being a field, one could calculate:
, , , , and simplify if possible.
This calculation is always legal and if the gcd of the -coordinate with ≠ (1 or ), so when simplifying fails, a non-trivial divisor of is found.
Two-stage variant
Analogous to the two-stage variant of Pollard's p − 1 algorithm, Lenstra ECM can too be done in two stages. This allows one to save a time factor of O(log p).
Algorithm Two-Stage ECM. Input: number to be factored n, integer bounds . Output: a factor of n or failure.
Preparation. Choose a random elliptic curve mod n. Pick a point on the curve. (A convenient choice is Suyama's parametrization, which only requires one random number to be drawn.)
Stages. Compute a point on the . The product means that one loops over every prime ; it plays the same role as the large seen in the algorithms above. Using the product of all prime powers less than instead of reduces the asymptotic complexity by . For each prime , , Compute a point on . Compute . If , output and exit. If all primes in range are tried without producing a factor, report failure.