Re: question on PARI/GP t_INTMOD exponentiation optimization for multiple similar size big exponents with same base

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Mon, Feb 16, 2026 at 03:49:51PM +0100, hermann@stamm-wilbrandt.de wrote:
> It all started with me trying to play with J. Brillhart, D. H. Lehmer and J.
> L. Selfridge 1975 paper theorem 1:
> https://t5k.org/prove/prove3_1.html
> 
> While theorem 1 does not require the same a_i for different prime divisors
> p_i of N-1 to be used, I learned that a primitive root allows to be used for
> all prime divisors of N-1.
> 
> I played with prime Euclid numbers https://oeis.org/A014545, for which the
> factorization of N-1 is trivial. A simple sequential replacement of
> znprimroot() is much faster because znprimroot() has to factor N-1 first,
> and prime 457th Euclid number is smallest example where GP has to spend much
> time on the factorization:

Well, the problem is not factoring,

? P=prime(457)#+1;
? factor(eulerphi(P));
? ##
  ***   last result: cpu time 85 ms, real time 85 ms.

This is strange since
o=factor(P-1);for(i=2,P-1,print(i," ");if(znorder(Mod(i,P),o)==P-1, break()))
is much faster than znprimroot(P).

> It seems that GP does optimize muliple modular exponentiation with same base
> better than how I tried to do it.

It does not optimize in this case.
What happens is that the binary powering code depend on
(e being the exponent) on logint(e,2) and hamming(e)
So if you replace an exponent by another exponent that is not
significantly smaller, this does not improve the running time.

In C there are multiple modular exponentiation code:
Fp_pow_init/Fp_pow_table
that you can use in GP using install()

install(Fp_pow_init,mGGLG)
install(Fp_pow_table,GGG)

To compute x^n mod p for n in N, set nmax to max N, k a small integer and initialize:
R = Fp_pow_init(x, nmax, k, p);

Then you can compute x^n mod p with
Fp_pow_table(R, n, p)

Cheers,
Bill.