A question a child can ask

Pick a number. Is it prime — divisible only by 1 and itself? For small numbers you just check. Is 7 prime? Yes. Is 91? No (it's 7 × 13). The question is so elementary a child can ask it. But asking it about a number with hundreds of digits turns it into one of the most beautiful stories in computer science.

For decades, primality testing sat in a strange limbo. We had fast methods that were probably right, and slow methods that were certainly right, but no fast method that was provably always right. Then, in 2002, three Indian computer scientists — Agrawal, Kayal and Saxena — settled it with the AKS algorithm, proving that primality is in P: decidable in polynomial time.

And here's the twist that makes primes the perfect kipu story: deciding whether a number is prime is easy, but finding its prime factors is (as far as we know) hard. That gap is the foundation of modern cryptography.

Test a number yourself

Type any whole number and the demo runs two tests side by side. Trial division is the schoolbook method — try every possible divisor up to √N; certain, but it slows to a crawl as numbers grow. Miller–Rabin is the probabilistic test real systems use: it performs a handful of clever modular checks and is correct with overwhelming probability, even for numbers with hundreds of digits.

<p class="hint">Type a whole number. <b>Trial division</b> (schoolbook) tries every divisor up to √N — certain, but slow. <b>Miller–Rabin</b> (used in real cryptography) answers in a handful of modular checks, even for huge numbers. Compare the step counts.</p>
<div class="inrow">
  <input id="num" type="text" inputmode="numeric" value="1000000007" class="num" />
  <button id="run" class="btn">Test</button>
</div>
<div class="quick">
  Try: <a data-n="97">97</a> <a data-n="561">561</a>
  <a data-n="7919">7919</a> <a data-n="1000000007">1000000007</a>
  <a data-n="2147483647">2147483647</a>
</div>
<div class="cards">
  <div class="card">
    <h4>Trial division</h4>
    <div class="verdict" id="tdVerdict">—</div>
    <div class="steps">steps: <b id="tdSteps">0</b></div>
  </div>
  <div class="card">
    <h4>Miller–Rabin</h4>
    <div class="verdict" id="mrVerdict">—</div>
    <div class="steps">checks: <b id="mrSteps">0</b></div>
  </div>
</div>

* { box-sizing: border-box; }
.hint { font-size: 14px; color: #556; line-height: 1.5; }
.inrow { display: flex; gap: 8px; margin: 14px 0 8px; }
.num {
  flex: 1; padding: 10px 12px; font-size: 16px; font-family: ui-monospace, monospace;
  border: 2px solid #d7dee6; border-radius: 8px;
}
.btn { padding: 10px 20px; border: none; border-radius: 8px; background: #1f6feb; color: #fff; font-size: 15px; cursor: pointer; }
.btn:hover { background: #1a5fd0; }
.quick { font-size: 13px; color: #667; margin-bottom: 16px; }
.quick a { color: #1f6feb; cursor: pointer; margin: 0 4px; text-decoration: underline; }
.cards { display: grid; grid-template-columns: 1fr 1fr; gap: 12px; }
.card { background: #f3f5f8; border: 1px solid #d7dee6; border-radius: 10px; padding: 14px; }
.card h4 { margin: 0 0 10px; font-size: 14px; color: #334; }
.verdict { font-size: 20px; font-weight: 700; margin-bottom: 8px; }
.verdict.prime { color: #0f6e56; }
.verdict.composite { color: #c0392b; }
.verdict.slow { color: #9a6a00; font-size: 15px; }
.steps { font-size: 13px; color: #667; font-family: ui-monospace, monospace; }
@media (max-width: 480px) { .cards { grid-template-columns: 1fr; } }

// Two ways to answer "is N prime?" — one certain-but-slow, one fast-and-practical.

// --- Trial division: try divisors up to sqrt(N). Capped so the page never freezes. ---
const STEP_CAP = 5_000_000;
function trialDivision(n) {
  let steps = 0;
  if (n < 2n) return { verdict: 'composite', steps };
  for (let i = 2n; i * i <= n; i++) {
    steps++;
    if (steps > STEP_CAP) return { verdict: 'slow', steps };
    if (n % i === 0n) return { verdict: 'composite', steps };
  }
  return { verdict: 'prime', steps };
}

// --- Miller-Rabin with fixed witnesses: deterministic for n < 3.3 * 10^24. ---
function modpow(b, e, m) {
  b %= m; let r = 1n;
  while (e > 0n) { if (e & 1n) r = r * b % m; b = b * b % m; e >>= 1n; }
  return r;
}
const WITNESSES = [2n,3n,5n,7n,11n,13n,17n,19n,23n,29n,31n,37n];
function millerRabin(n) {
  let checks = 0;
  if (n < 2n) return { verdict: 'composite', checks };
  for (const p of WITNESSES) { checks++; if (n % p === 0n) return { verdict: n === p ? 'prime' : 'composite', checks }; }
  let d = n - 1n, r = 0n;
  while (d % 2n === 0n) { d /= 2n; r++; }
  for (const a of WITNESSES) {
    checks++;
    let x = modpow(a, d, n);
    if (x === 1n || x === n - 1n) continue;
    let composite = true;
    for (let i = 0n; i < r - 1n; i++) { x = x * x % n; if (x === n - 1n) { composite = false; break; } }
    if (composite) return { verdict: 'composite', checks };
  }
  return { verdict: 'prime', checks };
}

const label = { prime: 'PRIME', composite: 'composite', slow: 'too slow — stopped' };

function paint(el, stepsEl, res) {
  el.className = 'verdict ' + res.verdict;
  el.textContent = res.verdict === 'slow' ? 'too slow — stopped' : label[res.verdict];
  stepsEl.textContent = (res.steps ?? res.checks).toLocaleString('en-US');
}

function run() {
  const raw = document.getElementById('num').value.trim().replace(/[^0-9]/g, '');
  if (!raw) return;
  let n;
  try { n = BigInt(raw); } catch (e) { return; }
  paint(document.getElementById('tdVerdict'), document.getElementById('tdSteps'), trialDivision(n));
  paint(document.getElementById('mrVerdict'), document.getElementById('mrSteps'), millerRabin(n));
}

document.getElementById('run').addEventListener('click', run);
document.getElementById('num').addEventListener('keydown', e => { if (e.key === 'Enter') run(); });
document.querySelectorAll('.quick a').forEach(a =>
  a.addEventListener('click', () => { document.getElementById('num').value = a.dataset.n; run(); }));
run();
Result
Console

Try a big prime, then a big composite. Watch trial division count thousands of steps while Miller–Rabin answers in a dozen. That difference — between "works" and "works at scale" — is what complexity is all about.

The hard part

Why was "is N prime?" so hard to resolve, even though answering it feels easy?

  • Trial division is exponential. Checking divisors up to √N sounds cheap, but N's size is the number of its digits. A 300-digit number has √N ≈ 1015010^{150} candidates — utterly impossible. Efficiency must be measured against digit count, not the value.

  • Probabilistic tests came first. The Fermat test, and the stronger Miller–Rabin, are fast and almost never wrong — but "almost" left a theoretical gap. They put primality in the class BPP (efficient with randomness).

  • AKS closed the gap (2002). It proved primality is in P without any randomness or unproven assumptions — a landmark result. In practice everyone still uses Miller–Rabin because it's faster, but AKS settled the theory: testing primality is genuinely easy.

Now the contrast. Factoring — given N, find its prime factors — has no known efficient algorithm. Deciding that a number is composite is easy; splitting it into factors is hard. Two questions about the very same number, on opposite sides of the tractability line. (And Shor's quantum algorithm could one day factor efficiently — see the factoring article on kipu.)

Where it matters

The easy/hard split around primes is not academic — it secures the internet:

  • RSA cryptography. To make a key, generate two huge random primes and multiply them. Generating them needs a fast primality test (Miller–Rabin); breaking the key would need fast factoring (which nobody can do). Your bank login rests on exactly this asymmetry.

  • Key generation everywhere. HTTPS, SSH, signed software updates and cryptocurrencies all lean on quickly finding large primes.

  • Hashing and pseudorandomness. Primes underpin hash tables, error-correcting codes and random-number generators.

Every time you see a padlock in your browser, a primality test ran moments ago — and the security depends on factoring staying hard.

Easy to check, hard to break

"Is N prime?" is the perfect miniature of computational complexity. The question is trivial to state, surprisingly subtle to settle (it took until 2002 to prove it's in P), and it sits right next to a twin question — factoring — that we believe is genuinely hard. That tiny gap between recognizing primes and factoring composites is the hinge on which modern cryptography turns.

Numbers, it turns out, aren't just things to count with. They're a laboratory for the deepest question on kipu: what makes a problem easy, and what makes it hard?

Share this article

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

Comments

Loading comments...

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