On a related note, the Rabin-Miller primality test is needed just to find the primes for RSA to work.