question about result from mpz_ModPow

[hermann at stamm-wilbrandt.de]

On 2026-08-20 18:21, Marco Bodrato wrote:
> 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.
> 
You are right, what I remembered incorrectly was Generalized Pepin Test
for Proth numbers, if 3 does not devide k then base 3 does test 
primality:
https://arxiv.org/pdf/0812.2596#page=3
"Deterministic Primality Proving on Proth Numbers"

On your step
- search a suitable base using mpz_kronecker_ui;

If it will not process potential bases increasingly, a test "k%3 != 0"
likely speeds up that step.

Regards,

Hermann.