Since time immemorial, people have found it necessary to send informationto others in a secure way, so that even if a message is intercepted by a thirdparty, it can be read only by the intended recipient. This is usually achieved byconverting the message into a string of numbers or letters according to somerule that only the sender and recipient know. The process of converting themessage into such a string is called “encoding,” and the process by which therecipient converts the received string back to the original message is called“decoding.”For example, one of the simplest imaginable encoding rules would be tosubstitute 01 for an A, 02 for a B, 03 for a C, and so on until we get to 26 for aZ. Then the message SMALLBRAIN IS THE CULPRIT

gets encoded as the string of numbers 19130112120218010914091920080503211216180920. (15.1)

However, anyone with a modicum of intelligence would be able to break thiscode in a matter of minutes. In view of the millions of Internet transactions,sensitive business and government communications, and so on, that take placeevery day, some rather more sophisticated ideas are required to ensure the se-cure transfer of information in today’s world. The codes now in use for suchpurposes — so-called RSA codes — are based on some of the theory of primenumbers and congruence developed in the last few chapters. These codes canbe explained in just a few pages, which I shall now attempt to do.Before going into the theory, let me explain the crucial fact that gives thesecodes their security. Any form of security is based on things that “attackers”are unable to do. In this case, information is being transmitted electronicallyby computer, so security needs to be based on something that computers can’tdo quickly.Let me now explain something that computers can’t do quickly. If you taketwo reasonably large prime numbers, say 1301 and 2089, you can find their

TO PURE

seconds. However, you were given the number 2717789 and asked to find its prime factors, itwould take you and your calculator much longer. (If you doubt this, try usingyour calculator to find the prime factors of 127741.) The same kind of obser-vation applies if we bring very powerful computers into play: take two verylarge primes p and q, say with about 200 digits each — I outlined to you howsuch primes are found in the last section of Chapter 14 — and calculate pq.Keep p and q secret, but tell the most powerful computer in the world todaythe value of pq. Then, however cleverly that computer is programmed (at leastwith ideas available today), it will probably take at least several centuries forit to find out what p and q are. In other words, computers find factorization oflarge numbers “difficult.”