Re: question about result from mpz_ModPow

[Marco Bodrato]

Ciao,

Il giorno Domenica, Agosto 16, 2026 11:08 CEST, "Marco Bodrato" <bodrato at anjara.org> ha scritto:
Il giorno Domenica, Agosto 02, 2026 15:55 CEST, rich beck <rich.beck at sbcglobal.net> ha scritto:

result = 3 ^ (prime-1)/2 MOD prime, where prime=329 x 2^4193199 +1,
and 3 is a primitive root of the prime.

The result should be the totient, (or (prime-1)) but i am not getting
that result in GMP.

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.
Also detecting the squares of that form is really simple.
Now we have a (small but infinite) class of numbers that allows us to return 2 (surely prime).
If we decide to disable this additional test, it's enough to #define GMP_ENABLE_PROTH_TEST 0
 
Another class that would be easy to detect is the form k*2^n-1.
We already have some pieces of code that could be adapted for them, but it's more complex.
 
Ĝis,m