mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   GMP-ECM (https://www.mersenneforum.org/forumdisplay.php?f=55)
-   -   P+1 test is also P-1 ? (https://www.mersenneforum.org/showthread.php?t=26737)

ATH 2021-04-25 16:23

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:
[url]https://mersenneforum.org/showpost.php?p=576652&postcount=199[/url]

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).

[url]https://mersenneforum.org/showpost.php?p=576840&postcount=230[/url]

LaurV 2021-04-25 16:26

[QUOTE=ATH;576842]Will P+1 test in GMP-ECM also find P-1 smooth factors?[/QUOTE]
Nope. that's only coincidental (or accidental :razz:). They find different types of factors. But the classes intersect.

axn 2021-04-25 17:05

[QUOTE=ATH;576842]Will P+1 test in GMP-ECM also find P-1 smooth factors? [/quote]
Yes.

[QUOTE=ATH;576842]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).[/QUOTE]

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.

ATH 2021-04-25 17:39

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.

axn 2021-04-25 18:20

[QUOTE=ATH;576854]How does this work when the test is designed for P+1 to be smooth?[/quote]
That's just the way the math works out.
A simple intro: [url]https://en.wikipedia.org/wiki/Williams%27s_p_%2B_1_algorithm[/url]

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.

R. Gerbicz 2021-04-25 19:48

[QUOTE=axn;576849]
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.[/QUOTE]

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.

patnashev 2021-05-01 15:18

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.


All times are UTC. The time now is 03:13.

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