View Single Post
 2021-06-22, 22:22 #21 JuanTutors     "Juan Tutors" Mar 2004 13·43 Posts 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 = 32pE 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 = H2^m = 32pE*2^m = value of the mth iteration of the PRP test mod Mp with base H instead of base 3. Modification 1 of Stage 2 calculates the following: Π (M*Hq-1)*(Hq-1) mod Mp = Π (32pE*(2^m+q)-1)*(32pEq-1) mod Mp, where this product is taken over all q such that B1> B2. Let M = HB3 Instead, Modification 2 of Stage 2 calculates the following: Π (M*Hq-1)*(Hq-1) mod Mp = Π (32pE(B3+q)-1)*(32pEq-1) mod Mp, where this product is taken over all q such that B1> 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 B21/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 2021-06-22 at 22:23 Reason: grammar