Prime Number
A prime number is a natural number greater than 1 divisible only by 1 and itself; it is the building block of number theory, and every integer factors uniquely into primes.
Purpose
To serve as the building blocks of integers, the basis of number theory and cryptography (RSA).
Mechanism
A natural number greater than 1 whose only divisors are 1 and itself. Fundamental theorem of arithmetic: every integer factors uniquely into primes. Primality tests: trial division, Miller-Rabin (probabilistic), AKS (deterministic but slow). There are infinitely many primes (Euclid's proof).
Use cases
- RSA key generation
- Diffie-Hellman parameters
- Prime hash table capacities
- Number theory research
Examples
- Input
The first 10 primesOutput2,3,5,7,11,13,17,19,23,292 is the only even prime
Common errors
- Using small primes for RSA moduli
- Use large primes (≥1024 bits)
Related terms
Modular Arithmetic
Modular arithmetic takes remainders after integer operations, keeping results within [0, n); it is the foundation of number theory and cryptography. GLOSSARY
BigInteger
BigInteger is an arbitrary-precision integer type, not limited by a fixed word size, used for computations beyond the native integer range (such as cryptography and combinatorics). GLOSSARY
GCD
The GCD (greatest common divisor) is the largest positive integer that divides two or more integers, computed efficiently with the Euclidean algorithm. GLOSSARY