Editing Pollard's p − 1 algorithm (section)

{{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>