Karim Belabas on Tue, 13 Dec 2005 19:44:02 +0100


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: modular exponentiation


* John Jones [2005-12-13 18:00]:
> > (14:15) gp >  k = 10000000000; N = 123456;
> > (14:15) gp >  Mod(10,N)^k
> > ***   Warning: multiword exponent in Fl_pow.
[...]
> The way it is, it looks like gp is warning the user that the answer 
> might be wrong because it cannot handle an exponent so large.  I think 
> that is a really bad message to send to the users.  If the warning is 
> there to say "this computation can probably be done more efficiently by 
> ...", then that is what it should say.

OK, I've changed it to:

  (19:32) gp >  Mod(10,123456)^10000000000
  ***   Warning: large exponent in Mod(a,N)^n: reduce n mod phi(N).

> Personally, I don't think gp should give such warnings at all.  In this 
> case, it is ironic that gp gives a warning since gp could do everything 
> itself: it could test the size of the modulus and the exponent to decide 
> if the exponent should be reduced modulo phi(N). But it doesn't do that, 
> because it would be a waste of time?

I'd rather warn the user that he's doing something stupid, than to silently
spend twice as much time (or worse!) for these (trivial) computations.

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]