Computing A^x (mod n)

Philip Lee rocketman768 at
Sat Oct 2 18:57:14 CEST 2004

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.

More information about the gmp-discuss mailing list