A prime number is an integer greater than one with exactly two distinct positive divisors: 1 and itself. Numbers that can be decomposed further are composite. section 8.2.1
Prime numbers are fundamental building blocks of asymmetric cryptography. Their importance comes from integer factorization: multiplying two large primes is easy, while recovering those primes from their product is computationally expensive. section 8.2 section 8.3.2
Cryptographic prime generation follows a random-candidate-and-test loop:
- Generate random bytes with an RNG and interpret them as an arbitrary-precision integer. section 8.2.2
- Test the candidate for primality; reject composite values and repeat until a prime is found. section 8.2.2
- Use sufficiently large primes in asymmetric key generation, where repeated testing reduces the chance that a candidate is composite. section 8.2.2 section 8.5
Factoring a composite number
The number 764,512 decomposes as 3,413 × 7 × 2⁵. This illustrates the fundamental theorem of arithmetic: every positive integer has a unique representation as a product of prime factors. section 8.2.1
