P-1 factoring
 

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?

[QUOTE=henryzz;132866]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?[/QUOTE]
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.

[quote=jasonp;132893]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.[/quote]
sorry i meant p-1 would have to be >b1^2 to not be found by stage 1

Have you read the explanation of the P-1 factorization method in the Mersenne Wiki at [URL="http://mersennewiki.org/index.php/P-1_Factorization_Method"]http://mersennewiki.org/index.php[U][COLOR=#0000ff]/P-1_Factorization_Method[/COLOR][/U][/URL] ?

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