= How large primes are found for RSA
* 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.
Back to article page