[kriesel]

Originally Posted by ZFR

From https://www.mersenne.org/various/math.php

When computing x, why are we taking 3^E*2*P instead of 2^E*2*P?

Wouldn't any coprime number do? If so, why not choose the smaller one?

E is not just the product of the primes < B1, it's the product of maximum integral powers of each prime fitting < B1 individually, called powersmooth.
The exponentiation a^E*2*p is done mod Mp. So smaller a doesn't really save run time, or operand size after relatively few operations. In practice the exponentiation is done with a full length fft transform from the start, so it saves no run time to use a smaller base.
https://en.wikipedia.org/wiki/Pollar...92_1_algorithm
As to why not 2 instead of 3, there's a small-numbers example early in https://magazine.odroid.com/article/...tical-history/ Later on, this same source includes, also in the context of primality testing, rather than P-1 factoring, the following:

In the more general context of testing numbers of arbitrary size, however, 
it is important to realize that there are certain classes of numbers, all 
of which are Fermat base-2 pseudoprimes, irrespective of whether they are
prime or composite. The two best-known such classes are, firstly, the 
Mersenne numbers M(p) = 2p−1 (for which we restrict the definition to prime
exponents since that is required for a number of this form to have a chance
of being prime); for example, 211−1 passes the test even though it factors as
23 × 89. The second class of such numbers is the Fermat numbers