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§

Pollard’s $p - 1$ method

Suppose we know that $m$ is the product of two primes and we want to find a prime factor $p$.

  1. Choose $a$ randomly, and set $j = 1$.
  2. Set $a \equiv a^j \pmod{m}$.
  3. Compute $d = (a-1, m)$.
  4. If $1 \lt d \lt m$, then $d$ is a non-trivial factor of $m$. Otherwise, set $j \leftarrow j + 1$ and repeat the procedure.

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$.