Pollard's P-1 Factoring Algorithm in Plain C

We teach programmers how to turn advanced math papers into code. Subscribe.

Pollard’s p-1 summary. Taken from (Wagstaff, 2013)

1.0 Paper Introduction

Theorems on Factorization and Primality Testing (Pollard, 1974)1 introduces a special-purpose p-1 algorithm for factoring integers composite integers N, into prime factors p, where (p-1) has small prime factors.

Fermat’s Little Theorem permits Pollard’s p-1 algorithm use information about the group’s order to find a factor p of N:

Fermat’s Little Theorem. Taken from (Charest, 2005)

Here’s Pollard’s insight: if a composite N, has a prime factor p, then there exists a d such that:

Definition of d. Taken from (Charet, 2005)

Let m be the exponent of a, then we can find d if the exponent m is a multiple of p-1 and p-1 has small factors i.e m = c(p-1):

Finding d when p-1 has small factors. Taken from (Charet, 2005)

By choosing m as a product of small prime factors, we must get a factor of N because:

Relationship between finding m and a prime factor of N. Taken from (Charet, 2005)

1.1 Pollard’s P-1 Algorithm

(Pollard, 1974) is unavailable online, so we follow the outline in (Charest, 2005)2 :

Pollard p-1 steps. Taken from (Charest, 2025)

In practice (OisinResearch, 2026)3, one quickly computes a generator g such that:

Simplified generator search

Then tests for the gcd:

GCD test

In our case, this works because if p is a prime factor of N, and p-1 divides always divides S.

1.2 Choosing S

S is called the Stage 1 exponent for p-1. This is simply the LCM of all numbers upto a bound B.

Smart researchers found a tree-like shortcut to find S and it involves computing the LCM of the largest prime powers upto the bound B.

Largest prime power definition

S is a pretty large number. For instance, for B = 10, S = 2520.

Another instance, when B = 1000, S is a 1438 bit number.

2.0 Coding Pollard’s P-1

Code is available on GitHub.

First, we use the tree shortcut to find the LCM of all numbers upto a bound:

Function to find the scalar S

We write a test function to…