* https://crypto.stackexchange.com/questions/1970/how-are-primes-generated-for-rsa
* https://crypto.stackexchange.com/questions/690/can-i-select-a-large-random-prime-using-this-procedure/693#693

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.


Discussion on "How large primes are found for RSA" by Ciro Santilli (@cirosantilli, 34)