Re: modular exponentiation

["Karim Belabas" <belabas@math.u-bordeaux1.fr>]

* Alain SMEJKAL [2005-12-13 12:45]:
> ----- Original Message ----- 
> From: "Jeroen Demeyer" <J.Demeyer@UGent.be>
> To: "Henk Karssenberg" <henk.karssenberg@hu.nl>
> Cc: <pari-users@list.cr.yp.to>
> Sent: Friday, November 25, 2005 1:54 PM
> Subject: Re: modular exponentiation
> 
> 
> > Henk Karssenberg wrote:
> > > 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]