📂Number Theory

Proof of the Pollard p-1 Factoring Algorithm

Algorithm ¹

Given a semiprime $N$, if $p$ is a smooth prime, then the factorization $N = pq$ of $N$ can be found as follows:

---

Step 1.

$a := 2$ and $L := 1$ are set.

---

Step 2.

$d := \gcd ( a^{L} - 1 , N )$ is calculated.

---

Step 3.

If $1< d < N$, then $d = p$, a divisor of $N$, is found and we are done. Otherwise, it is updated as $L := (L+1)!$. If $L$ becomes too large, revert to $L := 1$ and update it as $a : = a+ 1$. Then return to Step 2.

Explanation

The Pollard $p-1$ factorization algorithm exploits the weakness of smooth primes similar to the Pollig-Hellman algorithm. A single prime number becoming a weakness makes the prime factorization problem easily solvable. Because of this attack method, cryptographic systems that rely on the difficulty of the prime factorization problem cannot use smooth primes as their secret keys.

Principally, it is not necessary to start with $a=2$ as in Step 1 or to use $L = n!$ as in Step 2. It’s simply used because, if $p$ is smooth, then there is a high probability of successfully calculating $d := \gcd ( a^{L} - 1 , N )$.

Proof

$$ (p-1) \mid L \\ (q-1) \nmid L $$ Assuming $p$ is smooth, it is easy to satisfy the condition for $L = n!$. This means for some $i,j \in \mathbb{Z}$ and $k \in \mathbb{N}$, the following holds. $$ \begin{align*} L =& i ( p -1 ) \\ L =& j ( q -1 ) + k \end{align*} $$

Fermat’s Little Theorem: For a prime $p$ and an integer $a$ coprime to $p$, $a^{p-1} \equiv 1 \pmod{p}$

In $\pmod{p}$, $$ \begin{align*} a^{L} & \equiv a^{( p - 1 ) i } \\ & \equiv 1^{i} \\ & \equiv 1 \pmod{p} \end{align*} $$ In $\pmod{q}$, $$ \begin{align*} a^{L} & \equiv a^{( q - 1 ) j + k } \\ & \equiv 1^{j} a^{k} \\ & \equiv a^{k} \pmod{q} \end{align*} $$ Here, since $k \ne 0$, there is a high probability that $a^{k} \ne 1 \pmod{q}$. This means $$ p \mid a^{L} -1 $$

$$ q \nmid a^{L} -1 $$ This implies that $p$ is a divisor of $a^{L} -1$, and since $p$ is also a divisor of $N$, calculating the greatest common divisor of the two numbers results in $$ p = \gcd \left( a^{L} - 1 , N \right) $$

■

See Also

• Prime Factorization

Security Algorithms Utilizing the Difficulty of Prime Factorization Problem

• RSA Public Key Cryptosystem
• Goldwasser-Micali Probabilistic Key Cryptosystem

Attack Algorithms on the Prime Factorization Problem

• Pollard’s p-1 Factorization Algorithm
• Conditions Under Which the Prime Factorization of Semiprimes Becomes Easy