mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Data

Reply
 
Thread Tools
Old 2021-04-14, 03:33   #12
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

22·1,873 Posts
Default

Quote:
Originally Posted by kriesel View Post
How useful would P+1 be, for wavefront Mersenne exponents?
Yes, useless.

I'm not even sure it will be useful to the let's get number of unfactored exponents below 20M crowd.

The biggest advantage I see to studying P+1 is that stage 2 should be faster and Montgomery showed a way to convert a P-1 stage 2 into a P+1 stage 2.

Last fiddled with by Prime95 on 2021-04-14 at 03:34
Prime95 is offline   Reply With Quote
Old 2021-04-14, 03:41   #13
axn
 
axn's Avatar
 
Jun 2003

2×13×191 Posts
Default

Quote:
Originally Posted by kriesel View Post
How useful would P+1 be, for wavefront Mersenne exponents?
I had thought the applicable factoring methods were already fully exploited by GIMPS.
Doubtful that P+1 will breakeven for wavefront. Like, say, there might be a 1% probability, but costs more than 1% of PRP test (made-up numbers for illustrative purpose).
It is more costly than P-1, it loses the free "2p", and there is only a 50% chance of picking the correct seed. Sure, the other 50% of time you have done a stealth P-1, but since it is costlier than P-1 you might end up choosing smaller bounds. Honestly, I don't know. It is worth crunching the numbers to see if it might be worthwhile.

However, it *will* be useful for the "20M unfactored" project.

Quote:
Originally Posted by kriesel View Post
How applicable is Mihai's method of saving some powers of 3 produced from PRP iteration computations, in the parallel approach of PRP and P-1 stage 1, for a possible parallel P+1 stage 1 (also)?
Is one attempt at P+1 with seed 3 or 9 fast enough to be worthwhile? (Does seed 3 even work for Mersennes?)
IIUC, P+1 computation sequence is different enough to not be able to exploit that trick.

Quote:
Originally Posted by kriesel View Post
Seems to me if we were going to attempt both P+1 and P-1, P+1 would go first, and then a determination whether it was in effect a slow P-1, since it seems pointless to do P-1 slow and then again fast on the same bounds and seed.
You can only determine if it was a slow P-1 once a factor is revealed. At that point, it becomes a moot point.
So after a failed P+1 attempt, you still might want to run a P-1, but this time, your expected probability of success is reduced
axn is online now   Reply With Quote
Old 2021-04-14, 03:51   #14
axn
 
axn's Avatar
 
Jun 2003

2·13·191 Posts
Default

Quote:
Originally Posted by Prime95 View Post
I'm not even sure it will be useful to the let's get number of unfactored exponents below 20M crowd.
There are going to be some stubborn sub-ranges in the 10M-40M region where P-1 and TF have done their part, and only way forward is to do deeper P-1 or TF (ECM being too inefficient) which will be very costly. It would be better to run 3-4 P+1 curves using smaller bounds as way to find the required additional factors to finish off such ranges.
Basically, deeper P-1 on already P-1ed exponents have poor cost-to-benefit ratio. Having P+1 which searches a different factor space doesn't suffer from prior P-1 runs.
Anyway, I don't think there is any urgency in having this feature, if at all. Although, now that I think about it, P95 deals with the general form (k*b^n+c)/f, and so other projects might be able to use it.
axn is online now   Reply With Quote
Old 2021-04-14, 14:22   #15
axn
 
axn's Avatar
 
Jun 2003

2·13·191 Posts
Default

Quote:
Originally Posted by Prime95 View Post
The P+1 2/7 seed is special, we find a factor f when k=(f+1)/6 is B1/B2-smooth but only 50% of the time.

The P+1 6/5 seed is also special, we find a factor f when k=(f+1)/4 is B1/B2-smooth but only 50% of the time.
If f=5 (mod 6) and f+1 is smooth, 2/7 seed will find it.
If f=1 (mod 6) and f-1 is smooth, then also 2/7 will find it
If f=3 (mod 4) and f+1 is smooth, 6/5 will find it
If f=1 (mod 4) and f-1 is smooth, then also 6/5 will find it.

