question about result from mpz_ModPow

[hermann at stamm-wilbrandt.de]

> I would like to test one additional candidate NTT_Prime:
> 31 x 2^8348000 +1, also using 3 as the primitive root,
>  

> It's not too hard to write a program that can test such a prime.
> But remember: but the larger, the slower…
>  
> In the meanwhile, I added a small piece of code into mpz/millerrabin.c
> to detect numbers of the form
> k*2^n+1 with k < 2^n, and use the simple primality test proposed by 
> Proth.
> Detecting them is O(1), the code is really simple:
>  - search a suitable base using mpz_kronecker_ui;
>  - a single mpz_powm gives a deterministic prime/composite response.
> 
Proth test can always use base 3, no need to search for a base.

Exponentiation is done in prime proof software done based on gwnum lib
which is much more efficient than mpz_powm(). gnum lib is from the
GIMPS project (Great Internet Mersenne Prime Search).

paulunderwood created a plugin replacement for mpz_powm(), just
use gw_powm() instead, here an example application:
https://github.com/Hermann-SW/prp_and_sqrtm1/blob/main/sqrtm1.cc

gw_powm() is not as fast as specialized prime proof software can do
modular exponentiation. Jean Penne's LLR software can do faster:
http://jpenne.free.fr/

Regarding your initial question, 31 x 2^8348000 +1 is prime:

hermann at 7950x:~/tst$ ./sllr64 -t16 -d -q"31*2^8348000+1"
Starting Proth prime test of 31*2^8348000+1
Using all-complex AVX-512 FFT length 512K, Pass1=1K, Pass2=512, clm=2, 
16 threads, a = 3
31*2^8348000+1 is prime! (2513000 decimal digits)  Time : 1738.862 sec.
hermann at 7950x:~/tst$

Your number is place 249 of top 5000 list of largest known primes:
https://t5k.org/primes/lists/all.txt


Regards,

Hermann Stamm-Wilbrandt