---
tag: 04DR5PM25N
kind: concept
name: Modular exponentiation
aliases: [binary-exponentiation, square-and-multiply]
msc: [11Y16]
sources:
  - url: https://en.wikipedia.org/wiki/Modular_exponentiation
    locator: Right-to-left binary method
same_as:
  wikidata: Q1228841
  wikipedia: Modular exponentiation
---

## Summary

Modular exponentiation computes $b^e \bmod m$ for integers $b$, $e \ge 0$ and $m \ge 1$.
The binary method writes $e$ in base $2$. It squares $b$ again and again modulo $m$, and it multiplies the squares $b^{2^i}$ for the bits $i$ of $e$ that are $1$.
It needs about $2 \log_2 e$ multiplications modulo $m$, and each intermediate number is smaller than $m^2$.

## Remarks

The method is correct because of [[compatibility with multiplication|072D5G4SK6]]: one can reduce modulo $m$ after each multiplication.
The [[Fermat primality test|0N5ZSZMYH6]], the [[RSA cryptosystem|0HM584C465]] and the [[Diffie–Hellman key exchange|01TKKESHSB]] all use modular exponentiation.
The inverse problem, to find $e$ from $b$, $m$ and $b^e \bmod m$, is the [[discrete logarithm|09B4X51J09]] problem. It seems much harder.

## Explanations

### L1 human

To compute $3^{13} \bmod 7$, write $13 = 8 + 4 + 1$. The squares are $3^1 \equiv 3$, $3^2 \equiv 2$, $3^4 \equiv 4$ and $3^8 \equiv 2$.
Then $3^{13} \equiv 2 \cdot 4 \cdot 3 = 24 \equiv 3 \pmod 7$.
You never need the large number $3^{13} = 1594323$.