* 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)