View Single Post
Old 2020-01-23, 20:46   #6
Dr Sardonicus
Dr Sardonicus's Avatar
Feb 2017

23×409 Posts

Originally Posted by paulunderwood View Post
These are roughly 4200, 7000 and 8500 digits. You can get the exact values with pari/GP with length(decimal(10*2^13509-1)).

"3-PRP" means it passes Fermat's Little Theorem test: 3^(N-1)=1 mod N, which is necessary but not sufficient for a prime. With PFGW you can specify small bases with the -b switch.
The number of decimal digits in 10*2^13509-1 would also be 2 + floor(13509*log(2)/log(10)).

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.

Last fiddled with by Dr Sardonicus on 2020-01-23 at 20:49 Reason: add qualifier
Dr Sardonicus is offline   Reply With Quote