I think the following alternate Stage 2 algorithms are well thought out. I wrote this and sat with it for a few days before posting because I wanted to make sure I understood the Pm1 algorithms so that I do not accidentally mix Stage 1 and 2. These two modifications are what I would like to present. My apologies if they are flawed, and please tell me if you see a flaw. I currently do not see one.
Let Mp be the Mersenne number to be tested.
Let B1 and B2 be chosen as usual. Assume B2 > B1 as when a great deal of ram is used.
Let E be the exponent calculated in Stage 1 of Pm1.
Suppose that Pm1 found no factors in stage 1.
Let H = 3^{2pE} as usual.
Modification 1:
Suppose we are willing to perform the PRP test base H instead of base 3.
Let m = the iteration number for the PRP test. We can presuppose m = 10^6.
Before Stage 2 of Pm1, we perform the first m iterations of the PRP test using base H.
Let M = H^{2^m} = 3^{2pE*2^m} = value of the m^{th} iteration of the PRP test mod Mp with base H instead of base 3.
Modification 1 of Stage 2 calculates the following:
Π (M*H^{q}1)*(H^{q}1) mod Mp = Π (3^{2pE*(2^m+q)}1)*(3^{2pEq}1) mod Mp, where this product is taken over all q such that B1<q<=B2.
The time cost of this Modification 1 of Stage 2 algorithm are 50% larger, plus the cost of arriving at iteration m = 10^6 based on this procedure, which according to my computer's speed adds about 25% more time depending on the length of Mp. Thus, in total, including Stage 1, this Pm1 test is about 38% more time expensive:
1. Calculate M. (First 1% of the PRP test.)
2. Calculate H^{q}. (First multiplication, from an array, and part of the original Stage 2 algorithm)
3. Multiply M by H^{q} and subtract 1. (Second multiplication, and the only new multiplication. The subtraction is essentially free.)
4. Multiply by H^{q}1. (Third multiplication, and part of the original stage 2 algorithm)
The gain is all the unknown factors of each 2^m+q, which have on average 13.45 distinct prime factors each, a huge step from the single prime factor q. Note that 2^m+q may have common factors with E. However, since 2^m+q has over 3*10^{5} digits, that does not prevent us from gaining many prime factors.
Modification 2 of Stage 2 calculates the following:
Suppose we do not want to perform the PRP test base H and we insist on performing the PRP test base 3.
Then let B3 = a (necessarily even) primorial such that B3 >> B2.
Let M = H^{B3}
Instead, Modification 2 of Stage 2 calculates the following:
Π (M*H^{q}1)*(H^{q}1) mod Mp = Π (3^{2pE(B3+q)}1)*(3^{2pEq}1) mod Mp, where this product is taken over all q such that B1<q<=B2.
The time cost of this Modification 2 of Stage 2 algorithm are 50% larger, plus fast calculation of M, even for B3 equaling a fairly large primorial. Thus in total, including Stage 1, this Pm1 test is about 25% more time expensive:
1. Calculate M. (Fairly fast.)
2. Calculate H^{q}. (First multiplication, from an array, and part of the original Stage 2 algorithm)
3. Multiply M by H^{q} and subtract 1. (Second multiplication, and the only new multiplication. The subtraction is essentially free.)
4. Multiply by H^{q}1. (Third multiplication, and part of the original stage 2 algorithm)
The gain is all the factors of each B3+q, none of which are divisible by factors of B3 nor by q. Primorials grow quickly in length, so with very few multiplications, B3 could be much, much larger than B2. Prime95 is already equipped to handle the multiplication of all small primes below 40 million. My understanding as of now is that it is better to have B3 >> B2. If B3 can be taken as 2pE or just p*B1#, each B3+q could be guaranteed to have no factors in common with E and q. I think the smallest viable value of B3 is the smallest primorial greater than B2^{1/0.2} based on a cursory understanding of the Dickman function.
I do not want to dig into any other modifications (such as combining Modifications 1 and 2 or sacrificing time and splitting any of these into the usual Stage 2 and a true Stage 3) until we discuss above. At the risk of perhaps missing a basic mistake, I think these two modifications work and are beneficial.
Last fiddled with by JuanTutors on 20210622 at 22:23
Reason: grammar
