Pollard's p − 1 algorithm

<h2 id="base-concepts">Base concepts</h2>
Let n be a composite integer with prime factor p. By <a href="/facts/Fermat%27s_little_theorem/qIjSIm2s">Fermat's little theorem</a>, we know that for all integers a coprime to p and for all positive integers K:

a
          
            K
            (
            p
            −
            1
            )
          
        
        ≡
        1
        
          
          (
          mod
          
          p
          )
        
      
    
    {\displaystyle a^{K(p-1)}\equiv 1{\pmod {p}}}

If a number x is congruent to 1 <a href="/facts/Modular_arithmetic/0wtRa5dU">modulo</a> a factor of n, then the <a href="/facts/Greatest_common_divisor/kNFvBuKl">gcd</a>(x − 1, n) will be divisible by that factor.
The idea is to make the exponent a large multiple of p − 1 by making it a number with very many prime factors; generally, we take the product of all prime powers less than some limit B. Start with a random x, and repeatedly replace it by 
 
 
 
 
 x
 
 w
 
 
 
 mod
 
 n
 
 
 
 
 {\displaystyle x^{w}{\bmod {n}}}
 
 as w runs through those prime powers. Check at each stage, or once at the end if you prefer, whether gcd(x − 1, n) is not equal to 1.

<h2 id="multiple-factors">Multiple factors</h2>
It is possible that for all the prime factors p of n, p − 1 is divisible by small primes, at which point the Pollard p − 1 algorithm simply returns n.

<h2 id="algorithm-and-running-time">Algorithm and running time</h2>
The basic algorithm can be written as follows:

Inputs: n: a composite number
Output: a nontrivial factor of n or failure
<ol><li>select a smoothness bound B</li>
<li>define 
 
 
 
 M
 =
 
 ∏
 
 
 primes
 
  
 q
 ≤
 B
 
 
 
 q
 
 ⌊
 
 log
 
 q
 
 
 ⁡
 
 B
 
 ⌋
 
 
 
 
 {\displaystyle M=\prod _{{\text{primes}}~q\leq B}q^{\lfloor \log _{q}{B}\rfloor }}
 
 (note: explicitly evaluating M may not be necessary)</li>
<li>randomly pick a positive integer, a, which is coprime to n (note: we can actually fix a, e.g. if n is odd, then we can always select a = 2, random selection here is not imperative)</li>
<li>compute g = gcd(aM − 1, n) (note: exponentiation can be done modulo n)</li>
<li>if 1 < g < n then return g</li>
<li>if g = 1 then select a larger B and go to step 2 or return failure</li>
<li>if g = n then select a smaller B and go to step 2 or return failure</li></ol>
If g = 1 in step 6, this indicates there are no prime factors p for which p-1 is B-powersmooth. If g = n in step 7, this usually indicates that all factors were B-powersmooth, but in rare cases it could indicate that a had a small order modulo n. Additionally, when the maximum prime factors of p-1 for each prime factors p of n are all the same in some rare cases, this algorithm will fail.
The running time of this algorithm is O(B × log B × log2 n); larger values of B make it run slower, but are more likely to produce a factor.

<h3>Example</h3>
If we want to factor the number n = 299.

<ol><li>We select B = 5.</li>
<li>Thus M = 22 × 31 × 51.</li>
<li>We select a = 2.</li>
<li>g = gcd(aM − 1, n) = 13.</li>
<li>Since 1 < 13 < 299, thus return 13.</li>
<li>299 / 13 = 23 is prime, thus it is fully factored: 299 = 13 × 23.</li></ol>
<h2 id="methods-of-choosing-b">Methods of choosing B</h2>
Since the algorithm is incremental, it is able to keep running with the bound constantly increasing.
Assume that p − 1, where p is the smallest prime factor of n, can be modelled as a random number of size less than √n. By <a href="/facts/Dickman_function/PE99PvRS">the Dickman function</a>, the probability that the largest factor of such a number is less than (p − 1)1/ε is roughly ε−ε; so there is a probability of about 3−3 = 1/27 that a B value of n1/6 will yield a factorisation.
In practice, the <a href="/facts/Lenstra_elliptic-curve_factorization/PwdIdtQW">elliptic curve method</a> is faster than the Pollard p − 1 method once the factors are at all large; running the p − 1 method up to B = 232 will find a quarter of all 64-bit factors and 1/27 of all 96-bit factors.

