Quote:
Originally Posted by Dr Sardonicus
The number of decimal digits in 10*2^135091 would also be 2 + floor(13509*log(2)/log(10)).
[/quote[
This is certainly less resources hungry than the method I gave.
[quote[
It is possible AFAIK that "PRP" means that N "passes" RabinMiller to base 3; in this case, in addition to
3^(N1) == 1 (mod N), that
3^((N1)/2) == 1 or 1 (mod N).
If N satisfied the first condition but not the second, of course, a proper factorization of N would be in hand.

PFGW does not do a MR, only Fermat PRP. From pfgwdoc.txt:
Quote:
A.3.1 Fermat's method
Fermat's method is NOT a proof, but more like a quick indicator that a
number might be prime.

The program LLR is more sophisticated in this respect.
Please tell us how one gets a factor from the conditions you mention above,