Pollard’s P-1 Factorization Algorithm

July 21, 2009

Fermat’s little theorem states that for any prime number p, and any other number a, a^{p-1} \equiv 1 \pmod{p}. Rearranging terms, we have a^{p-1} - 1 \equiv 0 \pmod{p}, which means that p divides the left-hand side of the equation, thus p is a factor of the left-hand side.

John Pollard used this idea to develop a factoring method in 1974. His idea is to choose a very large number and see if it has any factors in common with a^{p-1} - 1, thus giving a factor of p. A systematic way to test many very large numbers is by taking large factorials, which have many small factors within them. Thus, Pollard’s p-1 factorization algorithm is this:

1) Choose b, which is known as the smoothness bound, and calculate the product of the primes to b by k = \mathrm{lcm}(1,2,3,\ldots,b).

2) Choose a random integer a such that 1 < a < n.

3) Calculate g=\gcd(a,n). If g is strictly greater than 1, then it is a non-trivial factor of n. Otherwise, continue to the next step.

4) Calculate d = \gcd(a^k - 1, n). If 1 < d < n, then d is a non-trivial factor of n. If d=1, go to Step 1 and choose a larger b. If d=n, go back to Step 2 and choose another a.

In Step 4, you can quit with failure instead of returning to Step 1 ifb becomes too large, where “too large” is probably somewhere around 10^6; in that case, you will need to continue with some other factoring algorithm.

Your task is to write a function that factors integers by Pollard’s p-1 method. What are the factors of 2^{98}-1? When you are finished, you are welcome to read or run a suggested solution, or to post your solution or discuss the exercise in the comments below.

Advertisement

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
5 Comments »