In the previous two theorems the group was the integers mod p. The p-1 method drives a random element up to 1, the group identity, assuming the order of the multiplicative group is smooth, i.e. a product of small primes. The pollard rho method generates a sequence of values mod p, looking for a duplicate. These are clever techniques, but if p±1 is not smooth, and if p is large, we are out of luck.
By selecting a random elliptic curve, we can work with a new group G that is not Zp. In most cases |G| is close to p, but we might get lucky and stumble on a group whose order is smooth. Let's see how this is going to work.
For purposes of illustration, let n = p×q, where p and q are large primes, and p±1 and q±1 are not particularly smooth. None of the prior algorithms will help.
The first task is to select an elliptic curve and a point on the curve mod n. This implies a curve and a point on the curve mod p and mod q. It also implies two elliptic groups, and if all goes well, our point will have a small / smooth order in one of the two groups.
Start with a point u, defined by two integers x and y mod n, and select any a, and let b = y2-x3-ax. Now u lies in both elliptic curves (mod p and q), defined by the parameters a and b.
To get us started, multiply u by the lcm of the first hundred integers, invoking the gcd algorithm along the way. If this does not separate p from q, and it probably won't, multiply by larger and larger primes, hoping to stumble upon the order of u in one of the two groups.
The trick is knowing when to give up on an elliptic curve, or suspend it, and look elsewhere. One cpu might investigate hundreds of curves simultaneously, using a time share approach, or a collection of distributed processors might follow their own elliptic curves, parseled out by a central server, or chosen at random. There's plenty of room for creative programming here, but that is beyond the scope of this web page.
To measure performance, Assume the elliptic group has an order that is a pseudo-random number near p. (This is born out in practice.) Multiplying u by small primes removes these primes from |u|. This may remove 20 digits from |u|, if we're lucky. Setting these small primes aside, |G| consists of large primes that are not likely to repeat. Thus |G| is a cyclic group, and u is almost always a generator thereof, with the same order. Thus |u| is quite large, almost as large as p itself, and that's not very helpful. We can only hope one of the elliptic groups consists of relatively small primes, or we're out of luck. With this in mind, it's probably better to try many different elliptic curves, rather than pursuing one curve for a long time.
I wrote a factoring program based on elliptic curves, and it can usually crack a 60 digit number without too much fuss.