Factorization: Pollard's $p-1$ method

§ Motivation

We want to continue looking into methods of factorization to see that it is a sufficiently hard problem to solve, and that the RSA algorithm is secure as a result.

§ Pollard's $p - 1$ method

This method works reliably a given composite composed of two primes $m=pq$ such that $p - 1$ is the product of small primes.

Suppose that there exists $L$ such that $(p - 1) \vert L$, but $(q - 1) \nmid L$. Then, it must be true that there exists $i, j, k$ with $k \neq 0$ satisfying

$$L = i(p - 1),\text{ and } L = j(q - 1) + k.$$

Hence, we have $a^L \equiv a^{i(p-1)} \equiv 1 \pmod{p}$ and that $a^L \equiv a^{i(p-1)} \equiv a^k \pmod{q}$. Since the value $k$ has no structure that relates to $\text{ord}_q(a)$, with high probability, for most choices of $a$ we find that $p \vert a^L - 1$ while $q \nmid a^L - 1$. This means that we can use Pollard's $p-1$ to recover $p$.