Ciro Santilli
🔗

How large primes are found for RSA | 🗖 nosplit | ↑ parent "RSA" | 105

🔗
🔗
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 is a prime number is .
🔗
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.
🔗
🔗