Introduction

Modular multiplication asks for (a * b) % mod, but that expression becomes dangerous when a * b overflows before the modulus is applied. For small integers this is fine, but for large values common in number theory and cryptography, overflow can silently produce the wrong answer.

The practical goal is to compute the modular product without ever forming an intermediate value that exceeds the available integer range.

Why the Naive Formula Can Break

This looks correct:

long long result = (a * b) % mod;

But if a and b are large enough, a * b may overflow long long before % mod runs. At that point the computation is already invalid.

For example, values near the 64-bit limit can overflow even if the final modular answer would fit perfectly well.

Best Case: Use a Wider Integer Type

On compilers that support __int128, the easiest solution in C++ is often to widen the multiplication:

1#include <iostream>
2
3long long mul_mod(long long a, long long b, long long mod) {
4    return static_cast<long long>((__int128)a * b % mod);
5}
6
7int main() {
8    long long a = 1000000000000LL;
9    long long b = 1000000000000LL;
10    long long mod = 1000000007LL;
11
12    std::cout << mul_mod(a, b, mod) << '\n';
13}

This is simple and fast, but it relies on compiler support for a wider intermediate type.

Portable Approach: Repeated Doubling

If you cannot rely on __int128, use the repeated-doubling method, which is analogous to binary exponentiation. Instead of multiplying in one step, it builds the result through safe additions under the modulus.

1#include <iostream>
2
3long long mul_mod(long long a, long long b, long long mod) {
4    long long result = 0;
5    a %= mod;
6
7    while (b > 0) {
8        if (b & 1) {
9            result = (result + a) % mod;
10        }
11        a = (a + a) % mod;
12        b >>= 1;
13    }
14
15    return result;
16}
17
18int main() {
19    long long a = 1000000000000LL;
20    long long b = 1000000000000LL;
21    long long mod = 1000000007LL;
22
23    std::cout << mul_mod(a, b, mod) << '\n';
24}

This avoids direct large multiplication and works in environments where a wider integer type is not available.

How the Binary Method Works

The idea is to decompose b into binary. Each set bit says that the current value of a should be added into the result. After each step:

• if the lowest bit of b is 1, add a into result
• double a modulo mod
• shift b right by one bit

This is the same structural idea used in fast exponentiation, except addition replaces multiplication.

When This Matters

Safe modular multiplication matters in code involving:

• modular exponentiation
• primality tests
• cryptographic arithmetic
• competitive programming with large constraints

A modular exponentiation routine, for example, often calls modular multiplication many times:

1long long pow_mod(long long base, long long exp, long long mod) {
2    long long result = 1 % mod;
3    base %= mod;
4
5    while (exp > 0) {
6        if (exp & 1) {
7            result = mul_mod(result, base, mod);
8        }
9        base = mul_mod(base, base, mod);
10        exp >>= 1;
11    }
12
13    return result;
14}

If mul_mod is wrong because of overflow, the whole exponentiation result becomes unreliable.

Signed Versus Unsigned Concerns

Be careful with negative values and signed overflow. In many modular arithmetic problems, inputs are normalized first:

a = ((a % mod) + mod) % mod;
b = ((b % mod) + mod) % mod;

This ensures values are in the expected range before repeated doubling begins.

Also remember that signed integer overflow is undefined behavior in C++. That is another reason why "it usually works on my machine" is not a good enough test for naive multiplication near the numeric limits.

Common Pitfalls

The biggest pitfall is assuming % mod protects you from overflow in a * b. It does not, because overflow happens first.

Another issue is writing a safe multiplication routine and then forgetting to use it inside modular exponentiation or primality code, where the same overflow risk still exists.

Developers also sometimes overlook compiler assumptions. A solution based on __int128 is excellent when available, but it is not universally portable.

Finally, if the modulus fits in 32 bits and the operands are already reduced, a simpler method may be enough. Choose the implementation based on the actual numeric range instead of using the slowest possible version by default.

Summary

• '(a * b) % mod can overflow before the modulus is applied.'
• Use a wider intermediate type such as __int128 when available.
• For portability, use repeated doubling to build the product safely under the modulus.
• Safe modular multiplication is essential for modular exponentiation and other large-number algorithms.
• Always reason about the operand range first; overflow safety is part of correctness, not an optimization detail.