9.2 Modular Inverses, Fast Exponentiation, and the Chinese Remainder Theorem

The gears on the observation tower rotate at different intervals. Ah Hua needs to determine when they will realign and which modular operations allow reverse computation.

Modular arithmetic preserves addition and multiplication, but not arbitrary division. Whether "division by a" is possible depends on whether a has a multiplicative inverse modulo the current base.

Congruence Allows Addition, Subtraction, and Multiplication

If:

a ≡ b (mod m)
c ≡ d (mod m)

then:

a + c ≡ b + d (mod m)
a - c ≡ b - d (mod m)
a × c ≡ b × d (mod m)

This means we can perform arithmetic operations on remainders throughout calculations, avoiding the growth of intermediate values. However, in fixed-width integers, multiplying first may still cause overflow. For very large modular multiplications, arbitrary-precision integers or specialized algorithms are required.

Canceling Factors Conditionally

From:

ac ≡ bc (mod m)

one cannot always conclude a≡b.

Example:

2·1 ≡ 2·3 (mod 4)

Both sides leave a remainder of 2, but 1≢3 (mod 4).

If gcd(c,m)=1 has a multiplicative inverse modulo m, then c can be safely canceled.

Modular Inverse

a the modular inverse of m modulo a⁻¹ satisfies:

a · a⁻¹ ≡ 1 (mod m)

The inverse exists if and only if:

gcd(a, m) = 1

By Bézout's identity: if ax+my=1, then:

a · x ≡ 1 (mod m)

Thus, x mod m is the modular inverse.

Example: Find the inverse of 3 modulo 11:

4 · 3 - 1 · 11 = 1

Therefore, 3⁻¹≡4 (mod 11).

Linear congruence:

a · x ≡ b (mod m)

has a solution if and only if gcd(a,m)|b. If the gcd is 1, the solution is unique modulo m; otherwise, there may be no solution or multiple solution classes.

Fast Modular Exponentiation

Computing a^e mod m should not involve generating a huge a^e. Instead, the square-and-multiply algorithm expands the exponent in binary:

result = 1
base = a mod m

while e > 0:
  if e is odd:
    result = result · base mod m
  base = base · base mod m
  e = floor(e / 2)

The number of modular multiplications is O(log e). A secure implementation must also consider:

• Whether the exponent allows negative values;
• Whether the modulus is positive;
• Whether multiplication operations may overflow;
• Whether cryptographic use cases require constant-time execution to avoid branching and memory access leaks based on the exponent bits.

Teaching code should not be used directly for key operations.

Fermat and Euler Theorems

If p is prime and p∤a:

a^(p-1) ≡ 1 (mod p)

Euler's theorem generalizes this to the case where gcd(a,n)=1:

a^φ(n) ≡ 1 (mod n)

φ(n) is the count of integers between 1 and n that are coprime to n.

If p is prime:

φ(p) = p - 1

If p,q are distinct primes:

φ(pq) = (p - 1)(q - 1)

The condition gcd(a,n)=1 cannot be omitted. Fermat's little theorem describes a necessary property of primes, but it is not a sufficient criterion: composite numbers can also exhibit the same behavior for certain or all coprime bases.

Chinese Remainder Theorem

If the moduli m₁,...,m_k are pairwise coprime, then the system of congruences:

x≡a₁ (mod m₁)
...
x≡a_k (mod m_k)

has a unique solution modulo:

M=m₁...m_k

We construct the solution as:

M_i = M / m_i
y_i = M_i⁻¹ mod m_i
x = Σ a_i * M_i * y_i mod M

Since M_i y_i is 1 modulo m_i and 0 modulo all other moduli, it acts like a basis vector selecting its corresponding component.

Example:

x≡2 (mod 3)
x≡3 (mod 5)
x≡2 (mod 7)

Solves to:

x≡23 (mod 105)

Non-Coprime Moduli

Two congruences:

x ≡ a (mod m)
x ≡ b (mod n)

have a common solution if and only if:

a ≡ b (mod gcd(m, n))

If a solution exists, it is unique modulo lcm(m,n). The standard "pairwise coprime" version is merely a simpler special case.

Engineering Applications and Boundaries

• Phase alignment in multi-cycle scheduling;
• Breaking large integer operations into modular components using coprime moduli and reconstructing the result;
• CRT acceleration in RSA private-key computations;
• Residue number systems and error-correcting codes.

CRT decomposition does not automatically ensure security. Cryptographic implementations must also defend against fault injection, side-channel attacks, and error validation, using audited libraries.

Completion Checklist

1. Evaluate 17⁻¹ mod 43;
2. Resolve 14x≡8 (mod 30);
3. Manually compute 7^181 mod 13;
4. Solve a system of three pairwise coprime congruences using the Chinese Remainder Theorem (CRT);
5. Construct a system of congruences that are not coprime and have no solution;
6. Explain why modular exponentiation may still overflow at fixed-width integer multiplication even when using modular arithmetic.

References

• MIT Mathematics for Computer Science