Number TheoryCongruences

Fast Powers mod n

Square again and again, multiply the powers that match the binary digits of the exponent, and reduce after every step.

Not started Jump to practice

Cryptography constantly needs numbers like $a^{e} \bmod n$ with exponents hundreds of digits long. Multiplying $a$ by itself $e$ times would take longer than the age of the universe. Two ideas make it instant: reduce mod $n$ after every multiplication (allowed by modular arithmetic), and build the exponent from its binary digits.

Repeated squaring. To find $a^{e} \bmod n$:

  • Write $e$ in binary, that is, as a sum of powers of 2.
  • Square again and again: $a^{1}, a^{2}, a^{4}, a^{8}, \dots$, each one the square of the one before, reduced mod $n$.
  • Multiply together the powers whose binary digit is 1, reducing after each multiplication.

Why it works

Since $a^{s + t} = a^{s} a^{t}$, a sum of powers of two in the exponent becomes a product of the squares you computed. Each square is the square of the previous one, so reaching $a^{2^{k}}$ takes only $k$ squarings. An exponent with $k + 1$ binary digits needs at most $k$ squarings and $k$ more multiplications: for a 600-digit exponent, about 4,000 steps instead of $10^{600}$. Reducing each time keeps every number below $n^{2}$.

Worked example: A small case

Find $5^{13} \bmod 23$.
  1. $13 = 8 + 4 + 1$ (binary $1101$).
  2. $5^{1} \equiv 5$, $\ 5^{2} = 25 \equiv 2$, $\ 5^{4} \equiv 2^{2} = 4$, $\ 5^{8} \equiv 4^{2} = 16$.
  3. $5^{13} = 5^{8} \cdot 5^{4} \cdot 5^{1} \equiv 16 \cdot 4 \cdot 5 = 320$.
  4. $320 = 23 \cdot 13 + 21$, so $5^{13} \equiv 21 \pmod{23}$.

Answer: $21$.

Count the work: three squarings and two multiplications, five in all, instead of the twelve multiplications of $5 \cdot 5 \cdots 5$. And no number above $22^{2} = 484$ ever appeared. (Check by brute force: $5^{13} = 1{,}220{,}703{,}125 = 23 \cdot 53{,}074{,}048 + 21$.)

The table for $3^{45} \bmod 100$, the last two digits of $3^{45}$: one row per binary digit of 45, the repeated squares, and the running product of the rows whose bit is 1. Change the exponent and watch how few rows it needs.

Worked example: Last two digits

Find the last two digits of $3^{45}$.
  1. We want $3^{45} \bmod 100$. $45 = 32 + 8 + 4 + 1$.
  2. $3^{2} = 9$, $\ 3^{4} = 81$, $\ 3^{8} \equiv 81^{2} = 6561 \equiv 61$, $\ 3^{16} \equiv 61^{2} = 3721 \equiv 21$, $\ 3^{32} \equiv 21^{2} = 441 \equiv 41$.
  3. $3^{45} \equiv 41 \cdot 61 \cdot 81 \cdot 3$. Step by step: $41 \cdot 61 = 2501 \equiv 1$, then $1 \cdot 81 = 81$, then $81 \cdot 3 = 243 \equiv 43$.

Answer: $43$.

Common mistake

Computing the whole power first. $3^{45} = 2{,}954{,}312{,}706{,}550{,}833{,}698{,}643$ already has 22 digits, and a calculator rounds it, so its last digits come out wrong. Reduce after every multiplication, so no number ever exceeds $(n - 1)^{2}$. And do not reduce the exponent mod $n$: $3^{45} \not\equiv 3^{45 \bmod 100}$ in general. (The right way to shrink exponents comes with Fermat's theorem.)

Key idea

Write the exponent in binary, square repeatedly, multiply the squares you need, and reduce mod $n$ after every multiplication. About $2\log_2 e$ multiplications suffice.

Practice

Pass with 3 right answers, the last 2 in a row. Each right answer earns 2 XP.

Loading practice…

Builds on

Leads to

Sources and further reading

  • William Stein, Elementary Number Theory: Primes, Congruences, and Secrets (Springer, 2009; free online edition), chapter 2, The Ring of Integers Modulo n (quickly computing huge powers)
  • Lehman, Leighton and Meyer, Mathematics for Computer Science (MIT OpenCourseWare 6.042J), chapter on number theory: modular arithmetic and RSA
@teddyrookbook GitHub