How does Miller-Rabin work?

Miller-Rabin is a probabilistic primality test that picks random witnesses and checks if they prove the number composite. With enough good witnesses, the test is deterministic for n below specific thresholds. For very large numbers it's probabilistic but with vanishingly small false-positive rates.

Is the largest known prime?

Mersenne prime 2^82,589,933 − 1 (~25 million digits) was the largest known as of 2018. Computer-search projects like GIMPS regularly find larger ones. The tool can verify any specific number up to ~10^16 deterministically.

Why does primality matter in cryptography?

RSA security relies on the difficulty of factoring large composites that are products of two primes. Each RSA key uses two ~1024-bit primes — Miller-Rabin tests are how those are generated and verified at key creation.

miller-rabin · bigint · deterministic · local

Check if a number is prime

Q: Is anything sent to a server?

No — the test runs in your browser.

Trial division for small inputs, Miller-Rabin (deterministic up to 3.3 × 10¹⁴) for big BigInt integers. Reports the smallest factor when not prime.

Prime Checker

Status

prime

checked

Digits

of n

Method

trial division

algo

Output

37 B

ready

input · integer n

Underscores, commas, and whitespace inside the number are stripped. Negative numbers are rejected.

output · result

PRIMEn = 9973

method: trial division

Quick Start

How to test primality

For small inputs we trial-divide. For large inputs we run deterministic Miller-Rabin with the SPRP witnesses that cover all n < 3.3 × 10¹⁴.

01
Type a number
Up to thousands of digits — BigInt handles them all.
Inputs are treated as UTF-8 throughout the pipeline and validated client-side as you type — nothing dispatches until the value is well-formed.
inpututf-8client-sidevalidated
n · text9973 · set
```
9973
```
loaded · parsedclient-side
02
Read the verdict
PRIME or NOT PRIME, in big mono type.
Each toggle re-computes through a memoised hook, so flipping options never resets your input and the UI stays snappy on large inputs.
verdictoptionslivememoisedtoggles
result · memoisedprime · live
```
PRIME
```
options set · memoisedlive
03
Inspect factor
For composites we show the smallest prime factor when feasible.
Randomness — where used — comes from crypto.getRandomValues, never Math.random. Heavy work sits in useMemo.
factorcomputeinstantlocaldeterministic
p · instantsmallest · computed
```
p = 7
```
computed · instantinstant
04
Copy result
Grab a tidy summary as plain text.
Copy writes through navigator.clipboard and downloads use a Blob — zero network traffic. Same input plus same options always yield the same bytes.
copydownloadzero-networkreproducible
ok · copiedtxt · copied
```
Copied
```
shipped · ready to shipsuccess

Pro tips

Pro tips for everyday utilities

Reach for crypto.getRandomValues

Cryptographically random for IDs, tokens, salts. Math.random is for animation and games, not security.

Sort IDs lexicographically

UUID v4 has no time ordering. Use ULID or UUID v7 if you need sorted IDs.

Mock data with seeds

Faker-style libraries can be seeded so tests are reproducible. Embed the seed in the fixture file.

Reference cards beat memory

Cheatsheets for Vim, Git, Docker, Linux signals are faster than man pages when you’re mid-flow.

Browser APIs vary

Touch events, gamepads, and clipboard differ across vendors. Feature-detect before use.

Persist in the right place

localStorage for user preferences, sessionStorage for transient state, IndexedDB for structured data.

Use Cases

Why check primality

Crypto, math homework, programming puzzles, factoring assistance.

RSA practice

Verify candidate primes during cryptography homework. Random values come from crypto.getRandomValues — cryptographically secure for tokens, salts, and session IDs. Math.random is deterministic enough for animations but predictable enough to be a security bug.

CSPRNG-backed

Coding interview prep

Sanity-check brute-force prime checks against a fast reference. Pair with hashids, ULID, or UUID v7 when you need both random and sortable — useful for primary keys, public-facing IDs, and event log ordering without a sequence column.

reproducible

Math classroom

Demonstrate Miller-Rabin vs. trial division speed. Output is deterministic given the same seed, so fixtures and tests stay reproducible across CI runs and contributor machines. Embed the seed in the fixture file for full replay.

snappy

Puzzle solving

Quickly factor small composites for number-theory puzzles. Heavy work runs through useMemo so the UI stays snappy on large inputs. Same input + same options yields identical bytes — the kind of stability snapshot tests rely on.

feature-detected

Sequence research

Confirm primality for terms in OEIS-style sequences. Storage tools persist to the right backend: localStorage for user preferences, sessionStorage for transient state, IndexedDB for structured data. Pick the right shelf and quota worries disappear.

deterministic

Large integers

Test arbitrary BigInts your language might struggle with. Browser feature detection: clipboard, fullscreen, gamepad, and Web Bluetooth APIs gracefully fall back when unavailable. No surprise white screens on Safari or older Firefox.

production-ready

FAQ

Frequently asked questions

Is Miller-Rabin probabilistic?

With this witness set it's deterministic for n < 3.3 × 10¹⁴. Beyond that it's a very high-probability test.

Why is the factor missing for huge composites?

We cap trial division at 10⁶ to stay snappy. For hard factoring use a CAS like SageMath.

What if I paste negative numbers?

We reject them — primality is only defined for n ≥ 2.

Why is 1 not prime?

By convention, primes are integers > 1. The fundamental theorem of arithmetic requires excluding 1.

Is anything sent to a server?

No — every check runs locally in your browser using native BigInt.

Suggest a tool

Something missing?

Tell us what you need. We ship the top requests every two weeks.

47 in queue·8 shipped this month

Request queued. Thanks!