This algorithm was written in 1974 by John M. Pollard. That is all I know for now.
This method is based on Fermatīs little theorem. It is well known that for any prime number you choose, p, and any other number, a,
a^(p-1) = 1 (mod p)
Which means that,
a^(p-1) - 1 = 0 (mod p)
i.e. p divides the left hand side, or: p is a factor of the left hand side. FACTOR! Thatīs what we want to hear!

So all we have to do is try out the converse. Assume that the number you wish to factor, N, has some unknown prime factor, p. We just try a bunch of a^k - 1 numbers and see if it they have a common factor with N. If so, we found our p. Done!

  1. Choose a number, N, you wish to factor
  2. Choose a number, 1 < a < N, say a = 2
  3. Choose a number, k, say k = 2
  4. If gcd(a, N) is not 1, you have a factor. Otherwise...
  5. Let t = a^k mod N
  6. Let d = GCD( t-1, N )
  7. Use division algorithm to see if d is a factor of N
  8. Change a and/or k and go back to step 4

You may well ask, "Why do we expect to have more success than any other method?" Good question. The key is this: p may be hard to find, but p-1 is a completely different number. It is very likely that p-1 is a product of small prime numbers. If you choose the right k, k and p-1 will have many common factors. That is really the trick to this algorithm: Choosing a good k. More on that later...
Theoretical Runtime:
where q is the largest prime factor of p-1
and p is the largest prime factor of N