Lenstra elliptic-curve factorization
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. 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. 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. The Lenstra elliptic-curve factorization method to find a factor of a given natural number formula_1 works as follows: 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 formula_36, in L-notation. Why does the algorithm work? If "p" and "q" are two prime divisors of "n", then implies the same equation also and These two smaller elliptic curves with the formula_37-addition are now genuine  groups. If these groups have "N" and "N" elements, respectively, then for any point "P" on the original curve, by Lagrange's theorem, is minimal such that formula_38 on the curve modulo "p" implies that "k" divides "N"; moreover, formula_39. The analogous statement holds for the curve modulo "q". When the elliptic curve is chosen randomly, then "N" and "N" are random numbers close to and respectively (see below). Hence it is unlikely that most of the prime factors of "N" and "N" 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 Z, rather than considering the multiplicative group of Z which always has order  The order of the group of an elliptic curve over Z 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. An example. 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 slope of the tangent line at some point "A"=("x", "y") is . Using "s" we can compute 2"A". If the value of "s" is of the form "a/b" where "b" > 1  and gcd("a","b") = 1, we have to find the modular inverse of "b". If it does not exist, gcd("n","b") is a non-trivial factor of "n". First we compute 2"P". We have so the coordinates of are and all numbers understood Just to check that this 2"P" is indeed on the curve: Then we compute 3(2"P"). We have Using the Euclidean algorithm: then then then then then Hence and working backwards (a version of the extended Euclidean algorithm): Hence and Given this "s", we can compute the coordinates of 2(2"P"), just as we did above: Just to check that this  is indeed a point on the curve: After this, we can compute formula_40. We can similarly compute 4!"P", and so on, but 8!"P" requires inverting The Euclidean algorithm gives that 455839 is divisible by 599, and we have found a The reason that this worked 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 formula_41 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 formula_42, under an equivalence relation ~ given by: formula_43 ⇔ ∃ c ≠ 0 such that "x' = cx", "y' = cy" and "z' = cz". Under this equivalence relation, the space is called the projective plane formula_44; points, denoted by formula_45, correspond to lines in a three-dimensional space that pass through the origin. Note that  the point formula_46 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. 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 formula_47 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 formula_48. Let be a (positive) integer and consider the elliptic curve (a set of points with some structure on it) formula_49. 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 formula_67. If formula_68 are not formula_48 and distinct (otherwise addition works similarly, but is a little different), then addition works as follows: If addition fails, this will be due to a failure calculating formula_76 In particular, because formula_77 can not always be calculated if is not prime (and therefore formula_63 is not a field). Without making use of formula_63 being a field, one could calculate: 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. Twisted Edwards curves. The use of Edwards curves needs fewer modular multiplications and less time than the use of Montgomery curves or Weierstrass curves (other used methods). Using Edwards curves you can also find more primes. Definition. Let formula_24 be a field in which formula_85, and let formula_86 with formula_87. Then the twisted Edwards curve formula_88 is given by formula_89 An Edwards curve is a twisted Edwards curve in which formula_90. There are five known ways to build a set of points on an Edwards curve: the set  of affine points, the set of projective points, the set of inverted points, the set of extended points and the set of completed points. The set of affine points is given by: The addition law is given by The point (0,1) is its neutral element and the inverse of formula_93 is formula_94. The other representations are defined similar to how the projective Weierstrass curve follows from the affine. Any elliptic curve in Edwards form has a point of order 4. So the torsion group of an Edwards curve over formula_95 is isomorphic to either formula_96 or formula_97. The most interesting  cases for ECM are formula_98 and formula_97, since they force the group orders of the curve modulo primes to be divisible by 12 and 16 respectively. The following curves have a torsion group isomorphic to formula_98: Every Edwards curve with a point of order 3 can be written in the ways shown above. Curves with torsion group isomorphic to formula_97 and formula_110 may be more efficient at finding primes. Stage 2. The above text is about the first stage of elliptic curve factorisation. There one hopes to find a prime divisor such that formula_111 is the neutral element of formula_112 . In the second stage one hopes to have found a prime divisor such that formula_111 has small prime order in formula_114. We hope the order to be between formula_115 and formula_116, where formula_115 is determined in stage 1 and formula_116 is new stage 2 parameter. Checking for a small order of formula_111, can be done by computing formula_120 modulo for each prime . GMP-ECM and EECM-MPFQ. The use of Twisted Edwards elliptic curves, as well as other techniques were used by Bernstein et al to provide an optimized implementation of ECM. Its only drawback is that it works on  smaller composite numbers than the more general purpose implementation, GMP-ECM of Zimmerman. Hyperelliptic-curve method (HECM). There are recent developments in using hyperelliptic curves to factor integers. Cosset shows in his article (of 2010) that one can build a hyperelliptic curve with genus two (so a curve formula_121 with of degree 5), which gives the same result as using two "normal" elliptic curves at the same time. By making use of the Kummer surface, calculation is more efficient. The disadvantages of the hyperelliptic curve (versus an elliptic curve) are compensated by this alternative way of calculating. Therefore, Cosset roughly  claims that using hyperelliptic curves for factorization is no worse than using elliptic curves. Quantum version (GEECM). Bernstein, Heninger, Lou, & Valenta suggest GEECM, a quantum version of ECM with Edwards curves. It uses Grover's algorithm to roughly double the length of the primes found compared to standard EECM, assuming a quantum computer with sufficiently many qubits and of comparable speed to the classical computer running EECM.