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.

- RSA | 211, 364, 2
- Public-key cryptography | 21, 486, 8
- Cryptography | 0, 647, 31
- Computer science | 240, 3k, 72
- Computer | 136, 23k, 582
- Technology | 0, 38k, 897
- Ciro Santilli's Homepage | 244, 174k, 3k

- RSA | 211, 364, 2