Thread: P+1 test is also P-1 ? View Single Post 2021-04-25, 19:48   #6
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

149410 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  