BACKGROUND
This algorithm was written in 1974 by John M. Pollard. That is all I know
for now.
BIG IDEA
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!
METHOD
- Choose a number, N, you wish to factor
- Choose a number, 1 < a < N, say a = 2
- Choose a number, k, say k = 2
- If gcd(a, N) is not 1, you have a factor. Otherwise...
- Let t = a^k mod N
- Let d = GCD( t-1, N )
- Use division algorithm to see if d is a factor of N
- YES? - You found a factor, you are done
- NO? - Then...
- Change a and/or k and go back to step 4
TECHNICAL ANALYSIS
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:
- O(q)
- where q is the largest prime factor of p-1
- and p is the largest prime factor of N
LINKS