Karim Belabas on Tue, 13 Dec 2005 14:37:51 +0100

 Re: modular exponentiation

```* Alain SMEJKAL [2005-12-13 12:45]:
> ----- Original Message -----
> From: "Jeroen Demeyer" <J.Demeyer@UGent.be>
> Cc: <pari-users@list.cr.yp.to>
> Sent: Friday, November 25, 2005 1:54 PM
> Subject: Re: modular exponentiation
>
>
> > > Dear M.,
> > >
> > > In PARI I try to calculate k = Mod(6682632708227277^28345232917,
> > > 72057594037927889) but this gives an overflow. Is there any option to
> > > calculate Mod(a^m,n) or a^m % n with huge numbers ?
> > >
> > > Thank you & kind regards.
> >
> > Henk,
> >
> > You should do k = Mod(a,n)^m.
> > This works because Mod(a,n) creates an object in Z/nZ.
> >
>
> Dear List,
>
> This method is very efficient but, is there a way to avoid spurious warning
> occuring on large exponents ?
> (Unsuccessfully tried \g debug preference)
>
> ? Mod(10,123456)^10000000000
>
>   ***   Warning: multiword exponent in Fl_pow.

It is not spurious, it is telling you that you're doing a more difficult
computation than you should.

(14:15) gp >  k = 10000000000; N = 123456;
(14:15) gp >  Mod(10,N)^k
***   Warning: multiword exponent in Fl_pow.
%2 = Mod(50368, 123456)
(14:15) gp >  l = k % eulerphi(N)
%3 = 2560
(14:15) gp >  Mod(10,N)^l
%4 = Mod(50368, 123456)

And in fact:

(14:15) gp > for(i=1,10^5, Mod(10,N)^k)
time = 1,446 ms.
(14:15) gp > for(i=1,10^5, Mod(10,N)^l)
time = 148 ms.

Of course, the powering function could compute Euler's phi by itself, since
it's quite easy for small inputs:

(14:18) gp > for(i=1,10^5, eulerphi(N))
time = 119 ms.

But that would still slow down the powering itself almost by a factor 2
for no good reason. So we assume that the user knows what he's doing,
and assume that powering an INTMOD with an exponent much larger than
the modulus must be a bug.

Cheers,

Karim.
--
Karim Belabas                  Tel: (+33) (0)5 40 00 26 17
Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux.fr/~belabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]

```