Prime Number Tester

What This Tool Does

This tool determines whether any integer is prime, finds the next or previous prime in either direction from a given value, and factorizes composite numbers into their unique prime decomposition. It accepts arbitrary-precision input through JavaScript's BigInt type, so there is no practical upper bound on what you can test — 1024-bit, 2048-bit, or even larger integers all return results in milliseconds. For small numbers (below roughly 10^15) the tool uses straightforward trial division up to the square root of the candidate; for larger numbers it switches to the Miller-Rabin probabilistic primality test with a deterministic witness set of the first twelve primes.

The deterministic witness set {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37} has been mathematically proven sufficient to correctly classify every composite integer below 3,317,044,064,679,887,385,961,981 (approximately 3.3 x 10^24), which exceeds 81 bits — well beyond any input a user is likely to enter directly. For inputs above that bound the test technically becomes probabilistic, but the error probability with twelve independent bases is bounded above by 4^-12, less than one chance in sixteen million, and no known composite passes all twelve bases. Every computation runs client-side; no value you enter is logged, transmitted, or stored anywhere outside your local browser session.

How to Use It: Test, Generate, and Factorize

The interface has three modes, switched via the chip row at the top: Test, Generate, and Factorize. Each one targets a different common primality task.

Test Mode

Enter any integer into the input field and press Test (or hit Enter). The result panel reports either PRIME in green or COMPOSITE in red, along with the digit count and the elapsed runtime in milliseconds. For composite results, the panel also shows the full prime factorization as a witness — so you don't just learn that the number is composite, you see the divisors that make it so. The Previous Prime and Next Prime buttons walk through the prime sequence in either direction, which is useful for finding primes near a target value (common when picking key generation seeds, hash table sizes, or modular arithmetic parameters).

Generate Mode

Set a count between 1 and 200 and press Generate. The tool emits the first N primes starting from 2, listed in ascending order separated by commas. The Copy button copies the comma-separated list to your clipboard — paste into a spreadsheet, a test fixture, or a math homework answer key. The Sieve of Eratosthenes would be faster for generating a contiguous range, but for short sequences a per-candidate Miller-Rabin check is more than sufficient and avoids needing to preallocate an array sized to the largest expected prime.

Factorize Mode

Enter a composite (or prime) integer and press Factorize. The tool returns the complete prime factorization — every prime divisor with its multiplicity. The result panel shows both the flat list of factors (12 = 2 · 2 · 3) and the exponent form (12 = 2^2 · 3). For small numbers this is instant; for larger composites with a small smallest prime factor, the trial-division loop finishes in milliseconds. Note that factorization of a hard semiprime — the product of two large primes of similar size, the structure RSA relies on — would take longer than the age of the universe with this tool's algorithm, which is exactly why RSA's security holds.

Common Use Cases: Cryptography, Sieves, and Math Verification

RSA and Public-Key Cryptographic Key Generation

RSA key generation requires picking two large primes p and q, typically each at least 1024 bits for a 2048-bit modulus. Libraries like OpenSSL and Go's crypto/rsa generate random odd candidates with high bits set, sieve away those divisible by small primes (cutoff usually around 2,000), then run Miller-Rabin with the FIPS 186-5-recommended round count. The prime number theorem says the density of primes near a 1024-bit integer is roughly 1 / (1024 · ln 2), or about one in 710, so expect to test several hundred candidates before finding a prime of the target size. This tool will not generate cryptographic-grade primes — entropy quality and constant-time arithmetic both matter for security — but it lets you verify that a given primality result holds for known constants and reference values.

Diffie-Hellman Safe Prime Verification

Classical (finite-field) Diffie-Hellman requires a safe prime p = 2q + 1 where q is also prime. RFC 7919 standardizes a fixed set of pre-computed safe primes (ffdhe2048, ffdhe3072, ffdhe4096, ffdhe6144, ffdhe8192) for TLS use, all derived from the same construction. You can paste any of those into this tool, confirm it tests prime, then test (p - 1) / 2 to confirm the Sophie Germain partner — verifying that a primes-from-standards constant actually matches its specification, which is good operational hygiene before deploying it in production.

Sieve of Eratosthenes Implementations

If you are implementing a sieve in any language — JavaScript, Rust, Python, C — this tool serves as a correctness oracle. Run your sieve up to N, then spot-check your output against the first N primes from Generate mode. Verify boundary cases (does your sieve correctly emit 2, 3, 5, 7?), confirm the largest prime in your output is the expected one (nth_prime(1000) = 7919, which is the default input value in this tool), and check the count. The Sieve of Eratosthenes is asymptotically faster than per-candidate primality testing when you need all primes up to a bound, but a primality tester is essential for spot-checking and for cases where you only need to test specific numbers.

Hash Table Size Selection

Hash tables that use modular reduction (index = hash(key) mod table_size) work best with prime table sizes because primes lack the small factors that cause clustering when hash functions have small periods. The historical reference here is Knuth's The Art of Computer Programming, Volume 3, which recommends primes for closed-addressing hash tables. Use this tool to find primes near your target table capacity. For a target of 10,000 buckets, the nearest prime above is 10,007; the nearest below is 9,973. Type 10000 into the input and press Next Prime or Previous Prime to navigate.

