View Single Post
Old 2020-01-23, 21:12   #7
paulunderwood's Avatar
Sep 2002
Database er0rr

13·251 Posts

Originally Posted by Dr Sardonicus View Post
The number of decimal digits in 10*2^13509-1 would also be 2 + floor(13509*log(2)/log(10)).

This is certainly less resources hungry than the method I gave.

It is possible AFAIK that "PRP" means that N "passes" Rabin-Miller to base 3; in this case, in addition to

3^(N-1) == 1 (mod N), that

3^((N-1)/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 M-R, only Fermat PRP. From pfgwdoc.txt:

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,

Last fiddled with by paulunderwood on 2020-01-23 at 21:14
paulunderwood is online now   Reply With Quote