Skip to Main Content


Feature Column Archive

5. Primes and cryptography

Although it may appear at first glance that the primes are just an "intellectual toy" for people who like mathematical and computing puzzles, primes relate to ideas that have important practical applications. Increasingly, modern society depends for its operation on fast and accurate information. Sometimes one wants to keep information secret from everyone except the sender and recipient. Examples of such information are diplomatic communications, money transfers between banks, medical records, and business transactions. Secret codes and ciphers come into play in such situations. The science of cryptology, which deals with the making and breaking of codes, involves specialists from linguists to engineers, mathematicians and computer scientists. The widespread use of computers and telecommunications equipment has made necessary more flexible codes and ciphers. (There is a technical difference between codes and ciphers but here I will use the term code to include systems that are really ciphers. In fact, ciphers are used at least as often as codes.)

Historically, most coding systems required the sender and receive to each have a "private key" which enabled them to encrypt and decrypt the information that was being sent and received. Revolutionary ideas worked on by Ralph Merkle, Whitfield Diffie, Martin Hellman, Leonard Adleman, Adi Shamir, and Ronald Rivest made it feasible to implement new public key systems. These systems make it possible for a person Y to put information in a public directory and have anyone X who wanted to send a secret message to Y use this "public key" so as to be able to send information in a secure manner. This system does not depend on the secrecy of the key but on the computational complexity of using "intercepted" encrypted text to obtain the "clear" (readable) text. Amazingly, the security of the system developed by Rivest, Shamir, and Adleman (known as RSA) is based on the fact that factoring products of two extremely large thought to be very difficult. The design of the system depends on being able to choose very large integers that are known to be prime. Thus, the issue of checking whether or not a particular very large number is prime becomes significant in this system. The new algorithm that verifies that testing for primality can be done in polynomial time is, unfortunately, not speedy enough to be used in cryptographical applications unless it can be modified in some way that speeds it up significantly. Furthermore, the fact that numbers can be tested in polynomial time to see if they are prime in no way affects the security of RSA to the best of current knowledge. RSA's security depends on the complexity not of checking if a number is prime but of factoring numbers into primes.

  1. Introduction
  2. Basic ideas
  3. Distribution of the primes
  4. Complexity and algorithms
  5. Primes and cryptography
  6. The right stuff
  7. References