Modular Exponentiation

Suppose you want to compute $a^{b} \bmod n$: raise $a$ to the power $b$, then keep only the remainder when divided by $n$. With small numbers it is a pocket-calculator chore. But in cryptography $b$ can have hundreds of digits — a power so large it would not fit inside every atom in the universe.

The obvious method multiplies $a$ by itself $b$ times. If $b$ is around $2^{1024}$, that is more multiplications than there are seconds in the age of the cosmos. Done that way, modular exponentiation would be hopeless, and so would the cryptography built on top of it.

Yet your browser performs exactly this calculation every time it opens a secure connection — in well under a millisecond. The gap between "impossible" and "instant" is a single beautiful idea.

Pick a base $a$, an exponent $b$, and a modulus $n$. The naive way would multiply $a$ by itself $b$ times. Instead, watch the square-and-multiply method: it reads the exponent's binary digits and reaches the answer in about $\log_{2}(b)$ steps.

<p class="hint">{{hint}}</p>
<div class="inputs">
  <label>a <input id="a" type="number" value="7" min="2"></label>
  <label>b <input id="b" type="number" value="13" min="1"></label>
  <label>n <input id="n" type="number" value="1000" min="2"></label>
</div>
<div class="btns">
  <button id="run" type="button">{{btn_run}}</button>
  <button id="naive" type="button" class="ghost">{{btn_naive}}</button>
</div>
<div class="status" id="status">{{status_init}}</div>
<table class="trace" id="trace"></table>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.inputs { display: flex; gap: .8rem; flex-wrap: wrap; margin: .3rem 0 .6rem; }
.inputs label { font: 600 14px system-ui, sans-serif; color: #1d3557; display: flex; align-items: center; gap: .35rem; }
.inputs input { width: 78px; font: 600 14px ui-monospace, monospace; padding: .3rem .4rem;
                border: 1px solid #cdd9e3; border-radius: 6px; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .4rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; color: #0a7d33; }
.status.bad { color: #c92f3c; }
.trace { border-collapse: collapse; width: 100%; font: 13px ui-monospace, monospace; }
.trace th, .trace td { border: 1px solid #cdd9e3; padding: .3rem .5rem; text-align: center; }
.trace th { background: #e8eef3; color: #1d3557; }
.trace td.bit1 { background: #d8f0df; }
.trace td.op { color: #1d3557; font-weight: 700; }

// Code not found

Notice two things. First, the number of steps is roughly the number of bits in $b$, not $b$ itself — double the exponent and you add just one step. Second, every intermediate value is taken mod n immediately, so the running numbers never grow past $n^{2}$. The huge power is computed without ever writing the huge power down.

How expensive is $a^{b} \bmod n$, really?

• Naive repeated multiplication costs $b - 1$ multiplications. Since $b$ is given with only about $\log_{2}(b)$ bits, that is exponential in the input size — utterly impractical.
• Exponentiation by squaring writes $b$ in binary and processes one bit at a time: square the running value, and multiply by $a$ whenever the bit is 1. That is at most $2 \cdot \log_{2}(b)$ multiplications.
• It is in P. Each multiplication is taken mod $n$, so the numbers stay below $n^{2}$, and a multiplication of numbers that size is itself polynomial. The whole computation is polynomial in the number of input bits — it sits comfortably among the easy problems.
• The one-way twist. Going forward (given $a$, $b$, $n$, find $a^{b} \bmod n$) is cheap. Going backward — recovering the exponent $b$ from the result — is the discrete logarithm problem, for which no fast classical algorithm is known.

That asymmetry is the punchline: modular exponentiation is a trapdoor. Easy one way, believed hard the other. Reverse it efficiently and you would break much of modern cryptography — a feat tied to the open questions around P vs NP.

Square-and-multiply is quietly one of the most-executed pieces of math on Earth:

• RSA encryption and signatures: encrypting, decrypting and signing are all a single $a^{b} \bmod n$. Every HTTPS handshake using RSA runs this loop.
• Diffie-Hellman key exchange: two strangers agree on a shared secret over an open line by each computing modular powers — security rests on the discrete logarithm being hard to reverse.
• Primality testing: Fermat and Miller-Rabin tests raise random bases to large powers mod $n$ to decide, with overwhelming confidence, whether $n$ is prime — the step that finds the giant primes RSA needs.
• Hashing and randomness: many pseudo-random generators and commitment schemes lean on the same one-way power.

Learn how $a^{b} \bmod n$ is computed and you have met the single arithmetic operation that underpins most of the encrypted traffic on the internet.

Modular exponentiation hides a small miracle: a calculation that looks like it needs more steps than there are atoms in the universe finishes in the time it takes to read this sentence. The trick is humble — square, and multiply when the bit says so — yet it turns an exponential cost into a logarithmic one.

That speed is not just convenient; it is foundational. Because raising to a power mod $n$ is fast going forward and believed hard going backward, it gives us a usable trapdoor. The next time a padlock appears in your browser, remember the quiet squaring loop behind it — and the still-open question of whether anyone can ever run it in reverse, a question that touches the heart of P vs NP.