Highest prime number calculated on a regular PC 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 10^21-1.

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.
You don't use a sieve to find cryptographic-size primes.

One method chooses an odd number of the appropriate size at random, then tests it using a Miller-Rabin or Lucas pseudoprime test, incrementing the number by 2 until a probable prime is found; an alternative is to pre-sieve with small primes (less than 1000, say), and perform pseudoprime tests only on those numbers that survive the sieve. That works, and is commonly used in cryptographic practice, but is not guaranteed to find a prime number. An implementation of this method is available at my blog.

Also at my blog is an explanation of a better method for generating cryptographic primes:


  Sometimes you need to have a large prime, for testing, cryptography,
  or some other purpose. I’m talking about primes of several hundred to
  a few thousand digits that are certified &mdash; proven to be prime
  &mdash; rather than probable primes according to a Miller-Rabin or
  other probabilistic test. Henry Pocklington’s Criterion, which dates
  to 1914, gives us a way to find such primes quickly. Paulo Ribenboim
  explains it thus:
  
  Let p be an odd prime, and let k be a positive integer, such that
  p does not divide k and 1 &lt; k &lt; 2(p + 1). Let N = 2kp + 1. Then the following conditions are equivalent:
  
  
  N is a prime.
  There exists an integer a, 1 &lt; a &lt; N, such that a(N&minus;1)/2 &equiv; −1 (mod N) and gcd(ak + 1, N) = 1.
  
  
  This gives us an algorithm for generating large certified primes.
  Choose p a certified prime. Choose 1 &le; k &lt; 2p at
  random; we ignore the last two possibilities for k, so we don’t have
  to worry about k being a multiple of p. Compute N. For each a
  &isin; {2, 3}, test the conditions for primality. If you don’t find a
  prime, go back and choose a different random k. Once you have a
  prime N, “ratchet up” and restart the process with the new certified
  prime N as the p of the next step. Continue until N is big
  enough.


There is code and a more complete explanation at my blog.