Mathematics Coursework and Number Theory Exploration

Students working through number theory exercises can verify primality of specific values, identify pseudoprimes, explore Mersenne primes and twin primes, and confirm hand-computed factorizations. The Fibonacci Generator is a useful companion when exploring number-theoretic identities — for example, the Fibonacci primality test (a fast probabilistic test based on Lucas sequences) is part of the BPSW algorithm. The Digital Root Calculator helps verify divisibility rules: a number is divisible by 3 if and only if its digital root is 3, 6, or 9, which is sometimes the fastest first-pass composite check by hand.

Edge Cases and Algorithmic Subtleties

A handful of mathematical facts and algorithmic behaviors are worth knowing before drawing strong conclusions from a primality test result.

Carmichael numbers fool pure Fermat tests, but not Miller-Rabin. A Carmichael number is a composite n satisfying a^(n-1) = 1 (mod n) for every base a coprime to n. The smallest is 561 = 3 · 11 · 17; others include 1105, 1729, 2465, 2821, 6601, and 8911. A pure Fermat primality test cannot distinguish these from genuine primes — it returns "probably prime" for any base coprime to n. Miller-Rabin avoids the Carmichael trap by checking the stronger condition that a^d = 1 or a^(2^i · d) = -1 (mod n) during the squaring chain. For every Carmichael number, at least three quarters of all bases in [2, n-1] are Miller-Rabin witnesses of compositeness — which is the entire reason Miller-Rabin replaced naive Fermat in production cryptography.

Deterministic Miller-Rabin bases work below specific bounds. The witness set {2} alone is sufficient for n < 2,047. The set {2, 3} works for n < 1,373,653. The set {2, 3, 5} covers n < 25,326,001. The set {2, 3, 5, 7} handles n < 3,215,031,751. The full set {2, 3, 5, 7, 11, 13} deterministically classifies every n < 3.3 x 10^14. Adding witnesses up through 37 extends deterministic correctness to n < 3.3 x 10^24. These bounds were established by Pomerance, Selfridge, and Wagstaff (1980) and extended by Jaeschke (1993) and Sorenson (2017). The tool uses the twelve-prime set for full coverage up to the 3.3 x 10^24 bound.

AKS is deterministic and polynomial-time, but slow in practice. The Agrawal-Kayal-Saxena algorithm (2002) is the first primality test that is simultaneously deterministic, polynomial-time, and unconditional. Its theoretical significance is enormous — it definitively placed PRIMES in the complexity class P. In practice, however, AKS's original runtime bound was O(log(n)^7.5), later improved by Lenstra and Pomerance to roughly O(log(n)^6). Both are orders of magnitude slower than Miller-Rabin or BPSW for any input you would actually encounter. No production cryptographic library uses AKS — they all use Miller-Rabin or BPSW. AKS matters theoretically; it does not matter practically.

p - 1 and p + 1 factoring methods exploit special structure. Pollard's p - 1 algorithm (1974) factors n efficiently when n has a prime factor p such that p - 1 is "smooth" — i.e., all of its prime factors are below some small bound B. Williams' p + 1 method (1982) does the same for primes where p + 1 is smooth. This is precisely why cryptographic primes generated for RSA include a "strong prime" check: p - 1 must have a large prime factor (a Sophie Germain partner), p + 1 must have a large prime factor, and p - 1's largest prime factor must itself have a large prime factor minus one. Production libraries do this strong-prime filtering after Miller-Rabin succeeds.

Lucas-Lehmer is the test for Mersenne primes. A Mersenne number has the form M_p = 2^p - 1 for prime p. The Lucas-Lehmer test is a deterministic primality test specialized for Mersenne numbers: define s_0 = 4 and s_{i+1} = s_i^2 - 2 (mod M_p); then M_p is prime if and only if s_{p-2} = 0 (mod M_p). This is the algorithm GIMPS (the Great Internet Mersenne Prime Search) uses to find the largest known primes — including M_82589933, a 24,862,048-digit Mersenne prime found in 2018. The tool here uses general-purpose Miller-Rabin rather than Lucas-Lehmer, so it can test any prime candidate, not just Mersenne candidates, but it is correspondingly slower for the very largest Mersenne numbers.

BPSW (Baillie-PSW) is the gold-standard probabilistic test. The combined Baillie-PSW algorithm runs a Miller-Rabin test with base 2, then a strong Lucas pseudoprime test using carefully selected parameters. No composite under 2^64 has ever been observed to pass BPSW, and a $620 prize has stood unclaimed since 1980 for any counterexample. Many production libraries (GMP's mpz_probab_prime_p, SymPy's isprime) use BPSW because in practice it appears deterministic, even though no proof of correctness exists. This tool uses the simpler twelve-prime deterministic Miller-Rabin set, which is provably correct below 3.3 x 10^24 and adequate for browser-side input sizes.

