Modulo of multiplication of large numbers [duplicate]

Question

Yes I know the question may seem naive but I have searched a lot on google and this site as well but could not find a satisfying answer to it. I simply want to calculate (A*B)%MOD, provided a is long long and so are b and MOD. Suppose MOD is larger than both A and B such that A%MOD = A and B%MOD = B but A*B is larger than 64 bits. How can correct value of (A*B)%MOD be calculated?

Answer 1

Basic idea here is to first define a non-overflowing addmod function which takes advantage of negative numbers in its arithmetic. Then define timesmod in terms of it also using bit operations. The time complexity is O(N) where N is the number of bits used (64 in this case).

#include <iostream>
using namespace std;

typedef long long BigInt; // must be signed, to detect overflow

BigInt A = 0x7fffffffffffff01;
BigInt B = 0x7fffffffffffff02;
BigInt M = 0x7fffffffffffff03;

// For simplicity it is assumed x, y, and m are all positive.
BigInt addmod( BigInt x, BigInt y, BigInt m )
{
  x %= m;
  y %= m;
  BigInt sum = x-m+y; // -m <= sum < m-1
  return sum < 0 ? sum + m : sum;
}

BigInt timesmod( BigInt x, BigInt y, BigInt m )
{
  x %= m;
  y %= m;
  BigInt a = x < y ? x : y; // min
  BigInt b = x < y ? y : x; // max
  BigInt product = 0;
  for (; a != 0; a >>= 1, b = addmod(b,b,m) )
    if (a&1) product = addmod(product,b,m);
  return product;
}

int main()
{
  cout << "A = " << A << endl;
  cout << "B = " << B << endl;
  cout << "M = " << M << endl;
  cout << "A*B mod M = " << timesmod(A,B,M) << endl;
  return 0;
}

Output:

A = 9223372036854775553
B = 9223372036854775554
M = 9223372036854775555
A*B mod M = 2

This is easily confirmed since A=-2 and B=-1 mod M.

Note: this code is not optimized.