That doesn't quite generate a prime. It generates a number that's a prime with a very high probability. There's always a small chance that it's not prime but

That doesn't quite generate a prime. It generates a number that's a prime with a very high probability. There's always a small chance that it's not prime but it's good enough given the tradeoffs needed to verify that it's prime with 100% certainty.