Monday, February 15, 2021

[sehpahxo] generator of largest safe prime

? q=2618163402417*2^1290000-1;
? s=2*q+1;
? addprimes(q);
? lift(znprimroot(s))
time = 4,760 ms.

q is the currently largest known Sophie Germain prime.  s is therefore the largest known safe prime.  i don't understand how Pari/GP can compute the smallest primitive root so quickly.

omitting addprimes(q) increases running time to 18 hours; same result.

No comments :