3 ms·
There are too many. Not just more than could fit in every database on Earth. More than could fit on every database if every star in the sky had an Earth, each w
by laughinghan 11y ago
There are too many. Not just more than could fit in every database on Earth. More than could fit on every database if every star in the sky had an Earth, each with as many databases as there are on Earth.
This is nothing specific to cryptography or prime numbers. Fun fact: if you shuffle a deck of cards correctly, it's almost certain that no one in history has ever had a deck in the exact same order. https://www.math.hmc.edu/funfacts/ffiles/10002.4-6.shtml https://www.math.hmc.edu/funfacts/ffiles/10002.4-6.shtml
- Consultant32452 11y agoI understand that there's a huge number of primes, but surely the primes being used to generate keys or whatever process they're involved in are "known" primes, right? It's not as if when I try to encrypt something my machine is going to search for a new prime number that hopefully won't get guessed.
- yoha 11y agoLong prime numbers are used for RSA keys. You only generate RSA keys when creating a new identity (webserver certificate, client certificate, SSH key, etc). Then, you do search for "a new prime number that hopefully won't get guessed". It can take from a few seconds to several minutes, depending on the hardware and the desired key length. The usual approach is to take a random odd number of desired length and then have a probabilistic primality test (much faster than what would be needed for a formal proof). Several attacks rely on bad entropy or bad pseudo random number generators (PRNG) to guess what prime was selected.