Is it prime?

A whole number, or a form like 2^89-1

 Check it

91561172979191,000,000,0072^89 − 11A random one

Nothing you type here leaves your browser. The number goes in the page address only if you share it.

Type a number of up to 300 digits and this prime number checker tells you whether it's prime. If it isn't, you get its prime factors. For any number, you also get the primes on either side of it and a list of every curious property it has. The check is exact for numbers below 3.3 × 10²⁴. Above that it's a test that no composite number is known to fool in practice. Everything runs in your browser, with no server involved.

What counts as a prime

A prime is a whole number greater than 1 whose only divisors are 1 and itself. The first few are 2, 3, 5, 7, 11 and 13, and there are 25 below 100, 9,592 below 100,000 and 78,498 below a million (scripts/examples/primes-personality.mjs counts them with the same sieve the sieve page animates). A number greater than 1 that isn't prime is composite, and the fundamental theorem of arithmetic says each composite number is a product of primes in exactly one way, apart from the order. That uniqueness is why mathematicians settled the question of 1.

Why 1 isn't prime

If 1 were prime, then 6 = 2 × 3 = 1 × 2 × 3 = 1 × 1 × 2 × 3, and "the" prime factorization of 6 wouldn't exist. Rather than add "except for ones" to every theorem, the convention is that a prime must have exactly two divisors, and 1 has one. It wasn't always the rule. Chris Caldwell and Yeng Xiong's 2012 history, What is the smallest prime?, follows how the answer moved over the centuries as the idea of a number changed. Zero isn't prime either. Every number divides it, so it has far more than two divisors.

How the check works

For small numbers the page divides by the small primes, which settles most of them at once. Anything that survives goes through the Miller–Rabin test. Write n − 1 as 2^s · d with d odd, pick a base a, and compute a^d modulo n, then square it up to s times. If n is prime, the sequence must either start at 1 or hit −1 (that is, n − 1) before it ends. If it does neither, a is a witness: a number that proves n is composite without giving a single factor. Try 561 or 1105 in the box above and the card names the witness it found.

A single base can be fooled by a composite number, so the page tries 13 bases, the first 13 primes (2 through 41). Gerhard Jaeschke worked out in 1993 that the first few primes are enough for small numbers, and Jonathan Sorenson and Jonathan Webster showed in 2015 that no composite number below 3,317,044,064,679,887,385,961,981 passes all of the first 13. Their search found that the smallest composite that passes the first 12 is 318,665,857,834,031,151,167,461. Base 41 catches it, and this site's tests check exactly that. Above that bound the 13 bases are no longer a proof. Nobody has ever found a composite that slips through all of them, and for random inputs the chance is astronomically small, so the card says "probable prime" and means it carefully. On the RSA key-size page you can generate 1,024-bit probable primes and see how real software does the same.

Factoring is a different and harder job than testing. To factor, the page tries Pollard's rho (in Richard Brent's faster form), which finds a factor p in about the square root of p steps. That's quick when the smallest factor has fewer than about 10 digits, and hopeless for the two 150-digit primes of a real RSA key. When the page gives up, it says so and shows what it did find. Telling prime from composite is easy, while finding the factors of a composite is the problem RSA's security rests on. The RSA toy lets you watch that gap at small scale.

What the labels mean

Below the verdict, the card lists everything it knows about your number, and each label opens to its definition. Here are the first few numbers for each, computed by the page's own code (scripts/examples/primes-personality.mjs):

Two of these have stories. Sophie Germain used her primes in the early 1800s in a partial attack on Fermat's Last Theorem, and the safe-prime form matters for Diffie–Hellman, where a group built on a safe prime has no small subgroups for an attacker to exploit. And 1729 is the number G. H. Hardy said he found dull on a taxi ride to visit the hospitalized Ramanujan, who replied that it was the smallest number that is the sum of two cubes in two ways (1³ + 12³ and 9³ + 10³). The card finds both, and it also marks 1729 as a Carmichael number.

Carmichael numbers: composites that look prime

Fermat's little theorem says that if n is prime then aⁿ⁻¹ ≡ 1 (mod n) for every a not divisible by n. It's tempting to use that as a primality test, and for most composites it works. Carmichael numbers are the composites that pass it for every base coprime to them, the smallest being 561 = 3 × 11 × 17. Korselt's criterion characterizes them: the number is squarefree, and for each prime factor p, p − 1 divides n − 1. For 561, 2, 10 and 16 all divide 560. In 1994 Alford, Granville and Pomerance proved there are infinitely many. Miller–Rabin is stronger than the plain Fermat test and sees through every one of them, which is why the quiz on the prime-or-not page ends with them.

Where prime testing shows up in cipher.ink

It doesn't, in the product. A message you seal here uses AES and PBKDF2, and neither involves a prime (AES-GCM, PBKDF2). The primes on this site belong to the public-key side of the story. RSA, Diffie–Hellman and ElGamal all start by finding large primes, and the test you just used is the one browsers and OpenSSL run to find them.

Common questions