Re: modular exponentiation

["Alain SMEJKAL" <a.smejkal@free.fr>]

From: "Karim Belabas" <belabas@math.u-bordeaux1.fr>
To: <pari-users@list.cr.yp.to>
Sent: Tuesday, December 13, 2005 7:36 PM
Subject: Re: modular exponentiation


> > 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.


I agree that having an exponent larger than modulus is definitly not optimal
but not wrong and never failed on INTMOD.
In fact I got this in a "lazy" algorithm that do not take care of size of
exponent vs. modulus.
Since it is managed to happen rarely I chose to not testing that to get a
globally faster calculation.

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.

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)


Regards,

Alain