11–20 of 42 posts
2^255-19
This is where Curve 25519 and the associated cryptography (ed25519, x25519) gets its name from. Written out, 2^255-19=57896044618658097711785492504343953926634992332820282019728792003956564819949.
The 50 000 000th prime is 982451653, but fun fact: you may have already memorized a prime much larger than this without even realizing you have done so! 2^255-19 This is where Curve 25519 and the associated cryptography (ed25519, x25519) gets its name from. Written out, 2^255-19=57896044618658097711785492504343953926634992332820282019728792003956564819949.
I wonder what would happen if someone discovered an efficient algorithm for finding or predicting prime numbers or their factors. It would put the fundamentals of internet security at risk and likely much more. Has anyone ever considered a plan B for such a scenario?
The 50 000 000th prime is 982451653, but fun fact: you may have already memorized a prime much larger than this without even realizing you have done so! 2^255-19 This is where Curve 25519 and the associated cryptography (ed25519, x25519) gets its name from. Written out, 2^255-19=57896044618658097711785492504343953926634992332820282019728792003956564819949.
You could have memorized even large one if you are familiar with the full name of the Mersenne Twister PRNG: MT19937 is named so because its period is 2^19937-1 which is a prime number (in fact, the largest known one at the time of Zigler's writing). In my knowledge any larger prime number hasn't been used for the practical purpose.
I was going to include the digits for comparison, but yes, on second thought 6002 digits is probably too much for polite inclusion in a HN post.
I wonder what would happen if someone discovered an efficient algorithm for finding or predicting prime numbers or their factors. It would put the fundamentals of internet security at risk and likely much more. Has anyone ever considered a plan B for such a scenario?
Yes. Shor's algorithm on quantum computers represents such a theoretical possibility, so the industry is moving to resistant algorithms that aren't based on products of large primes such as elliptic curve cryptography.
If I go to https://www.google.com using Chrome and Inspect > Security, I see it is using X25519Kyber768Draft00 for key exchange. X25519 is definitely ECC and and Kyber is being used for key encapsulation (per a quick google). I don't know to what extent it can be used independently vs it's new so they are layering it up until it has earned the right to stand on its own.
I wonder what would happen if someone discovered an efficient algorithm for finding or predicting prime numbers or their factors. It would put the fundamentals of internet security at risk and likely much more. Has anyone ever considered a plan B for such a scenario?
It's very, very easy to find big prime numbers: you generate a random number in the range that you are interested in, and then check whether it's prime. Repeat until you find a prime; they are fairly dense (a random number `n` has about a 1/log(n) chance of being prime) so you don't have to try too often.
In fact, that's how we find big primes for creating things like RSA key-pairs.
Testing a number for primality can also be done fairly quick. In general, much, much faster than finding the factors of a composite number. See https://en.wikipedia.org/wiki/Primality_test
> Has anyone ever considered a plan B for such a scenario?
Yes, quantum resistance cryptography is a thing. See the other comments.
[flagged]
Earlier quoted context omitted.
You could have memorized even large one if you are familiar with the full name of the Mersenne Twister PRNG: MT19937 is named so because its period is 2^19937-1 which is a prime number (in fact, the largest known one at the time of Zigler's writing). In my knowledge any larger prime number hasn't been used for the practical purpose.
Cool, I hadn't run into it before so thanks for introducing me! I was going to include the digits for comparison, but yes, on second thought 6002 digits is probably too much for polite inclusion in a HN post.
Here we are with many orders of magnitude of computing power that we have to ourselves, 24/7, and mostly we're using all that power to browse the Internet :P
Calculating the first 50,000,000 primes takes less than ten minutes (using no memory - that is, not a sieve). The 50,000,000th prime, BTW, is 982,451,653. I wonder what the author of this paper would've been able to do with the kind of processing available to us.