🧷 Prime Checker

Deterministic Miller–Rabin · prime factorisation · exact to 2⁶³

Advertisement

Two questions in one page: is this number prime? — answered with the deterministic Miller–Rabin test using the twelve bases proven sufficient below 3.3×10²⁴, so the verdict is a proof, not a gamble — and what is it made of?, the prime factorisation by trial division.

—

The maths, stated honestly

Trial division alone cannot touch 20-digit numbers; probabilistic tests can be fooled by constructed composites. Miller–Rabin sits between them: for every n below 3,317,044,064,679,887,385,961,981 the twelve bases 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 and 37 give a deterministically correct verdict — no probability involved. Factorisation here uses trial division past small primes; a number whose remaining part has no factor ≤ 1,000,000 is reported as such rather than faked into a full split. That refusal is the point: the RSA numbers protecting your bank are hard precisely because nobody has a fast general factoriser.

Part of Everyday Tools. Like everything on tukuk.org: free, no account, no tracking.

Advertisement
Advertisement