## Wednesday, December 05, 2018

### [keouzjxw] Smooth under powers of 2

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