Thread: P+1 test is also P-1 ? View Single Post
2021-04-25, 17:05   #3
axn

Jun 2003

5,081 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