Modular Exponentiation: Square and Multiply

Introduction

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.

Try It: Square and Multiply

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">Pick a base a, exponent b and modulus n, then press Run square & multiply. Watch the algorithm read b's binary digits and reach a^b mod n in about log₂(b) steps — never building the gigantic full power.</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">Run square &amp; multiply</button>
  <button id="naive" type="button" class="ghost">Compare with naive</button>
</div>
<div class="status" id="status">Set a, b, n and run.</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Fast modular exponentiation (exponentiation by squaring).
// Computes a^b mod n in O(log b) modular multiplications instead of b-1.
// We use BigInt so intermediate squares (always reduced mod n) stay exact.
function modpow(a, b, n){
  a = BigInt(a) % BigInt(n);
  let bb = BigInt(b), nn = BigInt(n);
  let result = 1n, base = a, steps = [];
  while (bb > 0n){
    const bit = bb & 1n;
    // Multiply step happens BEFORE squaring base for the next bit.
    if (bit === 1n) result = (result * base) % nn;
    steps.push({ base: base.toString(), bit: Number(bit), result: result.toString() });
    base = (base * base) % nn;   // square
    bb >>= 1n;                    // next bit
  }
  return { value: result, steps };
}

function render(){
  const a = document.getElementById('a').value;
  const b = document.getElementById('b').value;
  const n = document.getElementById('n').value;
  if (BigInt(n) < 2n){ setStatus('Modulus n must be at least 2.', true); return; }
  const { value, steps } = modpow(a, b, n);
  const bitsOfB = BigInt(b).toString(2);
  const t = document.getElementById('trace');
  let html = '<tr><th>step</th><th>bit of b</th><th>op</th><th>running base (mod n)</th><th>result (mod n)</th></tr>';
  steps.forEach((s, i) => {
    const op = s.bit === 1 ? 'square + multiply' : 'square only';
    html += '<tr><td>'+(i+1)+'</td><td class="'+(s.bit?'bit1':'')+'">'+s.bit+
            '</td><td class="op">'+op+'</td><td>'+s.base+'</td><td>'+s.result+'</td></tr>';
  });
  t.innerHTML = html;
  setStatus(fmt('✓ %a%^%b% mod %n% = %value%  ·  b = %bitsOfB% in binary  ·  %length% steps (naive would need %v% multiplications).', { a: a, b: b, n: n, value: value, bitsOfB: bitsOfB, length: steps.length, v: BigInt(b)-1n }), false);
  console.log('modpow', a+'^'+b+' mod '+n, '=', value.toString(), '| steps:', steps.length);
}
function naive(){
  const a = document.getElementById('a').value;
  const b = document.getElementById('b').value;
  const n = document.getElementById('n').value;
  if (BigInt(b) > 200000n){ setStatus('Naive loop skipped: b is too large to multiply one-by-one — that is the whole point!', true); return; }
  let acc = 1n, A = BigInt(a) % BigInt(n), nn = BigInt(n), count = 0n;
  for (let i = 0n; i < BigInt(b); i++){ acc = (acc * A) % nn; count++; }
  setStatus(fmt('Naive one-by-one: %a%^%b% mod %n% = %acc%  ·  %count% multiplications (vs ~log₂(b) for squaring).', { a: a, b: b, n: n, acc: acc, count: count }), false);
}
function setStatus(t, bad){ const s = document.getElementById('status'); s.textContent = t; s.className = 'status'+(bad?' bad':''); }
document.getElementById('run').addEventListener('click', render);
document.getElementById('naive').addEventListener('click', naive);
render();

<p class="hint">Pick a base a, exponent b and modulus n, then press Run square & multiply. Watch the algorithm read b's binary digits and reach a^b mod n in about log₂(b) steps — never building the gigantic full power.</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">Run square &amp; multiply</button>
  <button id="naive" type="button" class="ghost">Compare with naive</button>
</div>
<div class="status" id="status">Set a, b, n and run.</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Fast modular exponentiation (exponentiation by squaring).
// Computes a^b mod n in O(log b) modular multiplications instead of b-1.
// We use BigInt so intermediate squares (always reduced mod n) stay exact.
function modpow(a, b, n){
  a = BigInt(a) % BigInt(n);
  let bb = BigInt(b), nn = BigInt(n);
  let result = 1n, base = a, steps = [];
  while (bb > 0n){
    const bit = bb & 1n;
    // Multiply step happens BEFORE squaring base for the next bit.
    if (bit === 1n) result = (result * base) % nn;
    steps.push({ base: base.toString(), bit: Number(bit), result: result.toString() });
    base = (base * base) % nn;   // square
    bb >>= 1n;                    // next bit
  }
  return { value: result, steps };
}

function render(){
  const a = document.getElementById('a').value;
  const b = document.getElementById('b').value;
  const n = document.getElementById('n').value;
  if (BigInt(n) < 2n){ setStatus('Modulus n must be at least 2.', true); return; }
  const { value, steps } = modpow(a, b, n);
  const bitsOfB = BigInt(b).toString(2);
  const t = document.getElementById('trace');
  let html = '<tr><th>step</th><th>bit of b</th><th>op</th><th>running base (mod n)</th><th>result (mod n)</th></tr>';
  steps.forEach((s, i) => {
    const op = s.bit === 1 ? 'square + multiply' : 'square only';
    html += '<tr><td>'+(i+1)+'</td><td class="'+(s.bit?'bit1':'')+'">'+s.bit+
            '</td><td class="op">'+op+'</td><td>'+s.base+'</td><td>'+s.result+'</td></tr>';
  });
  t.innerHTML = html;
  setStatus(fmt('✓ %a%^%b% mod %n% = %value%  ·  b = %bitsOfB% in binary  ·  %length% steps (naive would need %v% multiplications).', { a: a, b: b, n: n, value: value, bitsOfB: bitsOfB, length: steps.length, v: BigInt(b)-1n }), false);
  console.log('modpow', a+'^'+b+' mod '+n, '=', value.toString(), '| steps:', steps.length);
}
function naive(){
  const a = document.getElementById('a').value;
  const b = document.getElementById('b').value;
  const n = document.getElementById('n').value;
  if (BigInt(b) > 200000n){ setStatus('Naive loop skipped: b is too large to multiply one-by-one — that is the whole point!', true); return; }
  let acc = 1n, A = BigInt(a) % BigInt(n), nn = BigInt(n), count = 0n;
  for (let i = 0n; i < BigInt(b); i++){ acc = (acc * A) % nn; count++; }
  setStatus(fmt('Naive one-by-one: %a%^%b% mod %n% = %acc%  ·  %count% multiplications (vs ~log₂(b) for squaring).', { a: a, b: b, n: n, acc: acc, count: count }), false);
}
function setStatus(t, bad){ const s = document.getElementById('status'); s.textContent = t; s.className = 'status'+(bad?' bad':''); }
document.getElementById('run').addEventListener('click', render);
document.getElementById('naive').addEventListener('click', naive);
render();

Result

Console

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.

The Real Complexity

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.

Where It Matters

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.

Conclusion

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.

Comments

Loading comments...

https://www.kipuhub.com/en/article/modular-exponentiation/Content licensed under CC BY-NC 4.0.

Cookies & privacy

Modular Exponentiation

A trillion multiplications, done in forty steps