Re: Why is "lift(Mod(qnr, n)^(n\4))" 16% slower than C libgmp "powm(r, qnr, n/4, n)" ?

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

On Fri, Jun 23, 2023 at 12:15:39PM +0200, hermann@stamm-wilbrandt.de wrote:
> My Linux gp-2.15 runs with GMP kernel:
> 
> So why is "lift(Mod(qnr, n)^(n\4))" 16% slower than C libgmp "powm(r, qnr,
> n/4, n)" on same Intel CPU (running at boost frequency with single running
> process both times)?

The short answer is that the GNU MP library does not provide a function mpn_powm
that PARI could use. mpz_powm use a lot of internal mpn functions for fast modular
reduction which are very efficient but not public.

Now, I could add a wrapper for mpz_powm for large entries but 16% slower is not
that bad and we need fast modular reduction in more general setting.

Cheers,
Bill.