Computing A^x (mod n)

[Décio Luiz Gazzoni Filho]

On Saturday 02 October 2004 13:57, Philip Lee wrote:
> I'm just wondering the algorithm behind mpz_powm().  It can't be doing
> the calculation (mod n) inside whatever loop it's running, because if
> I take a a 572-bit number and raise it to a 576-bit number modulo a
> 576-bit number, the program will terminate. I'm guessing it is doing
> the exponential junk first and then just taking the modulus right?
> Because this would cause an extreme overflow in such a case as mine.
> (As you can tell, I'm doing some RSA stuff ).
>
> So my question is, "if the mpz_powm() function isn't doing a running
> calculation (mod n ), why is it not?" As I said, this would cause
> overflows which would be prevented if it was instead doing a running
> calculation (mod n). Anyways, just wondering.

mpz_powm() does reduce modulo n after each multiplication/squaring. I speak 
from experience, but it's also mentioned in the manual (though not 
explicitly):

http://www.swox.com/gmp/manual/Modular-Powering-Algorithm.html

If your program is crashing, it's because there's something wrong with your 
code.

Décio

PS: it's almost insulting to suggest that the GMP guys would have implemented 
modular exponentiation without reduction after each step. Better put your 
asbestos suit on.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 190 bytes
Desc: not available
Url : /list-archives/gmp-discuss/attachments/20041002/84093647/attachment.bin