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.
Addressing a*a mod m overflow problem where m is large
0
$\begingroup$
modular-arithmetic
-
0I'm using int64's -- unfortunately I had a very difficult time getting GMP to work – 2012-04-11
1 Answers
2
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).
-
0mention) but can be done as, for example, 2 - (4 - 2) = 0 with$a$carry. Now you have the carry of 1 plus the 2, which is small enough to carry out directly. So the final answer is 302 or 50 in base 10. – 2012-04-11