Re: modular exponentiation

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

* Alain SMEJKAL [2005-12-14 00:26]:
> I did not look at Pari code but I hope that this conditional warning test is
> done at no extra cost,
> else it would be a luxury only for advising user under rare condition.

No extra cost, see below.

> The warning strategy remains unclear, is it limited to Eulerphi()
> practicable calculation?
> Seeing these trivial and all unneficients cases there is only one warning :
> 
> ? Mod(10,1000)^1000000000
> %958 = Mod(0, 1000)
> 
> ? Mod(10,1000)^10000000000
> 
>   ***   Warning: multiword exponent in Fl_pow.
> %959 = Mod(0, 1000)
> 
> ? Mod(10,10000000000)^10000000000000000000
> %960 = Mod(0, 10000000000)

The exact strategy is as follows. If the modulus is word-sized (say <
2^32), the powering is done directly with 'unsigned longs' (using Fl_pow() ),
not with all the (expensive) overhead of multiprecision.

BUT if the exponent happens not to be word-sized, we cannot use
Fl_pow(), or any routine for powering modulo C longs with multiprecision
exponents. In fact no such routine exist because it just signals a major
inefficiency ( eulerphi() is always trivial to compute in these cases ).

This test is just here to avoid an error in a conversion routine from
multiprecision integers. It occurs iff 

  modulus    <  2^32
  |exponent| >= 2^32

If the warning is a nuisance, I can disable it unless 'debuglevel' is
positive.

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]