# Addressing a*a mod m overflow problem where m is large

is there another way to calculate a*a mod m mathematically? m is larger than a so (a%m)*(a%m) %m doesn't do anything, but a*a is large enough to overflow.

-
Which sizes are we talking about here? What kind of arithmetic do you have access to? – Henning Makholm Apr 11 '12 at 19:14
Anything doable in C++ – WhatsInAName Apr 11 '12 at 19:25
I assume that you're already using long rather than int in your code? If so, then you should use the GMP bignum types for arbitrary precision arithmetic: gmplib.org – Chris Taylor Apr 11 '12 at 19:41
I'm using int64's -- unfortunately I had a very difficult time getting GMP to work – WhatsInAName Apr 11 '12 at 19:46

Break a down into base-b digits where (b-1)^2 is small enough that it does not overflow. For example, use base-$2^{16}$ and 32-bit words or base $2^{32}$ and 64-bit words. Then multiply these words by the usual algorithm (or, if you like, a faster algorithm like Karatsuba).
+1 I was about to suggest writing $a$ in base-$b$ digits, where $b$ is such $b*m$ doesn't overflow. You beat me to it with a variant of the same idea. – Jyrki Lahtonen Apr 11 '12 at 19:21