| MadSci Network: Computer Science |
For reasons I'll present below, cryptographers make heavy use of prime numbers, and are intensely interested whenever visible progress is made in the old problem of finding the prime factors of some big number, such as when a deliberately hard-to-factor, 130-digit number was factored in 1996. We're not as nutty as the question implies, though: the neverending search for the next Largest Known Prime is, to cryptographers, only slightly more than an amusing sporting event among computer scientists; and in their daily work, many cryptographers routinely discover many previously unknown primes in the 100-to-200 digit range without even being interested enough to look at them.
Prime numbers are interesting to cryptographers because they are central to some of the mathematical problems on which modern ciphers are based. For example, if you decide to use the most popular public-key cipher today, called RSA, you start by finding two large (100-digit) prime numbers and multiplying them together to get your own, personal "modulus," which will be another large (200-digit) number. You post your modulus for all the world to see, and if anybody wants to encrypt a secret number to send to you, all he has to do is cube it (multiply it by itself twice), divide by your modulus, and send you the remainder from the division. Knowing the prime factors of the modulus, you can recompute the original secret number from the remainder that your friend sends you (the details are slightly complicated); but an enemy who intercepts the remainder -- even an enemy who knows your modulus -- in general cannot recompute the original secret number from it. The "secret number" can, of course, be some kind of letters-to-numbers translation of a textual message. (Warning: for this encryption to be strong, the secret number must be big enough that its cube greatly exceeds the modulus. In practical applilcations, a large number is added to the secret number before cubing.)
As far as anybody knows, there is in general no way to break this cipher faster than by finding the two prime numbers that were multiplied together to make your modulus. Consequently, cryptologists are very interested in how big a number of this sort can be factored, since that tells them how big they have to make their moduli. To keep its pulse on the progress of factoring technology, RSA Data Security Inc., the company founded to commercialize the RSA encryption algorithm, has sponsored a series of factoring challenges, with prizes in the thousands of dollars for factoring specific numbers of various lengths. The 129-digit modulus used in the original (1977) description of the RSA cipher was factored in 1994, and the 130-digit member of the RSA Factoring Challenge series was factored in 1996.
Another prime-related problem of great interest to cryptographers is the that of finding a logarithm in the field of integers modulo a large prime. Here's what that means. Find a large prime, p. Choose a non-secret number g, and a secret number x. Raise g to the xth power, divide by p, and call the remainder r. (In mathematical notation, r = g^x mod p.) Given p, g, and r, it is hard to find x. This is called the "discrete logarithm" problem, and for properly chosen p and g, it seems to be slightly more difficult than the problem of factoring a difficult composite number the size of p. Based on this principle, two people communicating over an insecure channel (such as the Internet) can compute a secret number that they both know but that can't be computed from information intercepted on the channel. The "secret number" can then be used as an encryption key. (The procedure for doing this is known as Diffie-Hellman key agreement.)
Further information on cryptology in general can be found...
Try the links in the MadSci Library for more information on Computer Science.