Ciro Santilli @cirosantilli 37

Answers suggest hat you basically pick a random large odd number, and add 2 to it until your selected primality test passes.

The prime number theorem tells us that the probability that a number between 1 and $N$ is a prime number is $1/log(N)$.

Therefore, for an N-bit integer, we only have to run the test N times on average to find a prime.

Since say, A 512-bit integer is already humongous and sufficiently large, we would only need to search 512 times on average even for such sizes, and therefore the procedure scales well.