[hmyencgu] Generators of large safe primes

Here are the least primitive roots (generators) of some very large safe primes discovered by others.

f(k,n)=sophie=k*2^n-1; addprimes(sophie); component(znprimroot(2*sophie+1),2)

f(18543637900515,666667)
time = 6,472 ms.
11

f(183027,265440)
time = 2,373 ms.
5

f(607095,176311)
time = 1,464 ms.
7

f(14962863771,140001)
time = 1,116 ms.
5

f(2540041185,114729)
time = 877 ms.
13

f(109433307,66452)
time = 452 ms.
5

Pari/GP (as of version 2.5.0) seems to have some magical code able to compute the least primitive root of a safe prime much faster than doing even 1 modular exponentiation, after asserting the primality of corresponding Sophie Germain prime.

t(k,n,g)=sophie=k*2^n-1; 1==Mod(g,2*sophie+1)^sophie

t(109433307,66452,5)
time = 55,515 ms.

t(2540041185,114729,13)
time = 3min, 26,513 ms.

t(14962863771,140001,5)
time = 5min, 32,705 ms.

t(607095,176311,7)
time = 9min, 43,161 ms.

t(183027,265440,5)
time = 24min, 24,071 ms.

t(18543637900515,666667,11)
time = 2h, 50min, 5,654 ms.

Perhaps there is an application for very time-consuming Diffie-Hellman key exchange.

See also 16384-bit safe primes and A181356 and comments on RFC 2409 and 3526.