13.3 POLLARD'S p − 1 METHOD [POLLARD, 1974]
Find the prime factors of n
- Choose an integer k that is a multiple of all integers less than some bound B; for example, k = B! or k = 1cm{1, 2, …, B}.
- Randomly choose an integer a between 2 and n − 2.
- Compute b = ak (modulo n) and d = gcd{n, b − 1}.
- If d is a trivial divisor of n, start over again with another choice of a and/or k.
Example 13.2
n = 53,467, a = 3, k = 840 = 1cm{i :1 ≤ i ≤ 8}. See Tables 13.3 and 13.4.
Example 13.3
n = 34,163, a = 2, k = 840 = 1cm{i :1 ≤ i ≤ 8}. See Tables 13.5 and 13.6.
13.3.1 Explanation of Pollard's p − 1 Method
Let B be larger than any prime factor of p − 1 where p is a prime factor of n. If k is the least common multiple of all integers i with 1 ≤ i ≤ B, then by Fermat's Little Theorem, ak = aC(p − 1) = 1 (modulo p). This implies p divides both b − 1 = (ak − 1) (modulo n) and n, ensuring that d = gcd{b − 1, n} is a nontrivial divisor of n.
Improved methods to factor require a diversion to review some number theory.
Get Computer Security and Cryptography now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.