Pollard's P-1 Factoring Algorithm in Plain C Coding Pollard's 1974 Paper on Factoring Within P-1 Multiplicative Subgroups Murage Kibicho Jul 27, 2026 1 Share We teach programmers how to turn advanced math papers into code. Subscribe. 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 ensure the result divides all numbers inclusive of the given bound: Test exponent finder If you’re coding along, then for primeBound=1000, you get: S(1438 bits) :7128865274665093053166384155714272920668358861885893040452001991154324087581111499476444151913871586911717817019575256512980264067621009251465871004305131072686268143200196609974862745937188343705015434452523739745298963145674982128236956232823794011068809262317708861979540791247754558049326475737829923352751796735248042463638051137034331214781746850878453485678021888075373249921995672056932029099390891687487672697950931603520000 Next, we write a terse wrapper for p-1: Wrapper for Pollard p-1 2.1 Testing Our Code We shall test using the Wikipedia example: Example from wikipedia We call our function like this: Calling p-1 factorizer We find 13 as expected: 13 found as factor 3.0 Improvements There exists a two stage variant. One simply increases the bound such that the algorithm spends more time in this second phase than the first phase. Stage 2 variant. Taken from (Charest, 2005) In this case, the p-1 algorithm will find p if its p-1 prime factors are all less than the Stage 1 bound, except for 1 factor that is smaller than the second bound (Charest, 2005) . References 1 Pollard, J. M. (1974). Theorems on Factorization and Primality Testing . Mathematical Proceedings of the Cambridge Philosophical Society , 76 (3), 521–528. doi:10.1017/S0305004100049252 2 Charest, A. (2005). Pollard’s p-1 and Lenstra’s factoring Algorithm . McGill University. Link . 3 OisinResearch. (2006). Sieve2dmono. GitHub repo . 1 Share Previous