Fast Modular Exponentiation

Compute bⁿ by repeated squaring: read the exponent in binary and multiply the running result by the current square only where a bit is 1. Cornerstone of RSA and modular arithmetic.

Category

Mathematics

Time complexity

O(log n)

Space complexity

O(1)

Pseudocode

result ← 1
while exp > 0
  if exp bit is 1: result ×= base
  base ← base²; exp ≫= 1

Reference implementation

result = 1
while e > 0:
    if e & 1: result = result * b % mod
    b = b * b % mod
    e >>= 1

Open the interactive Fast Modular Exponentiation visualisation →