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

[Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>]

* Bill Allombert [2014-11-13 11:30]:
> 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

Of course, to optimize this precise expression, you might as well use
the formula

  [a,b;0,c]^n = [a^n, b*(a^n-c^n)/(a-c); 0, c^n] if a != c
                [a^n, n*b*a^(n-1); 0, a^n]       if a = c

then simplify the resulting triple sum over a,b,c. For example, modulo n > 0,
your sum is obviously [0,0;0,0]  :-)

Cheers,

    K.B.
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite de Bordeaux         Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux1.fr/~kbelabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux1.fr/  [PARI/GP]
`