Re: question about result from mpz_ModPow

[Marco Bodrato]

Ciao,

Il giorno Martedi, Agosto 18, 2026 01:31 CEST, hermann at stamm-wilbrandt.de ha scritto:
Proth test can always use base 3, no need to search for a base.
We may refer to different definitions of “Proth number” or expect different results form a “Proth test”.
I use “Proth number” for a numbers $P$ of the form P=k*2^n+1 where $k$ is odd and k<2^n.
I use “Proth test” for testing whether
b^{(P-1)/2} == -1 (mod P)
If it happens for a given number $b$ then one can say that $P$ is prime.
 
With the definitions I use, the number p = 7681 = 15*2^9+1 is a “Proth number”, but
3^{(p-1)/2} == 1 (mod p)
So that base 3 is not the right one to obtain a proof of its primality.
The smaller base that one can use for a “Proth proof of primality" of 7681 is 13.
 
One “can always use base 3” if one adds the condition “3 does not divide k”, but I prefer to extend the test to a wider set of numbers.
 
gw_powm() is not as fast as specialized prime proof software can do
modular exponentiation. Jean Penne's LLR software can do faster
 
Of course, the goal of GMP is not to be faster than specialized prime proof software, and nobody will claim that it's the leading tool to search for huge primes.
 
My contribution to the library is simply giving a more precise answer, and more quickly, for a class of numbers, if compared to the previous implementation of the same function in the library.
Without adding new large functions.
 
Ĝis, m

PS: You mention Jean Penne's LLR. That software, on the number “1155*2^5745+1” uses “Proth prime test” with base “a = 29”. And I fully agree with Jean Penne on the choice of the base :-)