What are the two methods for finding large primes, and how does the probabilistic method (Miller-Rabin) work?

The deterministic method constructs primes using formulas (fast but no formula generates ALL primes). The probabilistic method tests random candidates with Miller-Rabin (slower but reliable).

* Generating a large prime: pick a random odd candidate, screen it against small primes, then run Miller-Rabin — 'not prime' is certain, 'prime' is 99.9% per round, so a few rounds make a false positive vanish. *

Deterministic method:

• Use a formula like Euler's: $f(n) = n^2 + n + 41$ (produces primes for $n = 0$ to $39$, then sometimes composites)
• Very fast, but no formula generates all primes
• Must ensure the chosen primes appear random (not predictable)

Probabilistic method (Miller-Rabin):

1. Pick a random odd number of the desired size
2. Check gcd with the first ~50 small primes (quick filter)
3. If gcd = 1, run primality tests

• If the test says "not prime" → definitely composite
• If the test says "prime" → probably prime (99.9% per test)
• After 5 tests: false positive probability = $(1/1000)^5 = 10^{-15}$ — one in a quadrillion
• After 10 tests: $10^{-30}$ — effectively certain

Practical note: This isn't very fast (several primality tests per candidate), but you only generate primes once per key — typically once per user.

Go deeper:

• Miller-Rabin primality test (Wikipedia) — the actual test behind the 'probably prime' verdict.