Modular multiplication of large numbers in C ++

Question

I have three integers A, B (less than 10 ^ 12) and C (less than 10 ^ 15). I want to calculate (A * B)% C. I know that

(A * B) % C = ((A % C) * (B % C)) % C 

but let's say if A = B = 10 ^ 11 , then the above expression will cause an integer overflow. Is there any simple solution for the above case or do I need to use fast multiplication algorithms.

If I need to use the fast multiplication algorithm, then which algorithm should I use.

EDIT: I tried the problem above in C ++ (which does not cause overflow, I don’t know why), but isn’t the answer supposed to be zero ?

Thanks in advance.

Answer 1

Given your formula and the following variation:

 (A + B) mod C = ((A mod C) + (B mod C)) mod C 

You can use the divide and conquer approach to develop an algorithm that is simple and fast:

 #include <iostream> long bigMod(long a, long b, long c) { if (a == 0 || b == 0) { return 0; } if (a == 1) { return b; } if (b == 1) { return a; } // Returns: (a * b/2) mod c long a2 = bigMod(a, b / 2, c); // Even factor if ((b & 1) == 0) { // [((a * b/2) mod c) + ((a * b/2) mod c)] mod c return (a2 + a2) % c; } else { // Odd exponent // [(a mod c) + ((a * b/2) mod c) + ((a * b/2) mod c)] mod c return ((a % c) + (a2 + a2)) % c; } } int main() { // Use the min(a, b) as the second parameter // This prints: 27 std::cout << bigMod(64545, 58971, 144) << std::endl; return 0; } 

What is O(log N)

Answer 2

You can solve this using the Schrage method. This allows you to multiply the two signed numbers a and z as with a specific module m without generating an intermediate number greater than this.

This is based on approximate factorization of the module m ,

 m = aq + r 

i.e.

 q = [m / a] 

and

 r = m mod a 

where [] denotes the integer part. If r < q and 0 < z < m − 1 , then both a(z mod q) and r[z / q] lie in the range 0,...,m − 1 and

 az mod m = a(z mod q) − r[z / q] 

If this is negative, add m .

[This method is often used in linear congruent random number generators].

Answer 3

UPDATED: Fixed bug when high bit a % c . (hat tip: Kevin Hopps)

If you are looking for simple fast, you can use the following:

 typedef unsigned long long u64; u64 multiplyModulo(u64 a, u64 b, u64 c) { u64 result = 0; a %= c; b %= c; while(b) { if(b & 0x1) { result += a; result %= c; } b >>= 1; if(a < c - a) { a <<= 1; } else { a -= (c - a); } } return result; } 

Answer 4

Sorry, the godel9 algorithm will produce an incorrect result when the variable "a" contains a high bit value. This is because "a <= 1" is losing information. Here is a fixed algorithm that works for any integer type, signed or unsigned.

 template <typename IntType> IntType add(IntType a, IntType b, IntType c) { assert(c > 0 && 0 <= a && a < c && 0 <= b && b < c); IntType room = (c - 1) - a; if (b <= room) a += b; else a = b - room - 1; return a; } template <typename IntType> IntType mod(IntType a, IntType c) { assert(c > 0); IntType q = a / c; // q may be negative a -= q * c; // now -c < a && a < c if (a < 0) a += c; return a; } template <typename IntType> IntType multiplyModulo(IntType a, IntType b, IntType c) { IntType result = 0; a = mod(a, c); b = mod(b, c); if (b > a) std::swap(a, b); while (b) { if (b & 0x1) result = add(result, a, c); a = add(a, a, c); b >>= 1; } return result; } 

Answer 5

In this case, A and B are 40-bit numbers, and C is a 50-bit number, which is not a problem in 64-bit mode, if you have built-in code or you can write assembly code to use 64-bit 64- bit multiplication, which gives a result of 128 bits (the product is actually 80 bits), after which you divide the 128-bit dividend into a 50-bit divider to create a 50-bit remainder (modulo).

Depending on the processor, it may be faster to implement division by a 50-bit constant by multiplying by 81 bits (or less) of the constant. Again, assuming a 64-bit processor, it will take 4 multiplications and some additions, followed by a shift of the upper bits of the 4 multiplied product to get the quotient. Then, to obtain a 50-bit remainder, time multiplication of 50 bits modulo and subtraction (from an 80-bit product) is used.