mersenneforum.org P+1 test is also P-1 ?
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2021-04-25, 16:23 #1 ATH Einyen     Dec 2003 Denmark 7·11·41 Posts P+1 test is also P-1 ? The new P+1 test in Prime95 is also finding P-1 factors. 4 of the 8 factors found so far are P-1 smooth within B1/B2 and NOT P+1 smooth: https://mersenneforum.org/showpost.p...&postcount=199 Will P+1 test in GMP-ECM also find P-1 smooth factors? I never read anything about this before, I thought it was a special extra feature George added to his P+1 test, that it was taking more time to include P-1 as well. If yes will P-1 smooth factors only be found by half the seeds x0 same as P+1 smooth factors? (In a P+1 test). https://mersenneforum.org/showpost.p...&postcount=230 Last fiddled with by ATH on 2021-04-25 at 16:24
2021-04-25, 16:26   #2
LaurV
Romulan Interpreter

Jun 2011
Thailand

25·7·43 Posts

Quote:
 Originally Posted by ATH Will P+1 test in GMP-ECM also find P-1 smooth factors?
Nope. that's only coincidental (or accidental ). They find different types of factors. But the classes intersect.

Last fiddled with by LaurV on 2021-04-25 at 16:26

2021-04-25, 17:05   #3
axn

Jun 2003

3·19·89 Posts

Quote:
 Originally Posted by ATH Will P+1 test in GMP-ECM also find P-1 smooth factors?
Yes.

Quote:
 Originally Posted by ATH If yes will P-1 smooth factors only be found by half the seeds x0 same as P+1 smooth factors? (In a P+1 test).
Yes.

Suppose a number N has two smooth prime factors f and g (and other not smooth prime factors, which we don't care about). f is + side smooth, g is - side smooth (i.e. f+1 and g-1 are smooth to given b1/b2 bounds)
Then there exist seeds such that:
1) they will find both f & g when doing a P+1 run to b1/b2 bounds
2) they will find f but not g ...
3) they will find g but not f ...
4) they will find neither f nor g ...

Whether a given seed will find a given factor depends on both the relationship of the seed to the factor and the smoothness side of the factor. As long as they "align", the factor will be found. Probability of alignment is 50%, regardless of whether the smooth side is +1 or -1.

Last fiddled with by axn on 2021-04-25 at 17:06

 2021-04-25, 17:39 #4 ATH Einyen     Dec 2003 Denmark 61258 Posts Thank you. How does this work when the test is designed for P+1 to be smooth? Why is this not in the GMP-ECM Readme under P+1 ?? Granted, I have not done much P+1 factoring, but I have never heard about this before, where has this information been hidden? I guess I should have read actual P+1 theoretical papers, but an important fact like this should be listed in P+1 software.
2021-04-25, 18:20   #5
axn

Jun 2003

507310 Posts

Quote:
 Originally Posted by ATH How does this work when the test is designed for P+1 to be smooth?
That's just the way the math works out.
A simple intro: https://en.wikipedia.org/wiki/Willia...2B_1_algorithm

The thing that needs to be smooth is p-(D|p). If (D|p) is -1, then p+1. If (D|p) is 1, then p-1.

Note:- using P+1 to find P-1 factors is inefficient because a) P+1 is slower, and b) you only have a 50% chance of success, where as pure P-1 has 100% chance of success. Therefore, if you've already run P-1, then P+1 with same bounds is not going to find any additional "p-1" factors.

2021-04-25, 19:48   #6
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

33·5·11 Posts

Quote:
 Originally Posted by axn Whether a given seed will find a given factor depends on both the relationship of the seed to the factor and the smoothness side of the factor. As long as they "align", the factor will be found. Probability of alignment is 50%, regardless of whether the smooth side is +1 or -1.
There is a neat trap here, how you should/shouldn't choose the seeds, if we remain at Wikipedia's writing:
would you choose these starting values: D=3; D=77; and then D=51975 after two failures?
You should really avoid this, the problem with this is that (51975/q)=1 if you know (3/q)=1 and (77/q)=1, and this is independent from the q value, what you don't(!) know.
51975=3^3*5^2*7*11, so
(51975/q)=(3/q)^3*(5/q)^2*(7/q)*(11/q)=(3/q)*1*(77/q)=1
where we haven't used the value of q.
So in general you have to avoid those D for that D*d_i1*...*d_ik is a square number for some earlier d_i1,..,d_ik seeds.

Last fiddled with by R. Gerbicz on 2021-04-25 at 19:50

 2021-05-01, 15:18 #7 patnashev   "Pavel Atnashev" Mar 2020 22×11 Posts There are two special seeds. 2/7 selects plus or minus side that is divisible by 6. 6/5 selects the side divisible by 4. These two seeds increase the probability of smoothness. For arbitrary numbers P+1 method with any of the two seeds finds more factors than P-1 method.

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post sweety439 sweety439 7 2020-02-11 19:49 Trilo Miscellaneous Math 25 2018-03-11 23:20 lidocorc Software 3 2008-12-03 15:12 swinster Software 2 2007-12-01 17:54 T.Rex Math 0 2004-10-26 21:37

All times are UTC. The time now is 02:02.

Sun Jul 25 02:02:31 UTC 2021 up 1 day, 20:31, 0 users, load averages: 2.17, 2.06, 1.98

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.