Sunday, December 15, 2019

[jtzjuqjl] Some primes less than 2^2048 with smooth p-1

1 + 2^2, 3 bits, least primitive root 2, searched for primes of the form 1 + 2^a (Fermat) with znprimroot=2

1 + 2^16, 17 bits, least primitive root 3, searched for primes of the form 1 + 2^a (Fermat), no restrictions on primitive root (any znprimroot)

1 + 2^1 * 3^1252, 1986 bits, least primitive root 2, form 1 + 2^a * 3^b (Pierpont), znprimroot=2

1 + 2 * 3^478 * 5^554, 12% of 2^2048, least primitive root 2, form 1 + 2 * 3^b * 5^c, znprimroot=2

1 + 2^2 * 3^454 * 5^571, 66% of 2^2048, least primitive root 2, form 1 + 2^a * 3^b * 5^c, znprimroot=2

1 + 2 * 3^90 * 5^820, 77% of 2^2048, least primitive root 3, form 1 + 2 * 3^b * 5^c, any znprimroot

1 + 2^626 * 3^897, 82% of 2^2048, least primitive root 5, form 1 + 2^a * 3^b (Pierpont), any znprimroot

1 + 2^1616 * 3^66 * 5^141, 99.96% of 2^2048, least primitive root 34, form 1 + 2^a * 3^b * 5^c, any znprimroot

For primes with znprimroot=2, the exponent of 2 in the prime tends to be small.

Not sure what these might be useful for.  Perhaps to demonstrate Diffie-Hellman with a large but weak modulus.  It takes only 10 seconds to compute a discrete logarithm with one of these 2048-bit moduli:

? znlog(3,znprimroot(1+2^2*3^454*5^571));
time = 10,525 ms.

No comments :