Editing Pollard's p − 1 algorithm (section)

==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.