primality test

SICP §1.2.6 gives three ways to test whether n is prime: trial division (exact, but slow – it tests every candidate divisor up to √n), the Fermat test (fast, but foolable – some composites satisfy aⁿ ≡ a (mod n) for every base), and Miller-Rabin (adds a check for nontrivial square roots of 1, which catches every composite the Fermat test misses). Every divisor test, expmod call, and squaring below is a recorded step – move the timeline to any step, or change the number, method, or bases and the trace recomputes.

The presets are chosen to make the methods disagree: 561 and 1105 are Carmichael numbers that fool the Fermat test for every base; 341 fools it for base 2 alone; 2047 is a strong pseudoprime that fools Miller-Rabin for base 2 alone; 3215031751 is the smallest number that fools Miller-Rabin even with bases 2, 3, 5, and 7 run together. Watching trial division, Fermat, and Miller-Rabin reach different verdicts on the same input is the point – a probabilistic test's speed comes at the cost of exactly this failure mode.

The pure trace/replay model lives in wal-sh.tools.primality-test.core (host-neutral .cljc). Because expmod's intermediate values can reach roughly the square of n (up to ~10²⁴ for the n <= 10¹² this tool allows), every arithmetic operation on a number outside JVM/JS's safe 2^53 range is routed through a small set of named big-* wrapper functions rather than a bare +=/-/=*=/=mod, so the same source compiles to Clojure's auto-promoting bignum ops on the JVM and to native js/BigInt operations in ClojureScript. Tested on the JVM with test.check: the curated presets produce their documented verdicts, and modpow computed through the wrapper functions agrees with independent bignum arithmetic (Clojure's own auto-promoting ops and java.math.BigInteger.modPow) for operands well past Long/MAX_VALUE. The browser adapter is wal-sh.tools.primality-test.browser. Build: gmake tools-cljs; debug in isolation: gmake dev-tool TOOL=primality-test.