Determine if any integer is prime using a deterministic Miller–Rabin primality test. Get prime factorization, find the next prime, and explore the fascinating world of prime numbers.
A prime number is a natural integer greater than 1 that has no positive divisors other than 1 and itself. The fundamental theorem of arithmetic states that every integer greater than 1 can be uniquely represented as a product of primes. This makes primes the "atoms" of arithmetic — the building blocks of all numbers. Euclid's ancient proof (c. 300 BCE) demonstrated that there are infinitely many primes, a result that still resonates across modern mathematics.
A number \( n > 1 \) is prime if for every integer \( d \) with \( 1 < d < n \), \( d \nmid n \).
Equivalently: \( \tau(n) = 2 \), where \( \tau(n) \) is the number of positive divisors.
This tool implements a deterministic Miller–Rabin primality test for 64-bit integers (up to 264), extended with a probabilistic fallback for larger BigInt values. Miller–Rabin is based on Fermat's little theorem and efficiently detects composite numbers with high certainty. For numbers below 264, we use a fixed set of bases that provably eliminate false positives: [2, 325, 9375, 28178, 450775, 9780504, 1795265022]. This deterministic base set is based on the work of Jaeschke (1993) and Sinclair (2011). For larger inputs, the test runs with 12 fixed bases providing an error probability below 2-24 — astronomically reliable for practical purposes.
The factorization module uses trial division by cached primes up to 1,000,000. For any remaining cofactor greater than 1, a Miller-Rabin test is applied to determine if it is prime or composite. For numbers smaller than 1012, full factorization is typically displayed; for larger numbers, we show discovered factors and report the primality status of the remaining cofactor.
The Miller–Rabin test works by writing \( n-1 = d \cdot 2^s \) and checking whether \( a^d \equiv 1 \pmod{n} \) or \( a^{d \cdot 2^r} \equiv -1 \pmod{n} \) for some \( r \). If neither holds, \( n \) is composite. For 64-bit numbers, the deterministic base set above guarantees correctness. This implementation follows the guidelines from NIST FIPS 186-5 (Appendix C) for probabilistic primality testing. For larger BigInts, we implement modular exponentiation via exponentiation by squaring.
Factorization is performed by trial division using a cached sieve of Eratosthenes for primes up to 1 million. If a cofactor remains after trial division, its primality is determined via Miller-Rabin. The next prime function increments the input until a prime is found, using the same Miller–Rabin test with early exit.
RSA encryption requires two large random primes (typically 1024–4096 bits). Using a deterministic primality test ensures the generated numbers are genuinely prime, preventing catastrophic factorization attacks. Our Miller–Rabin implementation with high certainty mirrors industrial standards (e.g., OpenSSL, cryptlib).
Step-by-step example:
This tool allows students and developers to prototype and understand the fundamental building blocks of public-key cryptography.
| Category | Example / Value | Notes |
|---|---|---|
| Smallest prime | 2 | Only even prime |
| Largest known prime (2026) | 2136279841 - 1 | Mersenne prime, 41,024,320 digits (GIMPS) |
| Twin primes | (41, 43), (107+ 1, 107+3) | Infinitely many conjectured but unproven |
| Prime gap below 1018 | 1550 | See OEIS A005250 |
| Fermat prime | 65537 | Largest known Fermat prime, used in RSA |
The Prime Number Theorem (PNT) states that the density of primes around \( x \) is approximately \( \frac{1}{\ln x} \). Formally, \( \pi(x) \sim \frac{x}{\ln x} \), where \( \pi(x) \) counts primes ≤ x. This tool helps verify prime occurrence empirically by testing consecutive numbers. For example, near 1,000,000, roughly 1 in 14 numbers is prime, aligning with 1/ln(10^6) ≈ 1/13.8.