AlgoVerse

Modular exponentiation (repeated squaring)

Compute aᵇ mod n with about log b multiplications: square the base again and again, and multiply it in for every 1 bit of b.

Computing aᵇ with b − 1 multiplications is hopeless for large b (as in RSA). But write b in base 2:

Read the full explanation ↓
Input:
a=7 · b=560 · n=561PDF export

7⁵⁶⁰ mod 561 = 1; 560 has ten bits, so 13 multiplications (10 squarings and 3 products) do instead of 559.

  1. def mod_pow(a, b, n):
  2. # a to the power b, mod n, reading the bits of b from the right.
  3. result = 1 % n
  4. base = a % n
  5. rows = []
  6. while b > 0:
  7. bit = b % 2
  8. if bit == 1:
  9. result = result * base % n
  10. rows.append((bit, base, result))
  11. base = base * base % n
  12. b = b // 2
  13. return result

Invariant: result · base^b mod n always equals the final answer aᵇ mod n (with the current b and base).

Start

b560
base—
result—

The table is still empty.

Local variables

a7
b560
n561

Orange = changed in this step

Call stack

  1. mod_pow()line 1
Step 1 of 69
Black = square · Orange = key stepsquare: 0/10 · multiply: 0/3 · done: 0/1
    Explanation

    The idea

    Computing aᵇ with b − 1 multiplications is hopeless for large b (as in RSA). But write b in base 2:

    b = 560 = 1000110000₂   ⇒   a⁵⁶⁰ = a⁵¹² · a³² · a¹⁶

    The powers a¹, a², a⁴, a⁸, … come from repeated squaring, and only those whose bit is 1 are multiplied into the answer. Taking mod n after each multiplication keeps the numbers small.

    Cost

    At most 2 log b multiplications. It underlies RSA, the Miller–Rabin test and Diffie–Hellman.

    What to watch in the trace

    • Each table row is one bit of b (from the right): the bit, that round's base and the result so far.