## 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 if$b$ 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.

Pages: 1 2