Mathematics.

computational number theory

Modular Exponentiation

Discrete Mathematics25 minDifficulty4 out of 10

You should know: number representations

Overview

Modular exponentiation computes bᵉ mod m — a base raised to an exponent, reduced modulo m — without ever forming the (potentially astronomically large) full number bᵉ. Naively multiplying b by itself e times and reducing mod m at the end would require storing a number with roughly e·log(b) digits, which is completely inferactable for the exponents used in real cryptography (hundreds or thousands of bits, as in RSA). The key trick, exponentiation by squaring (also called fast or binary exponentiation), reduces the number of multiplications from O(e) to O(log e) by writing e in binary and repeatedly squaring the base while reducing modulo m at every step, so intermediate values never grow larger than m². This single technique — squaring plus modular reduction at every step — is what makes RSA encryption, Diffie–Hellman key exchange, and the Miller–Rabin primality test computationally feasible: they all require raising numbers to exponents with hundreds of digits, modulo similarly huge numbers.

Intuition

Instead of multiplying by b one factor at a time (e multiplications total), repeated squaring builds up powers of b that double at each step: b¹, b², b⁴, b⁸, b¹⁶, … After k squarings you already have b^(2^k) — exponential growth in the exponent from only k multiplications. Any exponent e can be assembled as a sum of distinct powers of 2 (its binary representation), so bᵉ is just the product of the b^(2^i) terms where bit i of e is 1. Reducing modulo m after every single multiplication (not just at the very end) keeps every number in the computation smaller than m², so the whole algorithm runs in O(log e) multiplications of numbers no bigger than m — this is precisely why an RSA server can compute a 2048-bit modular exponentiation in milliseconds instead of needing to store a number with hundreds of digits.

Formal Definition

Definition

Write the exponent e in binary as e = Σ bᵢ 2ⁱ (bᵢ ∈ {0,1}). The right-to-left binary method maintains a running result and a running squared base:

be mod m=b∑ibi2i mod m=∏i: bi=1b2i mod mb^{e} \bmod m = b^{\sum_i b_i 2^i} \bmod m = \prod_{i:\, b_i=1} b^{2^i} \bmod m
Binary decomposition of the exponent
result←1;base←b mod m\text{result} \leftarrow 1;\quad \text{base} \leftarrow b \bmod m
Initialization
while e>0:  if e odd, result←(result⋅base) mod m;  base←base2 mod m;  e←⌊e/2⌋\text{while } e>0:\ \ \text{if } e \text{ odd, result} \leftarrow (\text{result}\cdot \text{base}) \bmod m;\ \ \text{base} \leftarrow \text{base}^2 \bmod m;\ \ e \leftarrow \lfloor e/2 \rfloor
Right-to-left square-and-multiply loop
Time: O(log⁡e) modular multiplications, each on numbers<m\text{Time: } O(\log e) \text{ modular multiplications, each on numbers} < m
Complexity

Worked Examples

  1. Write 13 in binary: 13 = 8+4+1 = 1101₂. Build up squares of the base mod 7.

    31≡3,32≡2,34≡22≡4,38≡42≡2(mod7)3^1 \equiv 3,\quad 3^2 \equiv 2,\quad 3^4 \equiv 2^2 \equiv 4,\quad 3^8 \equiv 4^2 \equiv 2 \pmod 7

  2. 13 = 8+4+1, so multiply the base powers corresponding to the 1-bits (3^8, 3^4, 3^1).

    313≡38⋅34⋅31≡2⋅4⋅3(mod7)3^{13} \equiv 3^8 \cdot 3^4 \cdot 3^1 \equiv 2 \cdot 4 \cdot 3 \pmod 7

  3. Reduce the product modulo 7.

    2⋅4⋅3=24≡3(mod7)2 \cdot 4 \cdot 3 = 24 \equiv 3 \pmod 7

Answer: 3^13 mod 7 = 3.

Practice Problems

Difficulty 3/10

Compute 5^117 mod 19 (5^117 is far too large to compute directly, so use properties of modular exponentiation).

Difficulty 4/10

Using repeated squaring, compute 2^10 mod 100.

Difficulty 6/10

An RSA-style computation needs c = 7^560 mod 561, where 561 is a Carmichael number (561 = 3·11·17). Given that Fermat-like behavior can be misleading for Carmichael numbers, what does direct modular exponentiation give?

Quiz

The main advantage of exponentiation by squaring over naive repeated multiplication is:
Why is the result reduced modulo m after every multiplication step, rather than only at the end?
Modular exponentiation is a core operation in which of the following?

Summary

  • Modular exponentiation computes bᵉ mod m efficiently, without ever forming the full (astronomically large) number bᵉ.
  • Exponentiation by squaring writes e in binary and repeatedly squares the base modulo m, reducing the multiplication count from O(e) to O(log e).
  • Reducing modulo m after every multiplication (not just at the end) keeps all intermediate values bounded below m², which is essential for cryptographic-scale numbers.
  • This technique underlies RSA encryption, Diffie–Hellman key exchange, and primality tests like Miller–Rabin, all of which require raising huge numbers to huge exponents modulo huge moduli.
  • Carmichael numbers (like 561 = 3·11·17) satisfy Fermat's congruence aᵐ⁻¹ ≡ 1 (mod m) for all coprime bases despite being composite, which is why Fermat's test alone is unreliable for primality.

References

  1. WebsiteWikipedia — Modular exponentiation
  2. WebsiteWikipedia — Carmichael number