mersenneforum.org > Data Understanding P+1
 Register FAQ Search Today's Posts Mark Forums Read

2021-04-14, 03:33   #12
Prime95
P90 years forever!

Aug 2002
Yeehaw, FL

3·5·499 Posts

Quote:
 Originally Posted by kriesel 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

2021-04-14, 03:41   #13
axn

Jun 2003

25×5×31 Posts

Quote:
 Originally Posted by kriesel 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 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 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

2021-04-14, 03:51   #14
axn

Jun 2003

115408 Posts

Quote:
 Originally Posted by Prime95 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.

2021-04-14, 14:22   #15
axn

Jun 2003

496010 Posts

Quote:
 Originally Posted by Prime95 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?!

2021-04-14, 18:52   #16
alpertron

Aug 2002
Buenos Aires, Argentina

54C16 Posts

Quote:
 Originally Posted by axn 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.

2021-04-15, 02:15   #17
axn

Jun 2003

136016 Posts

Quote:
 Originally Posted by alpertron 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

 2021-04-15, 13:36 #18 alpertron     Aug 2002 Buenos Aires, Argentina 22·3·113 Posts 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.
 2021-04-25, 01:26 #19 ixfd64 Bemusing Prompter     "Danny" Dec 2002 California 45168 Posts Dumb question: does P+1 have an analogue of the Brent–Suyama extension?
2021-04-25, 02:20   #20
axn

Jun 2003

25·5·31 Posts

Quote:
 Originally Posted by ixfd64 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.

2021-04-25, 04:30   #21
Prime95
P90 years forever!

Aug 2002
Yeehaw, FL

1D3D16 Posts

Quote:
 Originally Posted by axn Yes, but George needs to confirm whether he implemented it or not.
I did not.

 2021-05-03, 20:00 #22 ixfd64 Bemusing Prompter     "Danny" Dec 2002 California 238210 Posts 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

 Similar Threads Thread Thread Starter Forum Replies Last Post hansl GMP-ECM 2 2019-05-31 01:16 Runtime Error Math 3 2019-03-24 00:56 Idgo Information & Answers 9 2018-11-28 10:49 Demonslay335 YAFU 11 2016-01-08 17:52 zacariaz Homework Help 32 2007-05-16 15:18

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

Sun May 9 09:48:55 UTC 2021 up 31 days, 4:29, 0 users, load averages: 4.16, 4.15, 3.86