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
-
0Which sizes are we talking about here? What kind of arithmetic do you have access to? – 2012-04-11
-
0Anything doable in C++ – 2012-04-11
-
0I 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: http://gmplib.org/ – 2012-04-11
-
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).
-
0+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. – 2012-04-11
-
0Can anyone provide an example, please? – 2012-04-11
-
0Suppose you can only store numbers up to 3. You can solve 5 * 10 by writing the numbers in base 4 (11 times 22) and finding each of the cross-products: 1*2 shifted by 0, 1*2 shifted by 1, 1*2 shifted by 1, and 1*2 shifted by 2. That gives 2 + 20 + 20 + 200 (where the extra zeros denote the position of the digit -- you're not really storing more than just the 2s). The last digit will be 2 since it's the only digit in that position. The next digit has a problem: 2+2 is too large and will overflow. So let the calculation wrap around: this should require doing nothing extra in C++ (which you – 2012-04-11
-
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