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 01:13:11PM +0200, Bill Allombert wrote:
> 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.

Could you compare

p=(2^95369 + 1)/3; Mod(2,p)^((p-1)/5)
with mpz_powm and PARI ?

Cheers,
Bill.