Karim Belabas wrote:
* 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.
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.
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?
John Jones
|