Editing Pollard's p − 1 algorithm (section)

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