◄ WORLD V · SONNY 5DART 032 · a helldive at the net

RABIN–MILLER probably prime

How to tell if a 300-digit number is prime without factoring it: interrogate it with random witnesses. Each honest witness that fails to expose the number halves your doubt. It never proves primality — it makes composite-ness astronomically unlikely. And its engine, modular exponentiation, now runs in real I-13 — because the % this campaign recommended just merged.

THE TECHNIQUE random witnesses · modular exponentiation

Write n−1 = 2^s · d. Pick a random base a and compute a^d mod n, squaring up. A prime forces a strict pattern; a composite almost always breaks it — that base is a witness to its composite-ness. k rounds leave a false-prime chance below 4^−k. live demo

HISTORY & CREDIT deterministic dream, randomized reality

The name pairs two people who solved the same subtly different problems four years apart. cited

1976 · Gary L. Miller gives a deterministic polynomial-time test — but its correctness rests on the unproven Extended Riemann Hypothesis.
1980 · Michael O. Rabin removes the hypothesis by making it randomized: pick witnesses at random, accept a tiny, controllable error. Unconditional, fast, practical.
context · alongside Solovay–Strassen (1977); the whole family made public-key crypto (RSA needs big primes) actually deployable.
2002 · Agrawal–Kayal–Saxena finally give an unconditional deterministic polynomial test — elegant, but Rabin–Miller is still what everything ships.

A rare case where the probabilistic answer beat the deterministic one into practice — fitting, for World V’s probabilistic wing. still shipped

RECOMMEND FOR I-13 the campaign’s own % came back

The engine is modular exponentiation — and thanks to the % operator this campaign recommended and just merged to main, it runs in real I-13:

def modexp(I base, I e, I m) { if e == 0 { -> 1 } I half <- modexp(base, e - 1, m) -> (half * base) % m } I r1 <- modexp(2, 10, 1000) // 1024 mod 1000 I r2 <- modexp(3, 13, 100)
$ i13 run modexp.i13 # on main, with the merged % RUN OK · 550 step(s) · call depth 14 r1 = 24 r2 = 23 r3 = 401
Recommend: the last two walls for a real primality test are arbitrary-precision integers (f64 loses exactness past 2⁵³, so cryptographic n overflow) and a seeded PRNG for witness choice. The bignum ask is the honest one: modexp is correct here but bounded — declare the f64 ceiling, or add a bignum type.
Self-referential payoff: this is the second dart (after Collatz, dart 010) where the campaign’s own recommend landed and made an algorithm run. The loop closes: measure a wall → recommend → implement → the next dart clears it.