How Fast Prime Tests Check Huge Numbers in Under a Millisecond
See how web browsers check giant 19-digit numbers for primality in under 0.1 milliseconds with 100% accuracy—using just 7 special test numbers and no guesswork.
Checking small numbers for primes is easy: just test dividing up to the square root.
But what if someone types an 18- or 19-digit number near 2⁶⁴ (18,446,744,073,709,551,615)? Checking every prime up to its square root (4.29 billion!) would take billions of steps and freeze your web browser for seconds or minutes.
Yet our calculator checks 19-digit numbers instantly—in less than 0.1 milliseconds—with 100% certainty. How? It uses a clever remainder shortcut called the Miller-Rabin test.
1. The Big Idea: Remainder Patterns Instead of Dividing Everything
In the 1600s, French mathematician Pierre de Fermat spotted a neat trick about prime numbers and clock remainders:
If
pis prime and doesn’t dividea, then raisingato the power(p − 1)and dividing bypalways leaves a remainder of1.a^(p − 1) mod p = 1
Try it with p = 7 and a = 2:
2⁶ = 64. Divide 64 by 7: 64 = 9 × 7 + 1 → remainder 1!
Most composite numbers fail this test immediately, leaving some remainder other than 1.
The Catch: “Fake Primes” (Carmichael Numbers)
A tiny handful of sneaky composite numbers pass Fermat’s test anyway! The smallest one is 561 (3 × 11 × 17). Even though 561 has three factors, a⁵⁶⁰ leaves a remainder of 1 when divided by 561 for every base that doesn’t share a factor with 561!
In 1976 and 1980, Gary Miller and Michael Rabin added one extra step inside the remainder loop that catches fake primes like 561 red-handed.
How Miller & Rabin Spot Fake Primes
Think of square roots in clock math (x × x leaving remainder 1):
- For a real prime
p, the only numbers whose square leaves remainder1are1andp − 1(which acts like−1). - For a composite number, extra sneaky roots pop up out of nowhere! Look at remainders dividing by
8:1² = 1,3² = 9(rem1),5² = 25(rem1), and7² = 49(rem1). Notice how3and5suddenly jump straight to1!
Miller-Rabin watches those step-by-step squares. Whenever 1 appears out of nowhere (not from 1 or n − 1), the number is caught red-handed as composite!
2. How the Fast Check Works Step by Step
Here is the 4-step flow inside the Miller-Rabin check:
Step 1: Pull Out All Powers of 2 from n − 1
Because n is odd, n − 1 is always even. Keep dividing n − 1 by 2 until an odd number d is left:
n − 1 = 2^s × d
Step 2: Calculate the Starting Remainder (x₀)
Pick a test base number a (for example a = 2), and compute the remainder of a^d divided by n. Using repeated squaring, computers finish this even for giant exponents in dozens of tiny steps instead of billions!
Step 3: Look for 1 or n − 1
- If your starting remainder is already
1orn − 1,npasses this test base cleanly! - Otherwise, keep squaring the remainder up to
s − 1times (x = (x × x) mod n). If you hitn − 1along the way,npasses this test base!
Step 4: Caught Red-Handed!
If you finish all s − 1 squarings and never see n − 1, then n is 100% proven composite—even without finding what its factors are!
3. From Probability to 100% Exact Proof (The 7 Magic Numbers)
Normally, on giant 600-digit numbers used in bank security, Miller-Rabin picks 40 random test bases. Each passing round slashes the odds of a fake prime slipping through to less than (1/4)⁴⁰ (less than 1 in a septillion!).
Even better: for every whole number up to 2⁶⁴ (18.4 quintillion, or 18,446,744,073,709,551,615), mathematicians proved by testing every possible edge case that you don’t need random guesses at all!
The 7 Verified Test Numbers up to 18 Quintillion
In 2011, researcher Jim Sinclair confirmed that checking just 7 specific test numbers gives 100% mathematical certainty—zero fake primes, zero mistakes, for every single whole number below 2⁶⁴:
[2, 325, 9375, 28178, 450775, 9780504, 1795265022]
| Up to This Limit | How Many Checks Needed | Exact Fixed Test Numbers | Discovered By |
|---|---|---|---|
2,047 |
1 |
[2] |
Selfridge (1980) |
1,373,653 |
2 |
[2, 3] |
Pomerance, Selfridge, Wagstaff (1980) |
25,326,001 |
3 |
[2, 3, 5] |
Pomerance et al. |
3,215,031,751 |
4 |
[2, 3, 5, 7] |
Jaeschke (1993) |
341,550,071,728,321 (3.4 × 10¹⁴) |
7 |
[2, 3, 5, 7, 11, 13, 17] |
Bleichenbacher |
2⁶⁴ (18.4 Quintillion) |
7 |
[2, 325, 9375, 28178, 450775, 9780504, 1795265022] |
Sinclair (2011) |
(Fun fact: Our Engine uses Sinclair’s exact 7 numbers so any 19-digit number under 2⁶⁴ is tested with 100% proof—no approximations!)
4. Worked Walkthrough: Catching 561 Red-Handed
Watch how fast base a = 2 exposes the famous fake prime 561:
- Pull powers of 2 out of
560:560 = 16 × 35 = 2⁴ × 35, sos = 4andd = 35. - Start with remainder of
2³⁵ ÷ 561:x₀ = 263(not1and not560, so start squaring!). - Square step 1:
263² = 69,169→ dividing by561leaves166(not560). - Square step 2:
166² = 27,556→ dividing by561leaves67(not560). - Square step 3:
67² = 4,489→ dividing by561leaves1!
Look! We hit 1 right after 67 (not 560, which equals −1 mod 561). Only composite numbers can have a rogue square root like 67! We just proved 561 is composite without ever finding 3 × 11 × 17.
5. Ready-to-Run JavaScript Code (BigInt)
Notice how JavaScript’s normal Number loses accuracy past 15–16 digits, so we use BigInt (1n, 2n, etc.) for exact 64-bit math:
function powerMod(base, exp, mod) {
let res = 1n;
let b = base % mod;
let e = exp;
while (e > 0n) {
if (e & 1n) res = (res * b) % mod;
b = (b * b) % mod;
e >>= 1n;
}
return res;
}
/**
* 100% exact prime check for any whole number from 0 up to 2^64 - 1.
*/
export function isPrime64(n) {
const num = BigInt(n);
if (num < 2n) return false;
if (num === 2n || num === 3n) return true;
if ((num & 1n) === 0n || num % 3n === 0n) return false;
// Split num - 1 into (2^s) * d
let d = num - 1n;
let s = 0n;
while ((d & 1n) === 0n) {
d >>= 1n;
s += 1n;
}
// Proven 7 bases for 100% certainty up to 2^64
const bases = [2n, 325n, 9375n, 28178n, 450775n, 9780504n, 1795265022n];
for (const base of bases) {
const a = base % num;
if (a === 0n || a === 1n || a === num - 1n) continue;
let x = powerMod(a, d, num);
if (x === 1n || x === num - 1n) continue;
let composite = true;
for (let r = 1n; r < s; r++) {
x = (x * x) % num;
if (x === num - 1n) {
composite = false;
break;
}
}
if (composite) return false; // Caught as composite!
}
return true; // Passed all 7 checks: guaranteed prime!
}
6. How Different Prime Tests Compare
| Method | Speed | 100% Exact? | Best Number Size | Where It’s Used |
|---|---|---|---|---|
| Simple Trial Division | Slow for big numbers | Yes | Up to 10 million | Homework, small factors |
6k ± 1 Shortcut |
3× faster | Yes | Up to 100 million | Everyday calculators |
| 7-Base Miller-Rabin | Instant (< 0.1 ms) | Yes (up to 2⁶⁴) |
Up to 18 quintillion | Web tools & 64-bit apps |
| Random-Base Miller-Rabin | Very fast | Near-certain (99.9999999999%) |
Hundreds of digits | Banking & RSA security keys |
| AKS Test | Very slow | Yes (any size) | Math proofs | Research papers only |
Quick Questions & Answers
Can the 7-base fast check ever make a mistake below 2⁶⁴?
Never. Researchers checked all possible counterexamples below 2⁶⁴, and zero fake primes pass all 7 bases. Within that range, the result is a 100% proven mathematical fact.
How does online banking check giant 600-digit primes?
For 600-digit keys (2,048 binary bits), computers can’t use the fixed 64-bit bases. Instead, they run Miller-Rabin with 40–64 randomly picked bases (dropping error odds far below 1 in 1,000,000,000,000,000,000,000,000) plus an extra Lucas check to be extra sure.
Why don’t apps use the AKS prime test instead?
In 2002, three computer scientists made headlines by proving any size number can be checked in predictable polynomial time without luck—using the AKS test. In practice, though, AKS runs thousands of times slower than Miller-Rabin, so real software sticks with Miller-Rabin.
Interactive Tools to Try
- Test any 19-digit number right now: Prime Number Calculator
- Split composite numbers into primes: Prime Factorization Calculator
- Try locking & unlocking messages with primes: RSA Prime Demo
- See full details of how our calculator works: How It Works & Methodology
Want to check a prime number right now?
Our free online calculator checks numbers up to 18 quintillion with 100% accuracy, giving you instant factor trees and clear step-by-step reasons.
Written in plain, friendly English and checked against trusted math research and automated tests.