P-1 factoring

[henryzz]

in p-1 when stage 1 has been done to B1 this makes it almost certain that there are no factors up to B1^2
how would i work out what the lowest factor that there can be after stage 2 has been done?

[jasonp]

Originally Posted by henryzz

in p-1 when stage 1 has been done to B1 this makes it almost certain that there are no factors up to B1^2
how would i work out what the lowest factor that there can be after stage 2 has been done?

Completing stage 1 doesn't tell you anything about any unknown factor p, except that p-1 doesn't factor completely into powers of primes < B1. p-1 could be a smooth number except for a factor of B1+2, or even a prime < B1 raised to a power larger than B1, and you'd never know it.

[henryzz]

Originally Posted by jasonp

Completing stage 1 doesn't tell you anything about any unknown factor p, except that p-1 doesn't factor completely into powers of primes < B1. p-1 could be a smooth number except for a factor of B1+2, or even a prime < B1 raised to a power larger than B1, and you'd never know it.

sorry i meant p-1 would have to be >b1^2 to not be found by stage 1

[cheesehead]

Have you read the explanation of the P-1 factorization method in the Mersenne Wiki at http://mersennewiki.org/index.php/P-1_Factorization_Method ?

[akruppa]

The smallest prime p that a (usual) P-1 stage 1 will not necessarily find is p=2q+1, where q is the smallest prime or prime power > B1 so that p is prime. By usual I mean that stage 1 is implemented as gcd(b^e-1,N), e=lcm(1, ..., B1).

So the best lower bound for p you get from P-1 stage 1 is 2*B1+3.

Edit: actually, there may be a Fermat prime >B1, <2B1 so the lower bound is only B1+1.

Alex