Monday, December 23, 2019

[xoartqzd] Large primes with generator 2

We use isprimroot_approx to find primes less than certain powers of 2 which have 2 as a primitive root.  Note that these aren't necessarily the largest primes less than the given power of two which have 2 as a primitive root.  The are the largest that have that property and for which p-1 could be easily factored.

Not sure what this is useful for.  If we want a prime such that p-1 is easily factored because it has a large prime factor, we can explicitly search for a safe prime (with primitive root 2).  If we want a prime such that p-1 is easily factored because it is smooth, we can explicitly search for primes like that as well, for example, search the form 1 + 2 * 3^a * 5^b.

2^ 2 - 1
2^ 3 - 3
2^ 4 - 3
2^ 5 - 3
2^ 6 - 3
2^ 7 - 21
2^ 8 - 29
2^ 11 - 19
2^ 12 - 3
2^ 15 - 19
2^ 16 - 165
2^ 23 - 21
2^ 24 - 227
2^ 31 - 19
2^ 32 - 5
2^ 47 - 147
2^ 48 - 59
2^ 63 - 165
2^ 64 - 59
2^ 95 - 211
2^ 96 - 147
2^ 127 - 309
2^ 128 - 275
2^ 191 - 19
2^ 192 - 333
2^ 255 - 19
2^ 256 - 189
2^ 383 - 13299
2^ 384 - 2147
2^ 511 - 1261
2^ 512 - 3459
2^ 767 - 19045
2^ 768 - 22467
2^ 1023 - 16611
2^ 1024 - 49355
2^ 1535 - 41379
2^ 1536 - 53987
2^ 2047 - 96459
2^ 2048 - 107325
2^ 3071 - 258267
2^ 3072 - 77405
2^ 4095 - 185469
2^ 4096 - 172029
2^ 6143 - 1093917
2^ 6144 - 1527539
2^ 8191 - 3821091
2^ 8192 - 5565653 , 2^ 8192 - 7092909 , 2^ 8192 - 7556165

(Found a few extra for 2^8192 in parallel search left running too long.)

No comments :