Given a composite number n, finding one of its factors is considered to be a hard problem, and is the basis of the cryptographic scheme RSA.

However there are various algorithms which strive to do the best possible, which in this case usually means e^(sqrt(logn loglogn)), or one of its powers (asymptotically). One of the most efficient algorithms known involves elliptic curves (although the best performance bound of this algorithm depends on a conjecture).

The basic idea is an extension of Pollard's method wihich works for certain composite numbers. Suppose one of the factors p of n happens to have the property that p-1 has only small prime factors, then let k be the product of all small primes upto some number s (say). Throw in some powers as well. Now, with a good chance k is a multiple of p-1, and hence for any non-trivial a , a^{k} = 1 (mod p) ( Fermat's thm ).

Hence, computing the gcd(n, a^{k}-1) is likely to give us p. But, this only works if there is a factor p, such that p-1 divided s.

Using Elliptic Curves

The problem with Pollard's method is that there are only finitely many groups (Fp)* on which the algorithm is relying. Lenstra used the fact that over the same Field Fp, there are a whole range of abelian groups defined by the different elliptic curves, and with high probability, one of them will have required property.

----------------------------------------------------------------------------

Factorization into prime elements is also a key tool in studying diophantine equations like in Fermat's Theorem and Elliptic curves .