Generating REALLY big primes

I remember solving the problem like this:

1. Use the sieve of eratosthenes to generate all primes below sqrt(1000000000) = ~32 000 in an array primes.
2. For each number x between m and n only test if it's prime by testing for divisibility against numbers <= sqrt(x) from the array primes. So for x = 29 you will only test if it's divisibile by 2, 3 and 5.

There's no point in checking for divisibility against non-primes, since if x divisible by non-prime y, then there exists a prime p < y such that x divisible by p, since we can write y as a product of primes. For example, 12 is divisible by 6, but 6 = 2 * 3, which means that 12 is also divisible by 2 or 3. By generating all the needed primes in advance (there are very few in this case), you significantly reduce the time needed for the actual primality testing.

This will get accepted and doesn't require any optimization or modification to the sieve, and it's a pretty clean implementation.

You can do it faster by generalising the sieve to generate primes in an interval [left, right], not [2, right] like it's usually presented in tutorials and textbooks. This can get pretty ugly however, and it's not needed. But if anyone is interested, see:

http://pastie.org/9199654 and this linked answer.

1. On probabilistic primality tests

A computer is a reliable, deterministic system: for the same input, it will run the same algorithm to the same output. Will it always do that ? Almost. There is such a thing as high energy particles roaming through the universe, usually known as cosmic rays. When such a particle hits a transistor hidden deep within a CPU, it may make it hiccup -- basically alter its output voltage, in a very transient way, such that for one clock cycle, the bit which the transistor output represent is flipped.

Now consider some computer running a prime generator algorithm, which creates random numbers and tests them for primality. The primality test is a function which returns a boolean value. At some point, the result (the boolean which is true for "prime", false for non-prime) is a constant value copied into a register. So there is a window of a few clock cycles during which that result is a single bit, contained in a flip-flop structure (which consists in 6 transistors).

What is then the probability that a cosmic ray flips that critical bit at just the "right" clock cycle, making the program consider a non-prime to be actually prime ? That probability is very low. As I said, computers are reliable systems. Nevertheless, that probability can be roughly estimated. It is usually considered that a given CPU experiences a cosmic ray bit flip once every three months. A Core2 Duo processor contains about 291 millions of transistors, and runs at (for instance) 2.4 GHz. If there is a single "critical" transistor, and that transistor is critical for a single clock cycle, then the probability of cosmic ray turning a non-prime into an apparent prime is about 1.8*10^-24. This is a very optimistic lower bound; in practice, many transitors could be flipped and imply the primality test failure, and the target timing covers several cycles, and a prime generator will examine several dozen non-primes for each prime generation. But let's consider that we are lucky.

The 1.8*10^-24 probability affects every primality test, regardless of whether it is deterministic or not.

A usual prime generator will run a Miller-Rabin test with a "certainty" of 2^-100 (the test is executed 50 times, and has a probability of no more than 0.25 to miss a non-prime each time). The "100" is arbitrary but common. That probability is a bit less than 10^-30. So there you have it: the probability of a Miller-Rabin test declaring prime a non-prime is less than a millionth part of the probability of a cosmic ray hitting a transistor and making the application assume that a number is prime whereas the Miller-Rabin test said that it was not.

In shorter words, if you get a non-prime out of a prime number generator, then this is due to a hardware issue such as a cosmic ray, not to the probabilistic nature of the primality test.

Having a bad prime due to a cosmic ray is actually a stroke of very good luck. The probability that an asteroid hurtling through space finally falls on your house an incinerates you during the first second after which you generated your key is much higher. I do not know about you, but personally I much prefer having a bad RSA key than being crushed by a falling rock.

2. A bad key

If you use a non-prime in a RSA key then you get a bad key. A bad key will generate bad signatures: the signature generator will produce a stream of bytes of the right length, but the signature verifier will declare the signature invalid. Note: actually, the signature may be valid, with a small probability. Using the "primes" p and q in RSA is akin to a probabilistic primality test, just like a Miller-Rabin test. Chances are, however, that the key will soon be found to misbehave. A similar behavior will be observed for asymmetric encryption.

It shall be noted that producing a bad signature, or failing to decrypt a RSA-encrypted message, can also occur due to yet another cosmic ray, or even the much more mundane occurrence of bad RAM.

Bottom line is that if you worry about having a bad RSA key but not about the much more probable event of a hardware failure (which is unavoidable because of cosmic rays, but thankfully not very common anyway), then you are getting your priorities wrong.