The largest factor found using ECM so far has 83 decimal digits and was discovered on 7 September 2013 by R.
works as follows: The time complexity depends on the size of the number's smallest prime factor and can be represented by exp[(√2 + o(1)) √ln p ln ln p], where p is the smallest factor of n, or
If these groups have Np and Nq elements, respectively, then for any point P on the original curve, by Lagrange's theorem, k > 0 is minimal such that
That is, gcd(v, n) gave a non-trivial factor of n. ECM is at its core an improvement of the older p − 1 algorithm.
The p − 1 algorithm finds prime factors p such that p − 1 is b-powersmooth for small values of b.
For any e, a multiple of p − 1, and any a relatively prime to p, by Fermat's little theorem we have ae ≡ 1 (mod p).
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 p − 1.
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 L[√2/2, √2] curves before getting a smooth group order.
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.
Hence gcd(455839, 106) = 1, and working backwards (a version of the extended Euclidean algorithm): 1 = 6 – 5 = 2·6 – 11 = 2·28 – 5·11 = 7·28 – 5·39 = 7·106 – 19·39 = 81707·106 – 19·455839.
The Euclidean algorithm gives that 455839 is divisible by 599, and we have found a factorization 455839 = 599·761.
Under this equivalence relation, the space is called the projective plane
, correspond to lines in a three-dimensional space that pass through the origin.
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
, a finite field will also provide a group structure on an elliptic curve.
The Elliptic Curve Method makes use of the failure cases of the addition law.
Let n be a (positive) integer and consider the elliptic curve (a set of points with some structure on it)
As pointed out in Lenstra's article (Factoring Integers with Elliptic Curves) the addition needs the assumption
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.
, since they force the group orders of the curve modulo primes to be divisible by 12 and 16 respectively.
: Every Edwards curve with a point of order 3 can be written in the ways shown above.
modulo n for each prime l. The use of Twisted Edwards elliptic curves, as well as other techniques were used by Bernstein et al[2] 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 Zimmermann.
There are recent developments in using hyperelliptic curves to factor integers.
with f of degree 5), which gives the same result as using two "normal" elliptic curves at the same time.
Bernstein, Heninger, Lou, and Valenta suggest GEECM, a quantum version of ECM with Edwards curves.
[3] 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.