In terms of mersenne factors, we have the following success matrix:
Code:
f mod 24 | P+1 smooth | P-1 smooth | Neither smooth
---------+------------+------------+---------------
  1      | Neither    | 2/7,  6/5  | Neither
  7      | 6/5        | 2/7        | Neither
 17      | 2/7        | 6/5        | Neither
 23      | 2/7, 6/5   | Neither    | Neither
From this, we can calculate the total probability of a 2/7 run or a 6/5 run to yield a factor (assuming no prior P-1). We can also calculate cumulative probability of two runs, as well as optimal sequence, etc. Would this make P+1 a viable replacement for P-1 at the PRP wavefront?!
axn is online now   Reply With Quote
Old 2021-04-14, 18:52   #16
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

101010011002 Posts
Default

Quote:
Originally Posted by axn View Post
Doubtful that P+1 will breakeven for wavefront. Like, say, there might be a 1% probability, but costs more than 1% of PRP test (made-up numbers for illustrative purpose).
It is more costly than P-1, it loses the free "2p", and there is only a 50% chance of picking the correct seed. Sure, the other 50% of time you have done a stealth P-1, but since it is costlier than P-1 you might end up choosing smaller bounds. Honestly, I don't know. It is worth crunching the numbers to see if it might be worthwhile.

However, it *will* be useful for the "20M unfactored" project.
When B1 > e (e = exponent), the algorithm p-1 loses the advantage of the free "2p" you said above. I found that for several exponents less than 10M, there are people running p-1 with B1 > e.
alpertron is offline   Reply With Quote
Old 2021-04-15, 02:15   #17
axn
 
axn's Avatar
 
Jun 2003

10011011001102 Posts
Default

Quote:
Originally Posted by alpertron View Post
When B1 > e (e = exponent), the algorithm p-1 loses the advantage of the free "2p" you said above. I found that for several exponents less than 10M, there are people running p-1 with B1 > e.
The advantage is not that we know to include 2p in the stage 1 powering routine, but rather, the part that needs to be smooth ((f-1)/2p) is much smaller and therefore higher probability of success compared to a regular number of same size (f-1). This is regardless of the bounds chosen.
/IIUC
axn is online now   Reply With Quote
Old 2021-04-15, 13:36   #18
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

22·3·113 Posts
Default

In Prime95 running one curve with specified B1 and B2 is 10 times slower than running P-1 with the same bounds.

So I think that for some cases with exponents less than about 10 million, P+1 could help.
alpertron is offline   Reply With Quote
Old 2021-04-25, 01:26   #19
ixfd64
Bemusing Prompter
 
ixfd64's Avatar
 
"Danny"
Dec 2002
California

45168 Posts
Default

Dumb question: does P+1 have an analogue of the Brent–Suyama extension?
ixfd64 is offline   Reply With Quote
Old 2021-04-25, 02:20   #20
axn
 
axn's Avatar
 
Jun 2003

136616 Posts
Default

Quote:
Originally Posted by ixfd64 View Post
Dumb question: does P+1 have an analogue of the Brent–Suyama extension?
Yes, but George needs to confirm whether he implemented it or not.
axn is online now   Reply With Quote
Old 2021-04-25, 04:30   #21
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

11101010001002 Posts
Default

Quote:
Originally Posted by axn View Post
Yes, but George needs to confirm whether he implemented it or not.
I did not.
Prime95 is offline   Reply With Quote
Old 2021-05-03, 20:00   #22
ixfd64
Bemusing Prompter
 
ixfd64's Avatar
 
"Danny"
Dec 2002
California

2×3×397 Posts
Default

Another question: I know it's possible to further generalize P-1 and P+1 using cyclotomic polynomials. Would this be beneficial to GIMPS?

Last fiddled with by ixfd64 on 2021-05-03 at 20:01
ixfd64 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Recommendations for understanding ECM? hansl GMP-ECM 2 2019-05-31 01:16
Understanding Mersenne PRP Runtime Error Math 3 2019-03-24 00:56
Understanding status info Idgo Information & Answers 9 2018-11-28 10:49
Understanding NFS Demonslay335 YAFU 11 2016-01-08 17:52
LL Test: Understanding the math zacariaz Homework Help 32 2007-05-16 15:18

All times are UTC. The time now is 12:37.

Sun May 16 12:37:35 UTC 2021 up 38 days, 7:18, 0 users, load averages: 2.48, 2.40, 2.25

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.