|John Jones on Tue, 13 Dec 2005 17:58:53 +0100|
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
|Re: modular exponentiation|
Karim Belabas wrote:
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.* Alain SMEJKAL [2005-12-13 12:45]:----- Original Message ----- From: "Jeroen Demeyer" <J.Demeyer@UGent.be> To: "Henk Karssenberg" <email@example.com> Cc: <firstname.lastname@example.org> Sent: Friday, November 25, 2005 1:54 PM Subject: Re: modular exponentiationHenk 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.
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?