Mathematicians put their own spin on the search for rare prime numbers
Most of us learned what a prime number is in our early days of math class: An integer divisible only by itself and by one. But what you may not have realized is the search for the rarest of them is an international one, with a local effort led in an unconventional way by two Indiana State University professors.
Research by Geoff Exoo, professor of mathematics and computer science, and Jeff Kinne, assistant professor of computer science, focuses on finding the largest prime numbers, the largest twin primes (p and p + 2 are both prime, such as five and seven) and the largest Sophie Germain primes (p and 2p + 1 are both prime, such as five and 11). The project started last summer with the assistance of six students and is funded by the Indiana Academy of Sciences and the ISU Office of the President.
Their method puts a new spin on a project George Woltman started in 1996, the Great Internet Mersenne Prime Search (GIMPS), which provides volunteers with software to run on their computers and search for Mersenne prime numbers. Today, GIMPS makes use of more than 900,000 computers worldwide, according to its website.
"We wanted to see if we don't do it that way, what would we find," Exoo said. "We wanted to be different," Exoo said.
"We have a similar setup of using many PCs in the search, but we wanted to look at different ways to generate the prime numbers," Kinne said.
Running their own software, the ISU-developed project uses 75 computers full-time and, through the generosity of other departments, about another 75 machines, part-time on weekends and holidays. This past winter break was especially fruitful, as they found the 14th largest known twin prime on Dec. 18.
Each Friday evening, a student working with the ISU Office of Information Technology goes around to a few campus computer labs and with a USB key, reboots the machines into a LINUX operating system and starts the program. "Then, on Monday morning, the computer automatically reboots itself back to Windows, and the lab users never even know the computers were searching for prime numbers over the weekend," Kinne said.
When the team is alerted to a possible prime number discovery, the data is verified and then sent to a website tracking prime numbers, which verifies the information again.
Theoretically, the Exoo's and Kinne's program could be set up to run in the background of any machine, and the user would never be inconvenienced by it, the professors said. Exoo mused it could also be set up as a screensaver.
"People have these powerful computers that they're using about 1 percent of," said Exoo.
Making use of much more of the computers' capability, Exoo and Kinne have found the 12th, 13th and 18th largest known Sophie Germain prime numbers and the 14th largest known twin prime.
It's been known since ancient times there is no largest prime number—they just occur more rarely.
"With primes, there's no end," Kinne said.
While many academic disciplines have big riddles with multiple answers that require vast resources to compute—for instance, "protein folding" in biology—some mathematicians, going back to ancient times, often relish the challenge for the chase, not for its practical applications. It's math for math's sake, if you will.
"In math, we often look at a problem because the question is interesting or fascinating, even if the solution of the problem does not have an immediate application," said Exoo.
Enter cryptography: the very practical application of prime numbers research. It's how we're able to make secure purchases online, and presently, prime numbers a few-hundred digits long are required for the encryption process.
"In another 20 years, computers will be faster, and you'll need larger numbers," Kinne said.
Computers themselves have revolutionized the discovery of prime numbers. In 1588, the largest known prime was six digits in size. In 1951, a mechanical calculator helped find a prime 44 digits long. Two years later, a Standards Western Automatic Computer (SWAC) found a 687-digit prime number. By 1983, the largest known prime was 39,751 digits long; in 1993, 227,832 digits. And just last year, we're up to a prime number that consists of more than 17 million digits.
While Exoo's and Kinne's numbers aren't quite that large yet—their discovery of the 208th largest overall prime is 712,748 digits—they would be about a mile long, if printed. But "we have not actually printed it out," Kinne said.