mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > GMP-ECM

Reply
 
Thread Tools
Old 2021-04-25, 16:23   #1
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

52×127 Posts
Default 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
ATH is offline   Reply With Quote
Old 2021-04-25, 16:26   #2
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

24·13·47 Posts
Default

Quote:
Originally Posted by ATH View Post
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
LaurV is offline   Reply With Quote
Old 2021-04-25, 17:05   #3
axn
 
axn's Avatar
 
Jun 2003

19×271 Posts
Default

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

Quote:
Originally Posted by ATH View Post
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
axn is offline   Reply With Quote
Old 2021-04-25, 17:39   #4
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

C6716 Posts
Default

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.
ATH is offline   Reply With Quote
Old 2021-04-25, 18:20   #5
axn
 
axn's Avatar
 
Jun 2003

10100000111012 Posts
Default

Quote:
Originally Posted by ATH View Post
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.
axn is offline   Reply With Quote
Old 2021-04-25, 19:48   #6
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2·32·83 Posts
Default

Quote:
Originally Posted by axn View Post
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
R. Gerbicz is offline   Reply With Quote
Old 2021-05-01, 15:18   #7
patnashev
 
"Pavel Atnashev"
Mar 2020

22·11 Posts
Default

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.
patnashev is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
I found the primality test, there seems to be no composite numbers that pass the test sweety439 sweety439 7 2020-02-11 19:49
Modifying the Lucas Lehmer Primality Test into a fast test of nothing Trilo Miscellaneous Math 25 2018-03-11 23:20
Double check LL test faster than first run test lidocorc Software 3 2008-12-03 15:12
Will the torture test, test ALL available memory? swinster Software 2 2007-12-01 17:54
A primality test for Fermat numbers faster than P├ępin's test ? T.Rex Math 0 2004-10-26 21:37

All times are UTC. The time now is 19:17.


Tue Oct 19 19:17:08 UTC 2021 up 88 days, 13:46, 0 users, load averages: 1.86, 2.05, 1.85

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.