Lenstra elliptic curve factorization
From Academic Kids

The Lenstra elliptic curve factorization is a fast probabilistic algorithm for integer factorization which employs elliptic curves.
This method was the best algorithm for integer factorization until the general number field sieve was developed. It is still best for factoring out divisors of size not greatly exceeding 20 to 25 digits (64 to 83 bits or so), as its running time depends on the size of a factor p rather than on the size of the number n to be factored. The largest factor found (the cofactor being larger) by ECM as of several years ago was around 50 digits. Increasing the number of curves tested improves the chances, but they aren't linear with the increase in the number of digits.
It is an improvement of the older Pollard p −1 factorization method. In that method, it was assumed that the given number n has a prime factor p such that p1 had only "small" prime factors (numbers whose prime factors are all "small" are informally called smooth). Then, by Fermat's little theorem, a^{e}=1 mod p whenever p1 divides e and p does not divide a. Taking e to be a product of small primes raised to small powers, and a to be a random residue mod n, we can hopefully factor n by computing the greatest common divisor of n and a^{e}1, as other divisors q of n are unlikely to have the property that q1 divides e  smooth values are rare. However, we will not be able to factor n if n does not have a prime factor p with p1 smooth.
The Lenstra elliptic curve factorization 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 p1. The order of the group of a random elliptic curve over Z_{p} varies between p+12*sqrt(p) and p+1+2*sqrt(p) (a theorem by Helmut Hasse) randomly, and is likely to be smooth for some Elliptic curves.
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 tantamounts to factoring n
 Compute eA in this group, where e is product of small primes raised to small powers, as in the Pollard p−1 factorization. It 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 Pollard 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 try with some other curve and starting point.
See also
 UBASIC for practical program (ECMX).