Prime Generation

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

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 ~1 in ln(2^1024) ≈ 1 in 710 random odd numbers near 2^1024 is prime. So expect ~700 attempts.

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.