0
$\begingroup$

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.

  • 0
    I'm using int64's -- unfortunately I had a very difficult time getting GMP to work2012-04-11

1 Answers 1

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).

  • 0
    mention) 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