How It Works • • By Prime Number Calculator Team • ⏱ 12 min read

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.

How Fast Prime Tests Check Huge Numbers in Under a Millisecond
Illustration: How Fast Prime Tests Check Huge Numbers in Under a Millisecond

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 p is prime and doesn’t divide a, then raising a to the power (p − 1) and dividing by p always leaves a remainder of 1. 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 remainder 1 are 1 and p − 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 (rem 1), 5² = 25 (rem 1), and 7² = 49 (rem 1). Notice how 3 and 5 suddenly jump straight to 1!

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:

Flowchart showing the 4 steps of the Miller-Rabin prime test
Figure 1: Inside the fast prime check—splitting out powers of 2, calculating the first remainder, and watching repeated squares for red flags.

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 1 or n − 1, n passes this test base cleanly!
  • Otherwise, keep squaring the remainder up to s − 1 times (x = (x × x) mod n). If you hit n − 1 along the way, n passes 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!

Table comparing how many fixed test numbers guarantee 100% accuracy at each number size
Figure 2: Proven sets of fixed test numbers that guarantee zero false primes all the way up to 18 quintillion (2^64).

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:

  1. Pull powers of 2 out of 560: 560 = 16 × 35 = 2⁴ × 35, so s = 4 and d = 35.
  2. Start with remainder of 2³⁵ ÷ 561: x₀ = 263 (not 1 and not 560, so start squaring!).
  3. Square step 1: 263² = 69,169 → dividing by 561 leaves 166 (not 560).
  4. Square step 2: 166² = 27,556 → dividing by 561 leaves 67 (not 560).
  5. Square step 3: 67² = 4,489 → dividing by 561 leaves 1!

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

Try It Yourself

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.

Open Calculator →
π
Prime Number Calculator Team
Math Education & Software Team

Written in plain, friendly English and checked against trusted math research and automated tests.

More Articles You Might Like