The algorithm Sieve of Erastosthenes uses memory to do its work. The available memory determines the highest prime number, which can be found. On a regular PC, we have typically 4 GBbyte memory, which allows to store
32*10^9 bits. Therefore the highest prime number to be found with Sieve of Erastosthenes is
32*10^9-1 with 4GB RAM.
With Segmented Sieve Of Eratosthenes we can square this number, which then results in
Another way to go further is to use the hard disk instead of RAM to store the bits for Sieve of Erastosthenes. A typical PC has 1 Tera Byte disk space, which is 8*10^12 bits, which then results in 8*10^12-1 as the highest prime number to be found. Using Segmented Sieve Of Eratosthenes we can square this and finally we realize that 64*10^24-1 is the highest prime number, which we can calculate on a regular PC.
But for cryptography key lengths of 1024 bit and more are common, which means that prime numbers of
10^300 are generated on a typical PC. How is this done ?
Are numbers randomly generated and then check whether they are prime numbers ?
Even checking whether a number with 300 digits is a prime is still a very extensive operation.
Please help me to understand this.