20210616, 00:42  #12 
"University student"
May 2021
Beijing, China
2·5·11 Posts 

20210616, 02:14  #13 
"Juan Tutors"
Mar 2004
2×3×7×13 Posts 
I was making a suggestion for stage 2, where just one additional prime at a time is being tested (as far as I understand it). In fact a value of B1=10^6 has approximately 72000 prime factors, so 18.4 prime factors would not be bad. I think the problem might be more that the 2^m+k is usually quite large.

20210616, 21:55  #14 
"Juan Tutors"
Mar 2004
2·3·7·13 Posts 
I think there may be a worthwhile modification of my suggestion merging Zhangrc's suggestion and mine. After posting a [BADLY FLAWED] suggestion above is perhaps fixable?
First, a random number with 10^8 digits has on average distinct prime factors, which is why I was suggesting waiting until near the end to perform a third P1 test. However, even a smaller integer with 10^6 digits has on average distinct prime factors. Also, please correct me if I am wrong, but is it not be the case that Mp is as likely to be a probable prime base 3 as it is to be a probable prime base 3^(2pE)? If this is the case, then my suggestion is that we perform the PRP test base 3^(2pE). Then when the test is 1% of the way done on iteration m ≈ Mp/100 ≈ 10^6, less than a week into the PRP test in many cases, we pause the PRP test and do a stage 2 (stage 3?) PRP test with 3^(2pE*(2^m+k)) for adequately chosen values of k. This would test approximately 14.65 distinct prime factors on each iteration. Last fiddled with by JuanTutors on 20210616 at 22:00 
20210617, 19:27  #15 
"Juan Tutors"
Mar 2004
2·3·7·13 Posts 
(from another thread)
Please see my above post where I modified my suggestion. As you see above I suggested performing the PRP test with 3^(2pE) instead of with 3, and then stopping at the m = millionth or so iteration and taking GCDs of 3^(2pE(2^m+k)) for various wellchosen values of k. There are alternate variations of this, but to answer your question, which was, take the GCD and then ... what? If the GCD is not 1, we know that a factor exists from the test, and therefore Mp is not prime. Yes, its' true that we will not know the factor of Mp, because we will not know the factors of 2^m+k, but we will know that Mp is not prime, which has always been the goal of the PRP test. We could, in the future if motivated, factor 2^m+k for as long as it takes to find that factor of Mp, or not. Last fiddled with by JuanTutors on 20210617 at 19:30 
20210617, 20:51  #16  
"Viliam Furík"
Jul 2018
Martin, Slovakia
683 Posts 
Quote:
It sounds like a reasonable feature if it works as promised. Using the PRP test as a free booster to speed up the ride is a great idea, IMO. If we start the test with a modular residue of 3^(2*p*E), where E is computed using B1=1,000,000, and we compute the entire PRP test with this value, what we get in the end is 3^(2*p*E*(2^p1)), which can still give us a factor, and has the added benefit of determining PRP, because if Mp is prime, then the residue of 3^(k*(2^p1)) is still 3 (mod 2^p1). However, in the case of a composite, residues will no longer match for different runs, i.e. with different B1 sizes, but certification should still be possible because we are still doing the same test, but with a different starting value (others should correct me on that if I am wrong because I'm not sure). It could also be done the other way around. First, perform the PRP test. Then, use the residue in P1, instead of 3. As I think about it, it is quite possible it will give no benefit, one way or the other. I think that the only way it could benefit the P1 would be when the 2^m+k would have just the right factors that are higher than B1. What do you think? 

20210618, 00:15  #17  
"Juan Tutors"
Mar 2004
2·3·7·13 Posts 
No, you are correct, we do not need to know the exact smoothness of the factor of Mp. That was my mistake. I will edit my post to acknowledge my deletion.
Quote:
Quote:
I don't know the exact details of the P1 implementation in GIMPS, but if k can be taken as multiples of E, then it can be guaranteed that 2^n+k has no common factors with E. If not, then I guess other methods of choosing k may be more appropriate, such as choosing k to be a multiple of a smaller primorial. From what I understand, if we start the PRP test with base 3^(2pE) instead of base 3, then calculating this modified stage 2 (stage 3?) means taking the mth step, which is 3^(2pE(2^m)) and multiplying that by a large array 3^(2pEk) for with k replaced with 1K, 2K, 3K, ..., nK for K a primorial (and if K can be replaced with E, even better), and then getting the GCD. //EDIT: Looking more deeply at the P1 Stage 2 algorithm, if letting K = E is possible, then storing 3^(2pE*E*2), 3^(2pE*E*4), 3^(2pE*E*6), 3^(2pE*E*8), ... allows us to then use the same bounds B1 and B2 to calculate 3^(2pE*(2^m+qE)) for all primes q such that B1<q<=B2, ensuring that each individual (2^m+qE) in (B1,B2] is neither divisible by a factor of E nor by q, making this a true stage 3. Last fiddled with by JuanTutors on 20210618 at 01:13 

20210618, 11:29  #18 
"Viliam Furík"
Jul 2018
Martin, Slovakia
683 Posts 
I don't know about such a theorem, but I do know there is an unproven conjecture called "abc conjecture", which says something about factors of sums. However, I don't it's useful in this case.

20210618, 12:25  #19  
Feb 2017
Nowhere
3^{2}·557 Posts 
Quote:
HardyRamanujan Theorem ErdősKac Theorem GolombDickman Constant Mersenne numbers have a number of well known properties which mark them as special, e.g. if p > 2 is prime, and q divides 2^p  1, then q = 2*p*k + 1 for some positive integer k. I don't have statistics for the number of factors, or the size of the smallest factor of 2^p  1, but I imagine someone does. I have, from time to time, gone through factor tables for small exponents looking for smallest factors q for which log(q)/(p*log(2)) is largest. The "nightmare" case is that 2^p  1 is a P2 with log(q) > p*log(2)/3. It is a humbling thought that 2^1277  1 is known to be composite, a C385, but has yet to be factored. It is known to have no factors less than 2^68. AFAIK it could be a P2 with smallest factor > 2^425. 

20210618, 14:08  #20 
"Juan Tutors"
Mar 2004
2×3×7×13 Posts 
Not quite the theorems I was after, but my last statement makes me realize that if we can delay stage 2 until PRP has run through its first 10^6 iterations or so, and again assuming that we can perform the PRP test with 3^{2pE} instead of with 3, then without too much difficulty and just double the time for stage 2, plus waiting until iteration m = 10^{6}, we can perform this modified stage 2 with a tremendous number more factors. In fact, letting m be the iteration number of the PRP test, so m = 10^{6} or so:
(3^{2pE*2^m})*(3^{2pEq})*(3^{2pEq}1) = (3^{2pE(2^m+q)})*(3^{2pEq}1) On the left, the second and third factor differ just by 1, so they can be calculated simultaneously. The only two costs of this modified stage 2 are then actually getting to iteration m=10^6 and also multiplying by both of those factors 3^{2pEq} and 3^{2pEq}1 mod Mp. So for double the multiplication and waiting for iteration m = 10^6, we get about 13.6 possible prime factors per iteration of stage 2. As a modification of this  and I don't know whether this is possible or even helpful based on the increased cost  If we cut the array containing 3^{2pE*2}, 3^{2pE*4}, 3^{2pE*6}, ... in half (by cutting out the later half of the list) so that we can then store a second array of the same halflength containing 3^{2pE*2pE*2}, 3^{2pE*2pE*4}, 3^{2pE*2pE*6}, ... then we can modify the above test to calculate (3^{2pE*2^m})*(3^{2pE*2pEq})*(3^{2pEq}1) = (3^{2pE(2^m+2pEq)})*(3^{2pEq}1) This guarantees that on the right, this new product has some number of prime factors which are distinct from factors of E and q. Last fiddled with by JuanTutors on 20210618 at 14:10 
20210622, 22:22  #21 
"Juan Tutors"
Mar 2004
2×3×7×13 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 = 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 
20210623, 02:53  #22  
Jun 2003
5151_{10} Posts 
Quote:
Quote:
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
How to make GMPECM skip stage 1 when feeding the prime95 results  Ensigm  Factoring  9  20200824 17:32 
When did PrimeNet begin rubberstamping results?  Chuck  PrimeNet  64  20140106 01:22 
Only submit part of ECM results?  dabaichi  PrimeNet  5  20111207 19:27 
In which country do you suggest me to begin my act  Unregistered  Information & Answers  0  20101130 23:34 
When did Rock'n'Roll begin?  davieddy  Lounge  9  20090825 20:01 