View Single Post
Old 2020-12-15, 01:30   #3
kriesel's Avatar
Mar 2017
US midwest

13EE16 Posts

Originally Posted by ZFR View Post

When computing x, why are we taking 3E*2*P instead of 2E*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 aE*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.
As to why not 2 instead of 3, there's a small-numbers example early in 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

Last fiddled with by kriesel on 2020-12-15 at 01:35
kriesel is online now