Editing Pollard's p − 1 algorithm (section)

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