Behind the Scenes: From Fermat to AKS

Fermat's Little Theorem: The Foundation

Every modern primality test traces back to Fermat's little theorem (1640): if p is prime and a is any integer not divisible by p, then a^(p-1) = 1 (mod p). The contrapositive yields a primality test: pick a base a, compute a^(n-1) mod n, and if the result is not 1, then n is definitely composite. Unfortunately the converse fails — there exist composite n for which a^(n-1) = 1 (mod n) for every a coprime to n. Those are the Carmichael numbers, and they are precisely the reason Miller-Rabin was developed.

Miller (1976) and Rabin (1980)

Gary L. Miller's 1976 paper "Riemann's Hypothesis and Tests for Primality" proposed a deterministic primality test based on the Extended Riemann Hypothesis (ERH): if ERH holds, the test runs in polynomial time. Michael O. Rabin then converted Miller's test into a probabilistic algorithm (1980, "Probabilistic Algorithm for Testing Primality"), removing the dependence on ERH at the cost of a small false-positive probability. The Rabin probabilistic version is what every modern crypto library implements: pick k random witnesses; if all of them pass, accept the number as probably prime with error bounded by 4^-k.

Agrawal-Kayal-Saxena (2002): PRIMES is in P

The original Agrawal-Kayal-Saxena paper "PRIMES is in P" (Annals of Mathematics, 2004; preprint 2002) was a landmark result. Three computer science researchers — Manindra Agrawal and his students Neeraj Kayal and Nitin Saxena at IIT Kanpur — proved that primality testing can be done deterministically in polynomial time, without invoking ERH or any other unproven assumption. The AKS test is based on the algebraic identity that n is prime if and only if (x + a)^n = x^n + a (mod n, x^r - 1) for suitable a and r. The original time complexity was O(log(n)^7.5); later improvements by Lenstra and Pomerance pushed it down to roughly O(log(n)^6). AKS is rarely used in practice because Miller-Rabin and BPSW are vastly faster, but its theoretical impact on complexity theory is permanent.

Sieve of Eratosthenes: Still the Fastest for Ranges

For enumerating all primes up to N the Sieve of Eratosthenes (circa 240 BCE) remains the fastest practical method, with time complexity O(N log log N) and space complexity O(N). The Sieve of Atkin (Atkin and Bernstein, 2003) achieves a slight asymptotic improvement to O(N / log log N) but with significantly higher constant factors, so it only beats Eratosthenes for genuinely huge N. Segmented sieves (sieving small ranges of k · √N at a time) reduce memory pressure dramatically — useful when enumerating primes in the gigabyte range. This tool uses per-candidate Miller-Rabin rather than a sieve for the Generate mode because most users want fewer than 200 primes, where sieve overhead dominates.

Production Implementations: GMP, OpenSSL, and Beyond

GNU Multiple Precision Arithmetic Library (GMP) exposes mpz_probab_prime_p(n, reps), which runs a BPSW combination plus an optional reps additional Miller-Rabin rounds with random bases. OpenSSL's BN_is_prime_fasttest_ex in crypto/bn/bn_prime.c follows the same general structure: trial-divide by small primes, then Miller-Rabin with FIPS 186-5 round counts. Python's SymPy exposes sympy.isprime, which uses BPSW for inputs under 2^64 and adds extra Miller-Rabin rounds beyond that. The gmpy2.is_prime wrapper exposes GMP's routine to Python. Each of these libraries embodies decades of cryptographic engineering experience; for production work, prefer them over any browser-side implementation.

Comparison: This Tool vs. WolframAlpha vs. CLI Tools

Several mature primality testers are available, each with different strengths. The choice depends on input size, required accuracy, throughput, and whether you need a tool inside an existing pipeline or just a one-off check.

For a quick browser check during development this tool is ideal — no install, no network round-trip, results in milliseconds. For high-throughput crypto workloads (key generation, certificate validation), prefer OpenSSL or a language-level wrapper around GMP. For mathematical research that requires a primality certificate verifiable independently of the testing algorithm, use PARI/GP with isprime(n, 1) or run a dedicated ECPP implementation.

Related Tools

Primality testing rarely happens in isolation — it usually sits inside a larger number-theoretic or cryptographic workflow. The Fibonacci Generator emits the Fibonacci sequence, which is closely linked to primality through the Lucas primality test and BPSW. The Digital Root Calculator implements the divisibility rule for 9 (and indirectly for 3) — useful as a first-pass composite check by hand before reaching for a calculator. The Math Expression Evaluator handles general-purpose arithmetic when you need to compute something like (p - 1) / 2 as a Sophie Germain partner check.

For cryptographic workflows, the Hash Generator produces SHA-256 and other digests via the Web Crypto API, which is useful when generating seeds for primality candidates. The UUID Generator emits cryptographically random identifiers — same underlying entropy concern. If you are working with bitwise primality tricks (Miller-Rabin's squaring chain decomposes n - 1 as 2^r · d), the Bitwise Calculator can compute the bit length and trailing zeros of any BigInt to confirm r and d by hand.