3
$\begingroup$

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.

$\endgroup$

migrated from stackoverflow.com Jul 3 '17 at 10:23

This question came from our site for professional and enthusiast programmers.

  • 8
    $\begingroup$ I'm not really sure what you're asking here. The largest prime discovered on a PC is probably 2^74,207,281-1. Prime numbers for RSA cryptography are generated by simply choosing a random odd number with the required number of bits and repeatedly adding 2 until the result is prime. There are several primality testing algorithms that can be used for this purpose. $\endgroup$ – squeamish ossifrage Jun 4 '17 at 21:33
  • 1
    $\begingroup$ "Are numbers randomly generated and then check whether they are prime numbers ?" Yes, with some optimizations. "Even checking whether a number with 300 digits is a prime is still a very extensive operation." True, but it should only take a few seconds to find a 1024-bit prime. $\endgroup$ – James K Polk Jun 4 '17 at 22:28
  • 1
    $\begingroup$ Wikipedia: "For the large primes used in cryptography, it is usual to use a modified form of sieving: a randomly chosen range of odd numbers of the desired size is sieved against a number of relatively small primes (typically all primes less than 65,000). The remaining candidate primes are tested in random order with a standard probabilistic primality test such as the Baillie-PSW primality test or the Miller-Rabin primality test for probable primes." $\endgroup$ – Maarten Bodewes Jun 5 '17 at 1:19
  • $\begingroup$ What does "Highest prime number calculated on a regular PC" mean? The largest register size is 64-bits, so the largest prime will be smaller than 2^64. You can probably go higher with a double, but I don't know where precision falls off. $\endgroup$ – jww Jun 5 '17 at 13:57
  • $\begingroup$ @jww Yeah, that was the point I was making, I guess that the given answer nicely reflects this. I guess that second comment is a bit spurious, it's quite clear from context that registers were not meant. $\endgroup$ – Maarten Bodewes Jun 5 '17 at 14:34
7
$\begingroup$

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 — proven to be prime — 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 < k < 2(p + 1). Let N = 2kp + 1. Then the following conditions are equivalent:

  1. N is a prime.
  2. There exists an integer a, 1 < a < N, such that a(N−1)/2 ≡ −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 ≤ k < 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 ∈ {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.

$\endgroup$
  • 1
    $\begingroup$ Whether Pocklington's method is better is debateable. $\endgroup$ – James K Polk Jun 6 '17 at 23:22
  • 1
    $\begingroup$ @JamesKPolk: Pocklington's method produces a guaranteed prime, the other method is faster but might produce a composite. Given that the objective is to produce a prime number, Pocklington's method will always succeed, the other method will always leave doubt. What's the debate? $\endgroup$ – user448810 Jun 7 '17 at 1:21
  • 1
    $\begingroup$ Very simply, computers can suffer errors. Therefore a run of Pocklington's method may produce a composite due to a random bit error. The probability of miller-rabin declaring a composite to be prime can be tuned to be as low as desired. Therefore, on a typical computer, Pocklington's method will be no more reliable than miller-rabin. $\endgroup$ – James K Polk Jun 9 '17 at 10:48
  • $\begingroup$ While one does not use a sieve to find one of the "Highest prime number calculated on a regular PC", nor to insure that a cryptographic-size prime indeed is prime, one often "does use a sieve to find a cryptographic-size prime", for efficiency reasons. That's especially true for primes $p$ with $(p-1)/2$ prime, or primes with $p-1$ and $p+1$ both having a large prime factor, as required by some RSA standards (including ANS X9.31, and FIPS 186 for 512-bit primes part of 1024-bit keys). $\endgroup$ – fgrieu Jul 3 '17 at 11:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.