Introduction

Pick a number g, a prime p, and a secret exponent x. Computing h = gˣ mod p — multiply g by itself x times, wrapping around p — is quick and easy, even for huge numbers.

Now go the other way. I hand you g, p and h, and ask: what was x? Suddenly there's no shortcut. The values of gˣ bounce around the range 0…p unpredictably, giving you no hint whether you're close. This is the discrete logarithm problem, and like factoring, it's a one-way function: trivial forward, believed brutally hard backward.

That asymmetry is a gift to cryptography. It lets two strangers agree on a shared secret over an open line — the famous Diffie–Hellman key exchange — and underpins elliptic-curve cryptography, which protects much of today's secure web.

Crack the Lock

Try it. With base g and prime p fixed, choose a secret exponent — the demo computes h = gˣ mod p (the public value). Then hit Crack to brute-force x back, testing exponents one by one and counting steps.

<p class="hint">With base <b>g = 5</b> and prime <b>p = 23</b>, pick a secret exponent x.
    The public value is <b>h = 5<sup>x</sup> mod 23</b>. Then Crack it — brute force searches
    every exponent until it matches.</p>
<div class="lock">
  <label>secret x = <b id="xv">6</b></label>
  <input id="x" type="range" min="1" max="22" value="6" />
  <div class="pub">public h = 5<sup id="xe">6</sup> mod 23 = <b id="h">8</b></div>
  <div class="btns">
    <button id="crack" type="button">Crack (brute force)</button>
    <button id="reset" type="button" class="ghost">Reset</button>
  </div>
  <div id="out" class="out"></div>
</div>
<hr/>
<h4 class="h">Diffie–Hellman handshake</h4>
<p class="hint">Alice and Bob each keep a secret, swap only public powers, and reach the
    <b>same shared key</b> — without ever sending it.</p>
<div class="dh">
  <div class="party">
    <div class="who">Alice</div>
    <label>secret a <input id="a" type="number" min="1" max="22" value="6" /></label>
    <div>sends A = 5<sup>a</sup> mod 23 = <b id="A">—</b></div>
    <div>computes B<sup>a</sup> = <b id="ka" class="key">—</b></div>
  </div>
  <div class="party">
    <div class="who">Bob</div>
    <label>secret b <input id="b" type="number" min="1" max="22" value="15" /></label>
    <div>sends B = 5<sup>b</sup> mod 23 = <b id="B">—</b></div>
    <div>computes A<sup>b</sup> = <b id="kb" class="key">—</b></div>
  </div>
</div>
<div id="shared" class="shared"></div>

