To Pi and Beyond

Credit Photograph by Jeffrey Coolidge / Getty

Possibly not everyone knows that March 14th is Pi Day, in honor of the symbol used to denote the ratio of the circumference of a circle to its diameter. Pi is commonly approximated as 3.14, but it appears to be an endless numberit has been computed to more than thirteen trillion digits, among which there is no pattern that repeats. It also belongs to a category of numbers called irrational numbersnumbers, that is, that cant be expressed as fractions. Numbers have always seemed irrational to me, like a joke everyone else gets that I dont, maybe even a joke at my expense. Nevertheless, I like the idea of irrational length, of infinity, of endlessness, although sometimes I feel uneasy about it. I am haunted, occasionally, by the thought of what lies on the other side of spaceat the end of the universe, that iswhich is only one reason that I no longer smoke marijuana.

Entertaining the idea of a peculiar long number such as pi puts me in mind of its cousins twice removed, prime numbers, which have so many strange properties. Prime numbers are those numbers, such as 3, 5, 7, 11, and so on, that can be cleanly divided only by one and themselves. Primes and pi suggest a benign infinity, a pleasing orderpi because of its endlessness and its relation to the circle, and primes because no matter how far you travel on the number line you will always encounter a prime, as Euclid proved in 300 B.C. Recently, Yitang Zhang solved a problem involving prime numbers called bounded gaps that had been open for more than a hundred years. Zhang proved that no matter how far you go on the number line, even to the range where the numbers would fill many books, there will, on an infinite number of occasions, be two prime numbers within seventy million places of each other. (Other mathematicians have reduced this gap to two hundred and forty six.) Before, it had not been known whether any such range applied to prime numbers, which seem to behave, especially as they get larger, as if they appear at random.

Pi is a useful number with a specific identity and a use. Primes are diverse and have many applications. Zhang said that his result, however, from a field of pure mathematics called number theory, had no commercial applications. Terence Tao, a mathematics professor at U.C.L.A., told me, Yitangs paper might have some applications to cryptography and Internet finance. The connection is weak, but there are some codes that rely on primes special properties. Tao mentioned a category of prime called a safe primethat is, a prime that corresponds to the formula 2p + 1, where p is also a prime. Safe primes are also called Sophie Germain primes. It is conceivable that, with additional work, Zhangs methods could be used to guarantee the existence of infinitely many primes of such a special type, although it wont tell you where to find them.

Primes, which are secretiveno one knows, for example, if there is a formula that might predict their occurrenceare also essential to keeping secrets. Much of Internet commerce and finance relies on a cryptographic system called R.S.A., which takes the initials of the men who came up with it, in 1977Ron Rivest, Adi Shamir, and Leonard Adleman. R.S.A. works by means of a pair of codes, a private key and a public key. A transaction involving, say, your credit card is scrambled using the public key, sent to a bank, then unscrambled using the private key. The public key is the result of two prime numbers multiplied together. Typically, each prime is more than a thousand digits long. (The largest known prime, which took several thousand computers nearly a month to find, has seventeen million digits, making it an astronomically larger number than pi but a dwarf to its digits.) The public key can be discovered from the private key, but the private key cannot easily be discovered from the public. Keys are protected by a principle called the trapdoor function. Trapdoor functions are ones that are simple to calculate in one direction but hard to calculate in the other without special information, which is the trapdoor. In the case of R.S.A., the trapdoor involves a field called modulo math. The most familiar form of modulo math is the clockface. Ten hours from four oclock is two oclock, not fourteen oclock; this is an example of arithmetic modulo twelve. To know the time at any number of hours into the future, you divide the hours by twelve and apply the remainder to the clockface. A version of a clockface can be composed of any number of hours, and this is what happens with R.S.A. The trapdoor function is a result of knowing the modulo involved in selecting the keys. Simply finding by luck or application the prime numbers involved in the key is useless without the modulo number.

Henry Cohn, a principal researcher at Microsoft, told me that Zhang was probably correct in saying that there were no commercial applications for his result.He thought, though, that its influence was what you might call motivational or philosophical. The idea that there is a philosophical quality to math is one that I can almost grasp but, even at a remove, find thrilling. Cryptographic security is based on conjectures that are unproved and seemingly very difficult to resolve, Cohn went on. For example, the security of R.S.A. depends on there not being a fast algorithm to factor a number into primes. Factoring means finding from one number the two numbersthe factorsthat were multiplied to produce it. An algorithm that would factor huge numbers into primes does not appear to exist, but its by no means certain, Cohn told me. Sometimes surprising things happen in mathematics, and we really dont want to be caught by surprise when computer security is on the line. Zhangs theorem doesnt directly address this issue, but it can be seen as part of a larger program in number theory: how can we justify seemingly simple properties of numbers?

Zhangs result describes how primes are distributed. They dont appear randomly, they follow some mysterious structure. When youre trying to make a cryptosystem like R.S.A., you are depending on the fact that numbers have a good deal of structure, Cohn wrote. He went on to say, however, that this structure could come back to bite you, by enabling an attacker to defeat the system. Ultimately, what youd like is a situation that looks beautifully regular and structured to the legitimate users while looking unapproachably random to hackers. This is a subtle balancing act, and lots of cryptosystems have fallen apart over the years when it turned out there was just a little too much hidden structure that could be taken advantage of. R.S.A. is important because this has not (yet?) happened to R.S.A.: it seems to be one of the few good ideas in a sea of bad ideas. But this makes cryptographers particularly attuned to issues of structure and randomness, in a way that lines up philosophically with number theorists working on topics like bounded gaps between primes.

Number theory is a discipline done for no purpose. It is practiced by people who believe that numbers have properties that exemplify an orderliness and beauty in the universe. The story of numbers is a story of creation not directly contained in the Scriptures, but if a divinity didnt create numbers and their properties, what accounts for them? The necessity of counting doesnt entirely explain pi or primes. A breakthrough in number theory is called a discovery, not an invention. There isnt yet any explanation for the properties of pi or for primes. There is only the sense of wonder that the world contains such extravagant mysteries so close at hand.

Source: http://www.newyorker.com/tech/elements/pi-prime-numbers-cybersecurity