Prime time for numbers

The world's largest prime number has been found recently, which, at nearly 13 million digits long, would take 3 months to say out loud.

Like numerical Easter eggs, prime numbers lie hidden in thickets of other, less interesting numbers, just waiting to be found. The first few are easy enough to rustle up - 2, 3, 5, 7, 11 - but the majority are devilishly well-hidden. New ones are also few and far between, which makes it all the more remarkable that recently two have been discovered within two weeks. A number is a "prime" when it can be divided by only itself and the number one. Thus, 7 is prime but 6 is not, as it can be divided by 2 and 3. The number 3,626,149 is also prime, although you'll probably have to take my word for it. To make things more complicated, primes are grouped into at least 77 "subspecies", such as Balanced, Cousin, Cuban, Emirps, Happy, Lucky, Palindromic, Primeval, Sexy, Stern, Safe and Wagstaff primes. Among these, and of great interest to the world mathematics community, not least because they offer computers a shortcut to the larger and otherwise impossible-to-find primes - so huge, they are beyond the reach of mere humans armed only with pencils and paper - are the Mersenne primes. These are identified by the deceptively simple formula 2p-1, where P itself is a prime number. For instance, 3 is the smallest Mersenne prime since it is equivalent to 22-1 - or 2 x 2 -1. Two years had passed since the last Mersenne prime was unearthed when, on Aug 23, news of the discovery of the first one longer than 10 million digits swept the global mathematics community. Edson Smith, a computer systems administrator at the University of California in Los Angeles, won a 10-year race to claim a cash prize offered by the Electronic Frontier Foundation (EFF), pipping to the post by only two weeks his German rival Hans-Michael Elvenich, who on Sept 6 announced the discovery of a second, slightly smaller 10-million-digit Mersenne prime. "I was flabbergasted when I found out," says Mr Smith. "The chances that we would find a new prime were astronomically small." Mr Smith's number (243,112,609-1 and, please, don't try this on your calculator), the largest Mersenne prime known to man, is nearly 13 million digits long; so incredibly long, in fact, that printing it would require more than 450 pages of newspaper like this one. Just saying it out loud would take more than three months. The discovery was not entirely pointless; it won Mr Smith a US$100,000 (Dh367,000) EFF prize and a place in the annals of mathematical history. Not that he is a mathematician. He maintains the computer lab for the mathematics department at UCLA and found the number using special software designed by a group of mathematicians and programmers who like to be known as "Gimps", which stands for the Great Internet Mersenne Prime Search. The software can be downloaded and installed on any desktop computer, where it runs in the background, using the Mersenne formula to steadily crunch its way through potential primes, and Mr Smith had installed the Gimps program on 75 computers in his lab. The lucky machine that actually discovered the new prime was a humble Dell desktop named Zeppelin, after the rock band, and no one was more surprised than Mr Smith. "It's a really great project," he says. "We installed it to show our undergraduates how distributed computing works. We never expected to actually find a new prime number." It is, says Mr Smith, doubtful that lightning will strike twice but, nevertheless, "We're going to keep running the program on our computers." About 100,000 computers around the world are currently running the Gimps software. Together, they are proof that a new kind of "grass-roots supercomputer" can trump the traditional supercomputing paradigm, in which enormous towers of machines fill rooms as big as football pitches. Although it probably took Zeppelin several weeks to verify that Mr Smith's number was prime, with so many other computers around the world doing the same thing for countless other numbers, together they cover a lot of ground quickly - and cheaply. The entire Gimps network performs 29 trillion calculations a second, making it one of the fastest supercomputers on earth. But why bother? What's the point? To this question, some Gimps participants offer that prime numbers are useful for encrypting sensitive information, such as credit-card transactions. However, the real answer is much simpler: most do it for no better reason than the thrill of the chase. Seekers after prime numbers are akin to the amateur astronomers who spend their nights scanning the heavens, searching for undocumented stars. "It's exciting to push the envelope of computational mathematics and to search for something unknown that you believe is out there," Mr Smith wrote on his website. "As bonus, unlike the explorers of old, we get to sit in comfortable office chairs while we're searching!" As numbers get bigger, so it grows increasingly unlikely they will be prime, since more and more numbers could potentially be their divisor. For the same reason, big numbers are also harder to check for primality. As far as we know, there is still no way of predicting where prime numbers will appear. Their distribution appears random - like "cosmic static", some say - and a rule that could predict their location is still considered one of the great buried treasures of mathematics. As Carl Pomerance, the great numbers theorist, is supposed to have said: "God may not play dice with the Universe, but there's something strange going on with the prime numbers." Nevertheless, there are a few evident patterns that hint at which numbers might be prime and, by using these, mathematicians can spare themselves the task of checking every number in order. For a start, all even numbers are automatically ruled out as possible primes, since they can be divided by 2 (and do note that 2 itself is the only even prime number, which of course makes it quite odd). Although Mr Smith found his prime with the aid of modern computers, even their feat would have been impossible without the help of a 16th-century French monk and Renaissance man, Marin Mersenne. Mersenne, who is sometimes called the "father of acoustics", published seminal works in the fields of theology, philosophy and music theory. Today, however, he is remembered chiefly by mathematicians for his discovery of a particular subfamily of numbers, some of which are primes, and the Gimps project specifically targets these "Mersenne primes" because it has devised a shortcut for testing whether numbers of that form are prime. By plugging already known primes into the Mersenne formula, computers can test numbers that would otherwise be too enormous to tackle. Not that it has helped that much. Mr Smith's number is only the 45th Mersenne prime to be found so far. "In general the situation is still really bad regarding our understanding of primes," says Richard Crandall, a professor at Reed College in Portland, Oregon, who devised the Gimps algorithm. "If you take a normal 50,000-digit number, we generally cannot prove whether it's prime or not. Only with these Mersenne primes - the latest of which have more than 10 million digits - can we test such big numbers for primality." It is, he says, "a great mystery. We still don't know whether there are any more Mersenne primes. We think there are infinitely many but we're not sure. Every time we find one though, it reassures us." According to Alex Eskin, a professor of mathematics at the University of Chicago, "In a sense, prime numbers are the fundamental building blocks of all numbers, so questions about them are very old and often very difficult. This is pure mathematics." The search for prime numbers goes back as far as mathematics itself. In the sixth century BC, the Greek mathematician and mystic Pythagoras started what may have been the first formal study of primes in the Western world. Though he is best known today for the eponymous Pythagoras's Theorem, in the ancient Mediterranean he was the founder of a religious sect whose initiates called themselves Mathematikoi. Pythagoras and his followers gave up all possessions, foreswore the eating of meat - and studied mathematics incessantly, in the belief that it could be used to predict the future. However, it was Euclid of Alexandria who made the first major advance in the study of primes, nearly 200 years later, when he proved there were an infinite number of primes and that they appeared at unpredictable intervals. After that, the study of prime numbers went into a sort of "dark ages", until a group of mathematicians in Europe began studying them again nearly 2,000 years later. Among them was Pierre de Fermat, a French lawyer and mathematician recognised today for what has become known as Fermat's Last Theorem. His less-well-known "Little Theorem" dealt with prime numbers. Although Fermat corresponded with Mersenne during his lifetime, it was not until after his death that someone else proved his Little Theorem. Even today, Fermat's work with primes is central to computational mathematics. Then came Leonhard Euler, an 18th-century Swiss mathematician who made several great conjectures about primes and showed that some of Fermat's thinking was wrong. "Mathematicians have tried in vain to this day to discover some order in the sequence of prime numbers, and we have reason to believe that is a mystery into which the mind will never penetrate," he concluded. In the 19th century, the search for the sequence of prime numbers gave rise to what is still considered the Mount Everest of maths: the Riemann Hypothesis, a conjecture proposed by the German mathematician Georg Friedrich Bernhard Riemann. "The Riemann Hypothesis, which is perhaps the biggest unsolved problem in mathematics, says approximately that the distribution of prime numbers is random," says Mr Eskin of the University of Chicago. There is still no proof for the hypothesis, although the Clay Mathematics Institute has offered a US$1 million reward for anyone who can show it to be true or false. Since Riemann, advances in the study of prime numbers have been relatively swift, especially with the advent of modern computers. "Prime numbers have been going off like popcorn," says Prof Crandall. "At first the popping was slow; we found a new prime every few years. Now with these computers the popping is speeding up to a rate of about one per year." With modern computers came the creation of encryption, which uses pairs of prime numbers to turn intelligible information into seeming nonsense. Each of the two numbers acts like a key. Without both keys, unlocking the code would require hundreds of years of supercomputing power, making encrypted information in effect impossible to crack. Because of their importance with encryption, prime numbers have even been patented. Roger Schlafly obtained US Patent 5373560 for two long primes, of approximately 150 digits, in 1994. The enormously long Mersenne primes that have been found lately, however, are too long to be useful for encryption and, considering the limitations of today's computers, have little more than novelty value. Nevertheless, there are still several prizes to be claimed: a US$150,000 reward for a prime with 100 million digits and US$250,000 for one with a billion. If you feel like having a go, visit Mersenne.org, download the Gimps software and await developments. [e-mail]