* { 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; }
.lock label { font: 600 14px system-ui; color: #1d3557; }
input[type=range] { width: 100%; margin: .4rem 0; accent-color: #457b9d; }
.pub { font: 700 15px ui-monospace, monospace; color: #1d3557; margin: .3rem 0 .6rem; }
.pub b, .out b { color: #2a9d8f; }
.btns { display: flex; gap: .5rem; margin-bottom: .5rem; }
button { font: 600 14px system-ui, sans-serif; padding: .5rem 1rem; border: 1px solid #457b9d; background: #457b9d; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #457b9d; }
.out { font: 600 14px system-ui; min-height: 1.3em; line-height: 1.5; }
.out .steps { color: #c0392b; font-weight: 800; }
hr { border: none; border-top: 1px solid #e6e9ee; margin: 1.1rem 0; }
.h { font: 700 14px system-ui; color: #1d3557; margin: 0 0 .4rem; }
.dh { display: grid; grid-template-columns: 1fr 1fr; gap: .7rem; }
.party { border: 1px solid #e6e9ee; border-radius: 10px; padding: .7rem; font: 600 13px system-ui; color: #444; line-height: 1.7; }
.who { font-weight: 800; color: #457b9d; margin-bottom: .3rem; }
.party input { width: 4rem; font: 700 14px ui-monospace, monospace; padding: .2rem .4rem; border: 1px solid #bbb; border-radius: 6px; }
.key { color: #6d597a; }
.shared { margin-top: .7rem; font: 800 15px system-ui; min-height: 1.3em; }
.shared.ok { color: #0a7d33; } .shared.bad { color: #c0392b; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Discrete log: given g, p, h = g^x mod p, find x. Easy forward (modpow),
// believed hard backward (here brute-forced for a tiny prime p=23).
const G = 5, P = 23;
function modpow(base, exp, mod) { let r = 1; base %= mod; while (exp > 0) { if (exp & 1) r = (r * base) % mod; base = (base * base) % mod; exp >>= 1; } return r; }

const $ = id => document.getElementById(id);

function updateLock() {
  const x = +$('x').value;
  $('xv').textContent = x; $('xe').textContent = x;
  $('h').textContent = modpow(G, x, P);
  $('out').innerHTML = '';
}

function crack() {
  const h = modpow(G, +$('x').value, P);
  let steps = 0, found = -1;
  for (let e = 1; e < P; e++) { steps++; if (modpow(G, e, P) === h) { found = e; break; } }
  $('out').innerHTML = fmt('Found <b>x = %found%</b> after <span class="steps">%steps%</span> steps. With a real 600-digit prime, that search has more steps than atoms in the universe.', { found: found, steps: steps });
}

function updateDH() {
  const a = Math.max(1, Math.min(22, +$('a').value || 1));
  const b = Math.max(1, Math.min(22, +$('b').value || 1));
  const A = modpow(G, a, P), B = modpow(G, b, P);
  const ka = modpow(B, a, P), kb = modpow(A, b, P);
  $('A').textContent = A; $('B').textContent = B;
  $('ka').textContent = ka; $('kb').textContent = kb;
  const s = $('shared');
  if (ka === kb) { s.className = 'shared ok'; s.textContent = fmt('✓ Shared key = %ka% — both computed g^(ab) mod p = %G%^%v% mod 23, never sent over the wire.', { ka: ka, G: G, v: a * b }); }
  else { s.className = 'shared bad'; s.textContent = 'Keys differ?!'; }
}

$('x').addEventListener('input', updateLock);
$('crack').addEventListener('click', crack);
$('reset').addEventListener('click', () => { $('x').value = 6; updateLock(); });
['a', 'b'].forEach(id => $(id).addEventListener('input', updateDH));
updateLock(); updateDH();
Result
Console

For a tiny prime it's instant; the counter still shows the search is linear in the size of p, which becomes hopeless for the 600-digit primes used in practice. Below, watch a Diffie–Hellman handshake: Alice and Bob each keep a secret exponent, exchange only public powers, and arrive at the same shared key — which an eavesdropper can't compute without solving the discrete log.

The Hard Part

The discrete logarithm sits almost exactly where factoring does:

  • Verifying is trivial: given a candidate x, compute gˣ mod p and check it equals h.
  • Brute force tries every exponent — linear in p, i.e. exponential in the number of digits.
  • The best classical methods (index calculus and its relatives) are sub-exponential: far better than brute force, still far from polynomial. For well-chosen primes, no one can do it in reasonable time.
  • It's in NP, not known to be NP-complete, and not known to be in P — its hardness is a widely held belief, not a theorem.
  • Quantum breaks it. Shor's algorithm solves discrete log in polynomial time on a quantum computer, just as it factors. A large quantum machine would break Diffie–Hellman and classic elliptic-curve crypto alike.

So discrete log and factoring are twin pillars of public-key cryptography — and twin casualties of quantum computing, which is why the world is racing toward post-quantum schemes.

Where It Matters

The discrete log quietly guards how secrets are shared online:

  • Diffie–Hellman key exchange: two parties derive a shared key over a public channel — the foundation of secure sessions.
  • Elliptic-curve cryptography (ECC): a discrete log over elliptic curves, giving strong security with small keys — used in TLS, SSH, and messaging apps.
  • Digital signatures: DSA, ECDSA and EdDSA sign software, transactions and certificates.
  • Cryptocurrencies: Bitcoin and Ethereum keys are elliptic-curve discrete-log pairs.
  • HTTPS everywhere: the padlock's key agreement often rests on exactly this problem.

It is, with factoring, one of the two hard problems holding up the public-key internet.

Conclusion

The discrete logarithm is factoring's quieter twin: another easy-forward, hard-backward operation we've turned into a cornerstone of digital trust. Its one-way nature is the small miracle that lets two people who've never met agree on a secret while the whole world listens.

And like factoring, it carries the same asterisk. Its hardness is a belief, not a proof, and a sufficiently large quantum computer would dissolve it via Shor's algorithm. That's why both pillars are being shored up with post-quantum cryptography — so the locks keep holding even as the tools to pick them evolve.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

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