Prime Generation

RSA needs LARGE prime numbers. For RSA-2048, two ~1024-bit primes.

Why prime, specifically? Because the private exponent d is the inverse of e modulo phi(n), and the tidy formula phi(n) = (p-1)(q-1) holds only when p and q are prime. Choose composite factors and you cannot compute phi(n) without factoring them first -- which is the very problem RSA's security assumes nobody can do.

How to find them?

1. Generate a random odd 1024-bit number.
2. Test if it's prime. If yes, you have one.
3. Else, increment by 2 and retry.

The prime number theorem says primes near 2^1024 have density 1/ln(2^1024), about 1 in 710. But you never test an even candidate, and every prime above 2 is odd -- so among odd candidates the density doubles to 2/ln(2^1024) and you should expect about 355 tries, not 710. Real generators do better still by sieving out multiples of 3, 5, 7, ... before paying for the expensive test.

Testing primality:

Trial division is slow: O(sqrt(n)) divisions. For 1024-bit n, sqrt(n) ≈ 2^512 — billions of years.

Miller-Rabin is the practical choice: probabilistic test in O((log n)^3) time per witness:

Each witness has at most 1/4 chance of being a "false witness". With 20 witnesses, probability of declaring composite as prime is < 2^-40.

Crypto libraries combine Miller-Rabin with deterministic small-prime trial division for speed.