Modular arithmetic is a branch of number theory that deals with operations on numbers that have a remainder when divided by a modulus. In C++, performing modular arithmetic involves using the % (modulo) operator and sometimes ensuring that the result remains within a specified range.

Table of Contents

1. Why we need Modular Multiplication?
2. Properties of Modular Arithmetic
3. Approach to Avoid Overflow for Large Mod Values
4. Time and Space Complexity:

Why we need Modular Multiplication ?

In computer programming, integers have a limited range determined by the number of bits used to represent them. When performing arithmetic operations, such as multiplication, there is a risk of integer overflow if the result exceeds the maximum representable value. Overflow occurs when the result is larger than the maximum value that can be stored in the data type.

Example: Consider the case of multiplying two large integers:

int a = 1000000;
int b = 1000000;
int result = a * b;  // Overflow may occur here

In this case, the result of 1000000 × 1000000 is 1 trillion, which exceeds the maximum representable value for a 32-bit integer, leading to overflow. To deal with this problem we take the help of modular arithmetics.

Properties of Modular Arithmetic

The following are some basic properties of modular arithmetic:

1. Addition in Modular Arithmetic: When adding two numbers and taking the result modulo m, you can take the modulo of each number separately and then add them.

        (a + b) mod m = (a mod m + b mod m) mod m
   

2. Subtraction in Modular Arithmetic:Similarly, when subtracting two numbers and taking the result modulo m, you can take the modulo of each number separately and then subtract.

        (a - b) mod m = (a mod m - b mod m) mod m
   

3. Multiplication in Modular Arithmetic:The product of two numbers taken modulo m is equivalent to the product of their individual remainders when divided by m.

        (a * b) mod m = (a mod m * b mod m) mod m
   

Let's consider an example of multiplication in modular arithmetic.

Example 1:

Suppose we want to calculate ( (123 * 456) mod 7 ).

Using the rule for multiplication in modular arithmetic:

      (a * b) mod m = ( (a mod m) * (b mod m) ) mod m 

We can break down the multiplication and then take the modulo:

     (123 * 456) mod 7 = ((123 mod 7) * (456 mod 7)) mod 7

Calculating the individual remainders:

                    (123 mod 7) = 6 
                    (456 mod 7) = 3 

Now, multiply the remainders:

            (6 * 3) mod 7 = 18 mod 7 = 4

Therefore, (123 * 456) mod 7 = 4 which can be verified as 123 * 456 = 56088 % 7 = 4 .

In C++, you can implement this as follows:

#include <iostream>

int modMultiply(int a, int b, int mod) {
    return ((a % mod) * (b % mod)) % mod;
}

int main() {
    int a = 123;
    int b = 456;
    int mod = 7;

    int result = modMultiply(a, b, mod);

    std::cout << "(" << a << " * " << b << ") % " << mod << " = " << result << std::endl;

    return 0;
}

Compilation & Execution :

 g++ filename.cpp -o filename.exe
 ./filename.exe

This program uses the modMultiply function to perform the modular multiplication and prints the result. In this specific example, it would output:

(123 * 456) % 7 = 4

Example 2 :

Suppose we want to calculate ( (a * b) mod m ) where ( a = 27178 ), ( b = 1219721 ), and ( m = 10000 ).

Using modular multiplication:

#include <iostream>
using namespace std;
int modMultiply(int a, int b, int mod) {
    return ((a % mod) * (b % mod)) % mod;
}
int main() {

    int result = modMultiply(27178, 1219721, 10000);
    cout<<result<<endl;

    return 0;
}

Output :

7338

In this case, the modular multiplication ensures that the intermediate products and the final result are within the specified modulus, preventing overflow.

When the Current Approach Will Fail:

The current approach of using the % operator may fail when dealing with negative numbers. The % operator in C++ may produce negative remainders for negative numbers, which can affect the correctness of modular arithmetic. The modified approach ensures that both operands are non-negative before the multiplication.

Also of we take a = 10^5 and b = 10^5 and mod = 10^7 it will not work as the a % mod will still be 10^5 and same goes for b. The multiplication will still exceed the limits.

Approach to Avoid Overflow for Large Mod Values:

When the modulus is close to the maximum representable value for the data type (e.g., ~ (10^7) for a 32-bit integer), it's crucial to avoid overflow while performing modular multiplication. Please refer to the procedure given below :

int modMultiply(int a, int b, int mod) {
    a = (a % mod + mod) % mod;  // Ensure a is non-negative
    b = (b % mod + mod) % mod;  // Ensure b is non-negative
    int result = 0;

    while (b > 0) {
        if (b % 2 == 1) {
            result = (result + a) % mod;
        }
        a = (2 * a) % mod;
        b /= 2;
    }

    return result;
}

The solution has two parts :

1. Handling Negative Numbers: Adding the mod term to given number.
   The a = (a % mod + mod) % mod and b = (b % mod + mod) % mod lines ensure that a and b are non-negative. This step is essential to prevent negative remainders from affecting the modular arithmetic.

2. . Modular Exponentiation: The loop efficiently calculates the rsult without causing overflow. It uses the binary exponentiation technique, which reduces the number of multiplications needed.

Approach:

#include <iostream>
using namespace std;
int modMultiply(int a, int b, int mod) {
    a = (a % mod + mod) % mod;  // Ensure a is non-negative
    b = (b % mod + mod) % mod;  // Ensure b is non-negative
    int result = 0;

    while (b > 0) {
        if (b % 2 == 1) {
            result = (result + a) % mod;
        }
        a = (2 * a) % mod;
        b /= 2;
    }

    return result;
}
int main() {

    int result = modMultiply(100000 , 100000 , 10000000);
    cout<<result<<endl;

    return 0;
}

Output :

0

Example 2:
The multiplication of a = 123456 , b = 56789 and mod = 10000000.

#include <iostream>
using namespace std;
int modMultiply(int a, int b, int mod) {
    a = (a % mod + mod) % mod;  // Ensure a is non-negative
    b = (b % mod + mod) % mod;  // Ensure b is non-negative
    int result = 0;

    while (b > 0) {
        if (b % 2 == 1) {
            result = (result + a) % mod;
        }
        a = (2 * a) % mod;
        b /= 2;
    }

    return result;
}
int main() {

    int result = modMultiply(123456 , 56789 , 10000000);
    cout<<result<<endl;

    return 0;
}

Output :

942784 

This approach uses a loop to perform the multiplication without causing overflow. It ensures that intermediate results and the final result stay within the specified modulus.

Time and Space Complexity:

The time complexity and space complexity are as follows :

Basic Approach:

• Time Complexity: O(1)
• Space Complexity: O(1)

Modified Approach:

• Time Complexity: O(log b) (where b is the exponent in modular exponentiation)
• Space Complexity: O(1)

The modified approach introduces a loop for modular exponentiation, contributing to a time complexity proportional to the logarithm of the exponent. Both approaches have constant space complexity as they don't require additional memory allocation based on the input size.

With this article at OpenGenus.org, you must have the complete idea of Modular Multiplication in C++.