We list some primes p with smooth p-1 which are slightly less than nice powers of 2. More precisely, primes of the form k*2^m+1 with the first priority to maximize m and second priority to maximize k, all while obeying the constraint to be less than 2^n. The nice exponents n are of the form {1,3,5}*2^e.

Previously, we computed primes of that form slightly greater than powers of 2.

We furthermore constrain the primes to have 3 as its least primitive root (generator). 2 seems to never be a primitive root for primes of this form, if the exponent m is large. (Why?)

Primes with smooth p-1 are useful because it is one of the forms for which it can easily be checked whether a given number is a primitive root of the prime. If primitive roots are likely to be used with these primes, we might as well make sure it has a nice one, namely 3.

If k*2^m is not smooth enough, consider Pierpont primes.

Pari/GP source code:

? f(bits)=local(g,m,x);found=0;for(db=1,bits,for(mx=1,2^db-1,m=2^db-mx; x=m*2^(bits-db)+1; if(ispseudoprime(x),g=lift(znprimroot(x));if(g==3,print(m,"*2^",bits-db,"+1 < 2^",bits);break(2)))))

? for(i=2,100,f(2^i);f(2^(i-2)*5);f(2^(i-1)*3))

3*2^1+1 < 2^4

1*2^4+1 < 2^5

1*2^4+1 < 2^6

7*2^4+1 < 2^8

1*2^8+1 < 2^10

13*2^8+1 < 2^12

5*2^13+1 < 2^16

1*2^16+1 < 2^20

7*2^20+1 < 2^24

13*2^28+1 < 2^32

113*2^33+1 < 2^40

29*2^43+1 < 2^48

95*2^57+1 < 2^64

29*2^75+1 < 2^80

7*2^92+1 < 2^96

7*2^120+1 < 2^128

167*2^151+1 < 2^160

13*2^188+1 < 2^192

467*2^247+1 < 2^256

13*2^316+1 < 2^320

667*2^374+1 < 2^384

127*2^504+1 < 2^512

101*2^633+1 < 2^640

373*2^758+1 < 2^768

1331*2^1013+1 < 2^1024

613*2^1270+1 < 2^1280

193*2^1528+1 < 2^1536

19*2^2038+1 < 2^2048

1385*2^2549+1 < 2^2560

179*2^3063+1 < 2^3072

305*2^4087+1 < 2^4096

269*2^5109+1 < 2^5120

1733*2^6133+1 < 2^6144

553*2^8182+1 < 2^8192

575*2^10229+1 < 2^10240

9637*2^12274+1 < 2^12288

5717*2^16371+1 < 2^16384

3457*2^20468+1 < 2^20480

1961*2^24565+1 < 2^24576

2561*2^32755+1 < 2^32768

## No comments :

Post a Comment