About

A miscounted prime breaks RSA key generation. A wrong factorization invalidates a cryptographic proof. This tool applies the deterministic Miller-Rabin primality test with witness set [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37] to produce a guaranteed correct result for any integer n < 3.317 × 10²⁴. For composite inputs, the tool returns the complete prime factorization via trial division combined with Pollard's Rho algorithm. Results are deterministic, not probabilistic. The tool handles arbitrarily large integers through JavaScript BigInt arithmetic.

Limitation: for integers exceeding 10¹⁸, factorization of large composite numbers may take several seconds if the number has two very large prime factors. The primality verdict itself remains instant regardless of size. Pro tip: when verifying Mersenne primes of the form 2^p − 1, first confirm that p itself is prime.

Formulas

The Miller-Rabin test expresses n − 1 as 2^s ⋅ d where d is odd, then checks witnesses:

n − 1 = 2^s ⋅ d

For each witness a, compute:

x = a^d mod n

If x = 1 or x = n − 1, the number passes for this witness. Otherwise, square x up to s − 1 times:

x ← x² mod n

If x never reaches n − 1, then n is composite. The Prime Number Theorem gives the approximate count of primes below n:

π(n) ≈ nln(n)

Where π(n) is the prime-counting function and ln is the natural logarithm. For factorization of composite numbers, Pollard's Rho uses the iteration x ← x² + c mod n with Floyd's cycle detection to find gcd(|x − y|, n) > 1.

Reference Data

Range	Count of Primes	Prime Density	Largest Prime in Range
1 - 10	4	40.0%	7
1 - 100	25	25.0%	97
1 - 1,000	168	16.8%	997
1 - 10,000	1,229	12.29%	9,973
1 - 100,000	9,592	9.59%	99,991
1 - 1,000,000	78,498	7.85%	999,983
1 - 10,000,000	664,579	6.65%	9,999,991
1 - 10⁸	5,761,455	5.76%	99,999,989
1 - 10⁹	50,847,534	5.08%	999,999,937
1 - 10¹⁰	455,052,511	4.55%	9,999,999,967
Notable Primes
Largest known twin prime	2,996,863,034,895 × 2^1,290,000 ± 1 (388,342 digits)
Largest known Mersenne prime	2^136,279,841 − 1 (41,024,320 digits, M52)
First 20 primes	2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71
Mersenne exponents	2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607
Fermat primes (known)	3, 5, 17, 257, 65537

Frequently Asked Questions

The probabilistic Miller-Rabin test uses random witnesses and has a false-positive rate of at most 1/4 per witness. The deterministic variant uses a fixed, proven set of witnesses. For n < 3.317 × 10²⁴, the witness set {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37} produces zero false positives. The result is guaranteed correct, not probable.

The Fundamental Theorem of Arithmetic states every integer greater than 1 has a unique prime factorization. If 1 were prime, uniqueness would break: 6 = 2 × 3 = 1 × 2 × 3 = 1² × 2 × 3. Excluding 1 preserves this theorem.

Primality testing runs in polynomial time. Miller-Rabin with k witnesses performs O(k ⋅ log²n) modular multiplications. Integer factorization has no known polynomial-time algorithm on classical computers. Trial division is O(√n). Pollard's Rho achieves expected O(n^1/4) for finding a factor.

Yes. The tool uses JavaScript BigInt for arbitrary-precision arithmetic. The primality test completes in milliseconds for numbers up to several hundred digits. Factorization of composite numbers with large prime factors may take longer. If both prime factors exceed 10⁹, the Pollard's Rho step could take seconds to minutes depending on factor size.

The Prime Number Theorem states π(n) ≈ n ÷ ln(n). At n = 10⁶, roughly 7.85% of integers are prime. At n = 10⁹, it drops to 5.08%. The gap between consecutive primes grows logarithmically on average, but arbitrarily large gaps exist (proven by the Green-Tao theorem context and prime gap results).

2 is correctly identified as the smallest and only even prime. 0 and 1 return "not prime" with an explanation. Negative numbers and non-integer inputs are rejected with a validation error. The tool only accepts positive integers ≥ 0.