Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

1 Answer

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

share|improve this answer
    
+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
    
Can anyone provide an example, please? –  WhatsInAName Apr 11 '12 at 19:24
    
Suppose 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 –  Charles Apr 11 '12 at 19:34
    
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. –  Charles Apr 11 '12 at 19:37
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.