mersenneforum.org > Math Can we begin PRP using part of the results of P-1 stage 1?
 Register FAQ Search Today's Posts Mark Forums Read

2021-06-16, 00:42   #12
Zhangrc

"University student"
May 2021
Beijing, China

2·32·7 Posts

Quote:
 Originally Posted by JuanTutors Perhaps 18.4 prime factors for each value of k is enough to make it matter? Or would the GCD stage take too long?
Only 18.4? You need tens of thousands, if not millions.

2021-06-16, 02:14   #13
JuanTutors

"Juan Tutors"
Mar 2004

13×43 Posts

Quote:
 Originally Posted by Zhangrc Only 18.4? You need tens of thousands, if not millions.
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.

 2021-06-16, 21:55 #14 JuanTutors     "Juan Tutors" Mar 2004 13×43 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 $ln(10^8 ln 10) \approx 19.25$ distinct prime factors, which is why I was suggesting waiting until near the end to perform a third P-1 test. However, even a smaller integer with 10^6 digits has on average $ln(10^6 ln 10) \approx 14.65$ 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 2021-06-16 at 22:00
2021-06-17, 19:27   #15
JuanTutors

"Juan Tutors"
Mar 2004

22F16 Posts

Quote:
 Originally Posted by LaurV Then you take the GCD step, and... what?

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 well-chosen 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 2021-06-17 at 19:30

2021-06-17, 20:51   #16
Viliam Furik

"Viliam Furík"
Jul 2018
Martin, Slovakia

2×353 Posts

Quote:
 Originally Posted by JuanTutors (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 well-chosen 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.
Do we need to factor the 2^m+k? It's my understanding of GCD that if for any number, in this case, some power of 3, we do GCD of it (minus 1) and the Mersenne number, and we get result other than 1, the result will directly be a factor of Mersenne number, per definition of GCD. If the factor isn't the Mersenne number itself, we are good.

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^p-1)), 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^p-1)) is still 3 (mod 2^p-1). 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 P-1, 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 P-1 would be when the 2^m+k would have just the right factors that are higher than B1.

What do you think?

2021-06-18, 00:15   #17
JuanTutors

"Juan Tutors"
Mar 2004

13×43 Posts

Quote:
 Originally Posted by Viliam Furik Do we need to factor the 2^m+k?
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:
 Originally Posted by Viliam Furik It sounds like a reasonable feature if it works as promised.
Agreed.

Quote:
 Originally Posted by Viliam Furik Using the PRP test as a free booster to speed up the ride is a great idea, IMO.
Hopefully it's possible. GPUto72 already implements a time saver using 3^(2pE). I was trying to find the theorem about the length of the distinct prime factors of a randomly chosen large integer, but I could not find it to estimate the probability of finding a factor. (For some reason I have in my mind the idea that for a random number, the length of its successive distinct prime factors grows on average by multiples of 2.)

I don't know the exact details of the P-1 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 P-1 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 2021-06-18 at 01:13

2021-06-18, 11:29   #18
Viliam Furik

"Viliam Furík"
Jul 2018
Martin, Slovakia

70610 Posts

Quote:
 Originally Posted by JuanTutors I was trying to find the theorem about the length of the distinct prime factors of a randomly chosen large integer, but I could not find it to estimate the probability of finding a factor.
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.

2021-06-18, 12:25   #19
Dr Sardonicus

Feb 2017
Nowhere

2·33·5·19 Posts

Quote:
 Originally Posted by JuanTutors I was trying to find the theorem about the length of the distinct prime factors of a randomly chosen large integer, but I could not find it to estimate the probability of finding a factor. (For some reason I have in my mind the idea that for a random number, the length of its successive distinct prime factors grows on average by multiples of 2.)
Not quite what you're asking, but possibly related:

Hardy-Ramanujan Theorem

Erdős-Kac Theorem

Golomb-Dickman 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.

 2021-06-18, 14:08 #20 JuanTutors     "Juan Tutors" Mar 2004 13×43 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 32pE instead of with 3, then without too much difficulty and just double the time for stage 2, plus waiting until iteration m = 106, 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 = 106 or so: (32pE*2^m)*(32pEq)*(32pEq-1) = (32pE(2^m+q))*(32pEq-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 32pEq and 32pEq-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 32pE*2, 32pE*4, 32pE*6, ... in half (by cutting out the later half of the list) so that we can then store a second array of the same half-length containing 32pE*2pE*2, 32pE*2pE*4, 32pE*2pE*6, ... then we can modify the above test to calculate (32pE*2^m)*(32pE*2pEq)*(32pEq-1) = (32pE(2^m+2pEq))*(32pEq-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 2021-06-18 at 14:10
 2021-06-22, 22:22 #21 JuanTutors     "Juan Tutors" Mar 2004 22F16 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
2021-06-23, 02:53   #22
axn

Jun 2003

3·7·13·19 Posts

Quote:
 Originally Posted by JuanTutors Modification 1 of Stage 2 calculates the following: 1. Calculate M. (First 1% of the PRP test.) 2. Calculate Hq. (First multiplication, from an array, and part of the original Stage 2 algorithm) 3. Multiply M by Hq and subtract 1. (Second multiplication, and the only new multiplication. The subtraction is essentially free.) 4. Multiply by Hq-1. (Third multiplication, and part of the original stage 2 algorithm)
Current P-1 stage 2 uses 1 multiplication to handle two q's. In your new scheme, it will take 4 multiplications to handled 1 q (Hq, M*Hq, (Hq-1) * (M*Hq-1), and Π).

Quote:
 Originally Posted by JuanTutors 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:
That makes it roughly 8x costlier stage 2. Since stage 2 is already longer than stage 1, overall this will be about 5x more time than regular P-1.

Quote:
 Originally Posted by JuanTutors 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*105 digits, that does not prevent us from gaining many prime factors.
Sadly, most of the 13.45 factors are completely useless. A factor q will divide a p-1 with probability 1/q (well, technically 1/(q-1)). Which means, for example, a 10-digit q is only 1% as good as an 8-digit q. A 20-digit q is 1/10 billion as good as a 10-digit q. So, while we gain a lot of factors, there is not a chance in our life time to ever see one appear in a found factor's P-1 decomposition. You're better off to just increase the B2 bound in traditional stage 2.

 Similar Threads Thread Thread Starter Forum Replies Last Post Ensigm Factoring 9 2020-08-24 17:32 Chuck PrimeNet 64 2014-01-06 01:22 dabaichi PrimeNet 5 2011-12-07 19:27 Unregistered Information & Answers 0 2010-11-30 23:34 davieddy Lounge 9 2009-08-25 20:01

All times are UTC. The time now is 09:45.

Fri Dec 3 09:45:25 UTC 2021 up 133 days, 4:14, 0 users, load averages: 1.33, 1.19, 1.16