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. Technically, the ECM is classified as a deterministic algorithm as all "random" steps (such as the choice of curves) used can be derandomized (using pseudo-random sources) and done in a deterministic way. (This is not to say that the algorithm can't be implemented in a probabilistic way, if one so chooses, provided one has a true source of randomness.) In computational complexity theory, the complexity class EXPTIME (sometimes called EXP) is the set of all decision problems solvable by a deterministic Turing machine in O(2p(n)) time, where p(n) is a polynomial function of n. ... In number theory, the integer factorization problem is the problem of finding a non-trivial divisor of a composite number; for example, given a number like 91, the challenge is to find a number such as 7 which divides it. ... In mathematics, an elliptic curve is a plane curve defined by an equation of the form y2 = x3 + a x + b, which is non-singular; that is, its graph has no cusps or self-intersections. ... In computer science, a deterministic algorithm is an algorithm which, in informal terms, behaves predictably. ... Random redirects here. ...

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; both are probabilistic algorithms, in the sense there is no guarantee that they will return a non trivial factor in the expected running time; there is an exponentially small probability they will take an exponential amount of time. In telecommunication, a general purpose computer is a computer designed to perform, or that is capable of performing, in a reasonably efficient manner, the functions required by both scientific and business applications. ... The quadratic sieve algorithm (QS) is a modern integer factorization algorithm and, in practice, the second fastest method known (after the general number field sieve). ... In mathematics, the general number field sieve (GNFS) is the most efficient algorithm known for factoring integers larger than 100 digits. ... A randomized algorithm or probabilistic algorithm is an algorithm which employs a degree of randomness as part of its logic. ...

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 greatly exceeding 20 to 25 digits (64 to 83 bits or so), 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. The largest factor found using ECM so far was discovered on August 24, 2006 by B. Dodson and has 67 digits [1]. 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. 2006 is a common year starting on Sunday of the Gregorian calendar. ... In mathematics, a divisor of an integer n, also called a factor of n, is an integer which evenly divides n without leaving a remainder. ... The decimal (base ten or occasionally denary) numeral system has ten as its base. ... This article is about the unit of information, see Bit (disambiguation) for other meanings. ... The word linear comes from the Latin word linearis, which means created by lines. ...

Lenstra's elliptic curve factorization

The Lenstra elliptic curve factorization method to find a factor of the given number n works as follows:

• Pick a random elliptic curve over Z with a point A on it. Then, we consider the group law on this curve mod n — this is possible since almost all residues mod n have inverses, which can be found using the Euclidean algorithm, and finding a noninvertible residue is tantamount to factoring n.

• Compute eA in this group, where e is product of small primes raised to small powers, as in the p-1 algorithm. This can be done one prime at a time, thus efficiently.

• Hopefully, eA is a zero element of the elliptic curve group in Z_p, but not in Z_q for another prime divisor q of n (as in the p-1 method, it is unlikely that both groups will have an order which is a divisor of e). Then we can find a factor of n by finding the greatest common divisor of the first coordinate of A and n, since this coordinate will be zero in Z_p.

• If it does not work, we can try again with some other curve and starting point.

The complexity depends on the size of the factor and can be represented by O(e^{(1 + o(1)) √(ln p ln ln p)}), where p is the smallest factor of n. In mathematics, an elliptic curve is a plane curve defined by an equation of the form y2 = x3 + a x + b, which is non-singular; that is, its graph has no cusps or self-intersections. ... Point can refer to: Look up Point in Wiktionary, the free dictionary // Mathematics In mathematics: Point (geometry), an entity that has a location in space but no extent Fixed point (mathematics), a point that is mapped to itself by a mathematical function Point at infinity Point group Point charge, an... In mathematics, a group is a set, together with a binary operation, such as multiplication or addition, satisfying certain axioms, detailed below. ... The reciprocal function: y = 1/x. ... In number theory, the Euclidean algorithm (also called Euclids algorithm) is an algorithm to determine the greatest common divisor (GCD) of two elements of any Euclidean domain (for example, the integers). ... Pollards p − 1 algorithm is a number theoretic integer factorization algorithm, invented by John Pollard in 1974. ... In mathematics, the greatest common divisor (gcd), sometimes known as the greatest common factor (gcf) or highest common factor (hcf), of two non-zero integers, is the largest positive integer that divides both numbers without remainder. ... Big O notation is often used to describe how the size of the input data affects an algorithms running time. ... e is the unique number such that the value of the derivative (slope of a tangent line) of f (x) = ex (blue curve) at the point x = 0 is exactly 1. ... The natural logarithm, formerly known as the hyperbolic logarithm, is the logarithm to the base e, where e is equal to 2. ...

Derivation

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 a^e ≡ 1 (mod p). Then gcd(a^e-1, n) is likely to produce a factor of n. However, the algorithm fails when p-1 has large prime factors, as is the case for numbers containing strong primes, for example. Pollards p − 1 algorithm is a number theoretic integer factorization algorithm, invented by John Pollard in 1974. ... In number theory, a positive integer m is called B-smooth if all prime factors of m are such that . For example, 22335654 is 5-smooth since none of its prime factors are greater than 5. ... In mathematics, the integers a and b are said to be coprime or relatively prime if and only if they have no common factor other than 1 and −1, or equivalently, if their greatest common divisor is 1. ... Fermats little theorem (not to be confused with Fermats last theorem) states that if p is a prime number, then for any integer a, This means that if you start with a number, initialized to 1, and repeatedly multiply, for a total of p multiplications, that number by... Modular arithmetic (sometimes called modulo arithmetic, or clock arithmetic because of its use in the 24-hour clock system) is a system of arithmetic for integers, where numbers wrap around after they reach a certain value — the modulus. ... In mathematics, the greatest common divisor (gcd), sometimes known as the greatest common factor (gcf) or highest common factor (hcf), of two non-zero integers, is the largest positive integer that divides both numbers without remainder. ... A strong prime is a type of prime number that is sometimes used for certain cryptographic applications such as key generation for RSA keys. ...

ECM gets around this obstacle by considering the group of a random elliptic curve over the finite field Z_p, rather than considering the multiplicative group of Z_p which always has order p-1. This picture illustrates how the hours in a clock form a group. ... In mathematics, an elliptic curve is a plane curve defined by an equation of the form y2 = x3 + a x + b, which is non-singular; that is, its graph has no cusps or self-intersections. ... In abstract algebra, a finite field or Galois field (so named in honor of Évariste Galois) is a field that contains only finitely many elements. ... In mathematics, multiplicative group in group theory may mean any group G written in multiplicative notation (rather than additive notation for an abelian group) for its binary operation or in particular the multiplicative group of a field F, namely F{0} under multiplication, written F* or Fx. ...

The order of the group of an elliptic curve over Z_p varies (randomly) between p + 1 - 2√p and p + 1 + 2√p 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 L[√2 / 2, √2] curves before getting a smooth group order. This heuristic estimate is very reliable in practice. In mathematics, Hasses theorem on elliptic curves bounds the number of points on an elliptic curve over a finite field. ... Look up Heuristic in Wiktionary, the free dictionary. ... The L-notation is widely used to express the computational complexity of an algorithm. ... The L-notation is widely used to express the computational complexity of an algorithm. ...

See also

• UBASIC for practical program (ECMX).
• GMP-ECM, an efficient implementation of ECM.
• ECMNet, an easy client-server implementation that works with several factorization projects.
• pyecm, a python implementation of ECM. Much faster with psyco and/or gmpy.

This article needs to be cleaned up to conform to a higher standard of quality. ...

Other external links

• Factoring applet that uses ECM

References

• Brent, Richard P. "Factorization of the tenth Fermat number." Mathematics of Computation 68 (1999), 429-451.

• Cohen, Henri. A Course in Computational Algebraic Number Theory. Springer-Verlag, New York, Berlin, Heidelberg, 1996. ISBN 0-387-55640-0.

• Lenstra, A. K. and Lenstra Jr., H. W. (editors), The development of the number field sieve. Lecture Notes in Mathematics 1554, Springer-Verlag, Berlin, 1993. MR 96m:11116.

• Lenstra Jr., H. W. "Factoring integers with elliptic curves." Annals of Mathematics (2) 126 (1987), 649-673. MR 89g:11125.

• Pomerance, Carl; Richard Crandall (2001). "Section 7.4: Elliptic curve method", Prime Numbers: A Computational Perspective, 1st edition, Springer, 301–313. ISBN 0-387-94777-9. 

• Pomerance, Carl. "The quadratic sieve factoring algorithm." Advances in Cryptology, Proc. Eurocrypt '84, Lecture Notes in Computer Science, Vol. 209, Springer-Verlag, Berlin, 1985, 169-182. MR 87d:11098.

• Pomerance, Carl. "A Tale of Two Sieves." Notices of the American Mathematical Society 43 (1996), 1473-1485.

• Silverman, Robert D. "The Multiple Polynomial Quadratic Sieve." Mathematics of Computation 48 (1987), 329-339.