Editing Pollard's p − 1 algorithm

{{Short description|Special-purpose algorithm for factoring integers}}
{{DISPLAYTITLE:Pollard's ''p''&nbsp;&minus;&nbsp;1 algorithm}}
'''Pollard's ''p''&nbsp;&minus;&nbsp;1 algorithm''' is a [[number theory|number theoretic]] [[integer factorization]] [[algorithm]], invented by [[John Pollard (mathematician)|John Pollard]] in 1974. It is a special-purpose algorithm, meaning that it is only suitable for [[integer]]s with specific types of factors; it is the simplest example of an [[algebraic-group factorisation algorithm]].

The factors it finds are ones for which the number preceding the factor, ''p''&nbsp;&minus;&nbsp;1, is [[smooth number#Powersmooth numbers|powersmooth]]; the essential observation is that, by working in the multiplicative group [[Modular arithmetic|modulo]] a composite number ''N'', we are also working in the multiplicative groups modulo all of ''N'''s factors.

The existence of this algorithm leads to the concept of [[safe prime]]s, being primes for which ''p''&nbsp;&minus;&nbsp;1 is two times a [[Sophie Germain prime]] ''q'' and thus minimally smooth.  These primes are sometimes construed as "safe for cryptographic purposes", but they might be ''unsafe'' &mdash; in current recommendations for cryptographic [[strong prime]]s (''e.g.'' [[ANSI X9.31]]), it is [[necessary but not sufficient]] that ''p''&nbsp;&minus;&nbsp;1 has at least one large prime factor.  Most sufficiently large primes are strong; if a prime used for cryptographic purposes turns out to be non-strong, it is much more likely to be through malice than through an accident of [[random number generation]].  This terminology is considered [[obsolete]] by the cryptography industry: the [[Lenstra elliptic-curve factorization|ECM]] factorization method is more efficient than Pollard's algorithm and finds safe prime factors just as quickly as it finds non-safe prime factors of similar size, thus the size of ''p'' is the key security parameter, not the smoothness of ''p''&nbsp;−&nbsp;1.<ref>[https://web.archive.org/web/20070315100305/http://www.rsa.com/rsalabs/node.asp?id=2217 What are strong primes and are they necessary for the RSA system?], RSA Laboratories (2007)</ref>

==Base concepts==
Let ''n'' be a composite integer with prime factor ''p''.  By [[Fermat's little theorem]], we know that for all integers ''a'' coprime to ''p'' and for all positive integers ''K'':

:<math>a^{K(p-1)} \equiv 1\pmod{p}</math>

If a number ''x'' is congruent to 1 [[Modular arithmetic|modulo]] a factor of ''n'', then the {{nowrap|[[Greatest common divisor|gcd]](''x'' &minus; 1, ''n'')}} will be divisible by that factor.

The idea is to make the exponent a large multiple of ''p''&nbsp;&minus;&nbsp;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 <math>x^w \bmod n</math> as ''w'' runs through those prime powers.  Check at each stage, or once at the end if you prefer, whether {{nowrap|gcd(''x'' &minus; 1, ''n'')}} is not equal to&nbsp;1.

==Multiple factors==

It is possible that for all the prime factors ''p'' of ''n'', ''p''&nbsp;&minus;&nbsp;1 is divisible by small primes, at which point the Pollard ''p''&nbsp;&minus;&nbsp;1 algorithm simply returns ''n''.

==Algorithm and running time==
The basic algorithm can be written as follows:

:'''Inputs''': ''n'': a composite number
:'''Output''': a nontrivial factor of ''n'' or <u>failure</u>

:# select a smoothness bound ''B''
:# define <math>M = \prod_{\text{primes}~q \le B} q^{ \lfloor \log_q{B} \rfloor }</math> (note: explicitly evaluating ''M'' may not be necessary)
:# 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)
:# compute {{nowrap|''g'' {{=}} gcd(''a''<sup>''M''</sup> − 1, ''n'')}} (note: exponentiation can be done modulo&nbsp;''n'')
:# if {{nowrap|1 < ''g'' < ''n''}} then return ''g''
:# if {{nowrap|''g'' {{=}} 1}} then select a larger ''B'' and go to step 2 or return <u>failure</u>
:# if {{nowrap|''g'' {{=}} ''n''}} then select a smaller ''B'' and go to step 2 or return <u>failure</u>

If {{nowrap|''g'' {{=}} 1}} in step 6, this indicates there are no prime factors ''p'' for which ''p''&nbsp;−&nbsp;1 is ''B''-powersmooth.  If {{nowrap|''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&nbsp;''n''. Additionally, when the maximum prime factors of ''p''&nbsp;−&nbsp;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 {{nowrap|O(''B'' × log ''B'' × log<sup>2</sup> ''n'')}}; larger values of ''B'' make it run slower, but are more likely to produce a factor.

=== Example ===

If we want to factor the number ''n'' = 299.
:# We select ''B'' = 5.
:# Thus ''M'' = 2<sup>2</sup> × 3<sup>1</sup> × 5<sup>1</sup>.
:# We select ''a'' = 2.
:# ''g'' = gcd(''a''<sup>''M''</sup> − 1, ''n'') = 13.
:# Since 1 < 13 < 299, thus return 13.
:# 299 / 13 = 23 is prime, thus it is fully factored: 299 = 13 × 23.

==Methods of choosing ''B''==

Since the algorithm is incremental, it is able to keep running with the bound constantly increasing.

Assume that ''p''&nbsp;&minus;&nbsp;1, where ''p'' is the smallest prime factor of ''n'', can be modelled as a random number of size less than&nbsp;{{radic|''n''}}. By [[Dickman function|the Dickman function]], the probability that the largest factor of such a number is less than (''p''&nbsp;&minus;&nbsp;1)<sup>''1/&epsilon;''</sup> is roughly ''&epsilon;''<sup>&minus;''&epsilon;''</sup>; so there is a probability of about 3<sup>&minus;3</sup>&nbsp;=&nbsp;1/27 that a ''B'' value of ''n''<sup>1/6</sup> will yield a factorisation.

In practice, the [[Lenstra elliptic-curve factorization|elliptic curve method]] is faster than the Pollard ''p''&nbsp;&minus;&nbsp;1 method once the factors are at all large; running the ''p''&nbsp;&minus;&nbsp;1 method up to ''B''&nbsp;=&nbsp;2<sup>32</sup> will find a quarter of all 64-bit factors and 1/27 of all 96-bit factors.

==Two-stage variant==
A variant of the basic algorithm is sometimes used; instead of requiring that ''p''&nbsp;−&nbsp;1 has all its factors less than ''B'', we require it to have all but one of its factors less than some ''B''<sub>1</sub>, and the remaining factor less than some {{nowrap|''B''<sub>2</sub> ≫ ''B''<sub>1</sub>}}. After completing the first stage, which is the same as the basic algorithm, instead of computing a new

:<math>M' = \prod_{\text{primes }q \le B_2} q^{ \lfloor \log_q B_2 \rfloor }
</math>

for ''B''<sub>2</sub> and checking {{nowrap|gcd(''a''<sup>''M'''</sup> − 1, ''n'')}}, we compute

:<math>Q = \prod_{\text{primes } q \in (B_1, B_2]} (H^q - 1)</math>

where {{nowrap|''H'' {{=}} ''a''<sup>''M''</sup>}} and check if {{nowrap|gcd(''Q'', ''n'')}} produces a nontrivial factor of&nbsp;''n''. As before, exponentiations can be done modulo&nbsp;''n''.

Let {''q''<sub>1</sub>, ''q''<sub>2</sub>, …} be successive prime numbers in the interval {{nowrap|(''B''<sub>1</sub>, ''B''<sub>2</sub>]}} and ''d''<sub>''n''</sub>&nbsp;=&nbsp;''q''<sub>''n''</sub>&nbsp;−&nbsp;''q''<sub>''n''−1</sub> the difference between consecutive prime numbers. Since typically {{nowrap|''B''<sub>1</sub> > 2}}, {{nowrap|''d''<sub>''n''</sub>}} are even numbers. The distribution of prime numbers is such that the ''d''<sub>''n''</sub> will all be relatively small. It is suggested that {{nowrap|''d''<sub>''n''</sub> ≤ [[Natural logarithm|ln]]<sup>2</sup> ''B''<sub>2</sub>}}. Hence, the values of {{nowrap|''H''<sup>2</sup>}}, {{nowrap|''H''<sup>4</sup>}}, {{nowrap|''H''<sup>6</sup>}},&nbsp;…&nbsp;(mod&nbsp;''n'') can be stored in a table, and {{nowrap|''H''<sup>''q''<sub>''n''</sub></sup>}} be computed from {{nowrap|''H''<sup>''q''<sub>''n''−1</sub></sup>⋅''H''<sup>''d''<sub>''n''</sub></sup>}}, saving the need for exponentiations.

==Implementations==

* The [https://gitlab.inria.fr/zimmerma/ecm GMP-ECM] package includes an efficient implementation of the ''p''&nbsp;−&nbsp;1 method.
* [[Prime95]] and [[MPrime]], the official clients of the [[Great Internet Mersenne Prime Search]], use a modified version of the ''p''&nbsp;−&nbsp;1 algorithm to eliminate potential candidates.

==See also==
* [[Williams's p + 1 algorithm|Williams's ''p'' + 1 algorithm]]

==References==
{{Reflist}}
*{{Cite journal |last=Pollard |first=J. M. |year=1974 |title=Theorems of factorization and primality testing |journal=Proceedings of the Cambridge Philosophical Society |volume=76 |issue=3 |pages=521–528 |doi=10.1017/S0305004100049252 |bibcode=1974PCPS...76..521P |s2cid=122817056 }}
*{{Cite journal |last1=Montgomery |first1=P. L. |last2=Silverman |first2=R. D. |year=1990 |title=An FFT extension to the ''P'' − 1 factoring algorithm |journal=Mathematics of Computation |volume=54 |issue=190 |pages=839–854 |doi=10.1090/S0025-5718-1990-1011444-3 |bibcode=1990MaCom..54..839M |doi-access=free }}
* {{cite book | author =Samuel S. Wagstaff, Jr. | title=The Joy of Factoring | publisher=American Mathematical Society | location=Providence, RI | year=2013 | isbn=978-1-4704-1048-3 |url=https://www.ams.org/bookpages/stml-68 |author-link=Samuel S. Wagstaff, Jr. | pages=138–141 }}

{{Number theoretic algorithms}}

{{DEFAULTSORT:Pollard's p - 1 algorithm}}
[[Category:Integer factorization algorithms]]