<h2 id="two-stage-variant">Two-stage variant</h2>
A variant of the basic algorithm is sometimes used; instead of requiring that p − 1 has all its factors less than B, we require it to have all but one of its factors less than some B1, and the remaining factor less than some B2 ≫ B1. After completing the first stage, which is the same as the basic algorithm, instead of computing a new

M
          ′
        
        =
        
          ∏
          
            
              primes 
            
            q
            ≤
            
              B
              
                2
              
            
          
        
        
          q
          
            ⌊
            
              log
              
                q
              
            
            ⁡
            
              B
              
                2
              
            
            ⌋
          
        
      
    
    {\displaystyle M'=\prod _{{\text{primes }}q\leq B_{2}}q^{\lfloor \log _{q}B_{2}\rfloor }}

for B2 and checking gcd(aM' − 1, n), we compute

Q
        =
        
          ∏
          
            
              primes 
            
            q
            ∈
            (
            
              B
              
                1
              
            
            ,
            
              B
              
                2
              
            
            ]
          
        
        (
        
          H
          
            q
          
        
        −
        1
        )
      
    
    {\displaystyle Q=\prod _{{\text{primes }}q\in (B_{1},B_{2}]}(H^{q}-1)}

where H = aM and check if gcd(Q, n) produces a nontrivial factor of n. As before, exponentiations can be done modulo n.
Let {q1, q2, …} be successive prime numbers in the interval (B1, B2] and dn = qn − qn−1 the difference between consecutive prime numbers. Since typically B1 > 2, dn are even numbers. The distribution of prime numbers is such that the dn will all be relatively small. It is suggested that dn ≤ <a href="/facts/Natural_logarithm/PnreKEzI">ln</a>2 B2. Hence, the values of H2, H4, H6, … (mod n) can be stored in a table, and Hqn be computed from Hqn−1⋅Hdn, saving the need for exponentiations.

<h2 id="implementations">Implementations</h2>
<ul><li>The <a href="https://gitlab.inria.fr/zimmerma/ecm">GMP-ECM</a> package includes an efficient implementation of the p − 1 method.</li>
<li><a href="/facts/Prime95/gyjjG3l3">Prime95</a> and <a href="/facts/MPrime/gyjjG3l3">MPrime</a>, the official clients of the <a href="/facts/Great_Internet_Mersenne_Prime_Search/vuF5SW9X">Great Internet Mersenne Prime Search</a>, use a modified version of the p - 1 algorithm to eliminate potential candidates.</li></ul>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Williams%27s_p_%2B_1_algorithm/qPlGLfS7">Williams's p + 1 algorithm</a></li></ul>

<ul><li>Pollard, J. M. (1974). "Theorems of factorization and primality testing". Proceedings of the Cambridge Philosophical Society. 76 (3): 521–528. <a href="/facts/Bibcode_(identifier)/9HtdQSGB">Bibcode</a>:<a href="https://ui.adsabs.harvard.edu/abs/1974PCPS...76..521P">1974PCPS...76..521P</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1017%2FS0305004100049252">10.1017/S0305004100049252</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:122817056">122817056</a>.</li>
<li>Montgomery, P. L.; Silverman, R. D. (1990). <a href="https://doi.org/10.1090%2FS0025-5718-1990-1011444-3">"An FFT extension to the P − 1 factoring algorithm"</a>. Mathematics of Computation. 54 (190): 839–854. <a href="/facts/Bibcode_(identifier)/9HtdQSGB">Bibcode</a>:<a href="https://ui.adsabs.harvard.edu/abs/1990MaCom..54..839M">1990MaCom..54..839M</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1090%2FS0025-5718-1990-1011444-3">10.1090/S0025-5718-1990-1011444-3</a>.</li>
<li><a href="/facts/Samuel_S._Wagstaff,_Jr./23qeUItG">Samuel S. Wagstaff, Jr.</a> (2013). <a href="https://www.ams.org/bookpages/stml-68">The Joy of Factoring</a>. Providence, RI: American Mathematical Society. pp. 138–141. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-1-4704-1048-3.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">What are strong primes and are they necessary for the RSA system?, RSA Laboratories (2007) <a href="https://web.archive.org/web/20070315100305/http://www.rsa.com/rsalabs/node.asp?id=2217" target="_blank">https://web.archive.org/web/20070315100305/http://www.rsa.com/rsalabs/node.asp?id=2217</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
</ol>

Pollard's p − 1 algorithm open-in-new

Pollard's p − 1 algorithm