Re: (Modular ^) vs. (^ then mod)

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

On Thu, Nov 13, 2014 at 10:50:28AM +0100, Pedro Fortuny Ayuso wrote:
> Hi,
> 
> I am doing quite a few (millions) of modular powers and
> additions like shown below. Is it natural that the Mod
> operation takes longer than the operation without Mod?
> It may be as simple as "yes, pretty normal" but somehow
> I expected the operation with the Mods to be faster,
> but I may well be quite wrong.

No it is not normal, and it does not happen on my machine.
What version of GP are you using (what \v says) ?

With PARI/GP 2.7.2 (64bit) I get:
? s=[0,0;0,0];for(a=0,n-1, for(b=0, n-1, for(c=0, n-1, s=s+[a,b;0,c]^n)))
? ##
  ***   last result computed in 5,421 ms.
? s=[0,0;0,0]; for(a=0,n-1, for(b=0, n-1, for(c=0, n-1, s=s+[Mod(a,n),Mod(b,n);0,Mod(c,n)]^n)))
? ##
  ***   last result computed in 5,301 ms.

If you really need to optimize this, you can use the internal FpM_powu
libpari function for powering of matrices over Z/nZ as follow

install(FpM_powu,GLG)
n=120;
s=Mod([0,0;0,0],n);for(a=0,n-1, for(b=0, n-1, for(c=0, n-1, s=s+FpM_powu([a,b;0,c],n,n))))

which is about twice faster.

(ideally, GP should call FpM_powu by itself, but it is not implemented yet).

Cheers,
Bill.