Re:All Mersenne prime exponents below 100m tested at least once
by IvyMike on Friday December 04, 2020 @04:59PM
(#25308716)
> ...nor are they so numerous that iterating over them is computationally difficult
That's not correct; for a given bound x, the expected number of primes is x/ln(x).
For example, if you need to choose a prime of 100 digits, there are something like 10^96 of them; you can find a random one using probabilistic methods, do your cryptography, and know that your attacker would have to try 10^96 primes to break it. Since they can't really do this, this is not the weak point of your cryptosystem.
If you chose a Mersenne prime, there are only 51 of them. Your attacker would have to try less than 10^2 of them.
That's not correct; for a given bound x, the expected number of primes is x/ln(x).
For example, if you need to choose a prime of 100 digits, there are something like 10^96 of them; you can find a random one using probabilistic methods, do your cryptography, and know that your attacker would have to try 10^96 primes to break it. Since they can't really do this, this is not the weak point of your cryptosystem.
If you chose a Mersenne prime, there are only 51 of them. Your attacker would have to try less than 10^2 of them.