[spacemonkey92]

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?

[eru]

I'm not sure what you mean by predicting prime numbers?

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.

[fragmede]

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.

[jdewerd]

I thought Shor's algorithm could attack ECC too and the lattice crypto with the sci-fi crystal names (Kyber and Dilithium) was the response?

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.

[bux93]

It's new so they are layering it up. At https://pq.cloudflareresearch.com/ you can also see if your browser supports X25519MLKEM768, the X25519Kyber512Draft00 and X25519Kyber768Draft00 variants are deprecated ('obsolete'?)

[ndsipa_pomu]

We also have cryptography that uses elliptic curves rather than large primes.