ORLANDO, Florida, June 30, 1999 -- Nayan Hajratwala, a participant in the Great Internet Mersenne Prime Search (GIMPS), has discovered the first known 2 million-digit prime number using software written by George Woltman and the distributed computing technology and services of Scott Kurowski's company, Entropia.com, Inc. The prime number, 26,972,593-1, contains 2,098,960 digitsqualifying for the $50,000 prize offered by the Electronic Frontier Foundation (EFF). An article is being submitted to an academic journal for consideration.
The new prime number, discovered on June 1st, is one of a special class of prime numbers called Mersenne primes. This is only the 38th known Mersenne prime. Nayan used a 350 MHz Pentium II IBM Aptiva computer running part-time for 111 days to prove the number prime. Running uninterrupted it would take about three weeks to test the primality of this number. Richard Crandall, whose faster algorithms helped prove the number prime, has a poster that displays this huge number for sale at http://www.perfsci.com.
Discovering prime numbers of this size would be impossible without the distributed computing power harnessed by Entropia.com's PrimeNet system, a research computing solution created, operated and supported for GIMPS. PrimeNet coordinates more than 21,500 computers into a virtual massively parallel supercomputer for research. The computers are provided by 12,600 home Internet users, schools and businesses from around the world, and perform 720 billion calculations per second. The GIMPS project spent the equivalent of 1,650 of Intel's top-of-the-line processors running full-time for a year to find this prime number.
This was all done using spare computer time that would otherwise be wasted! Thus demonstrating that extraordinarily difficult problems can be solved very cost-effectively using these distributed techniques. Entropia.com is galvanizing this resource for practical use by accepting proposals for other research computing problems. The company also plans to offer a means of financial compensation for computer time contributed to its customers' computing projects.
Earlier this year an anonymous donor funded the Electronic Frontier Foundation's cooperative computing awards. These awards have a dual purpose. One is to spur further advances in distributed computing. Second is to further research in prime numbers and computer algorithms. Both are important in the field of cryptography, privacy, and computer security. Nayan should be able to claim the $50,000 award for discovery of a million-digit prime number. Nayan's claim is pending publication in a refereed academic journal. The next award is $100,000 for discovery of a ten-million-digit prime number. Using current algorithms, this is more than 125 times as difficult as finding a 2 million digit prime. GIMPS and Entropia.com are gearing up for this challenge now.
Nayan Hajratwala is from Plymouth, Michigan and works for PricewaterhouseCoopers. George Woltman is a retired computer programmer living in Orlando, Florida. A life-long number theory enthusiast, he founded the GIMPS project in January 1996. Scott Kurowski is a software development manager and entrepreneur living in San Jose, California. He founded Entropia.com, Inc. in 1997 to support large-scale Internet distributed computing projects for researchers.
This prime number is the fourth record prime found by the GIMPS project. In recognition of every GIMPS contributor's effort and the invaluable services of Scott Kurowski's company, credit for this new discovery will go to "Hajratwala, Woltman, Kurowski, et al." In January 1998, Roland Clarkson discovered the previous largest known prime number. Gordon Spence discovered the 36th Mersenne primein August, 1997. Joel Armengaud discovered the 35th Mersenne primein November, 1996.
Using a program written by Ernst Mayer, the new Mersenne prime was independently verified by David Willmore using two weeks of computer time donated by Aerial Communications on a 500 MHz Alpha workstation. Ernst Mayer works with Richard Crandall on a variety of number theory projects.
There is a well-known formula that generates a "perfect" number from a Mersenne prime. A perfect number is one whose factors add up to the number itself. The smallest perfect number is 6 = 1 + 2 + 3. The newly discovered perfect number is 2^6972592 * (2^6972593-1). This number is 4,197,919 digitslong!
The search for more Mersenne primes is already under way. There may be smaller, as yet undiscovered Mersenne primes, and there are certainly larger Mersenne primes waiting to be discovered. Anyone with a reasonably powerful personal computer can join GIMPS and become a big prime hunter. All the necessary software can be downloaded for free at http://www.mersenne.org/prime.htm.
An integer greater than one is called a prime number if its only positive divisors are one and itself. For example, the number 10 is not prime because it is divisible by 2 and 5. A Mersenne prime is a prime of the form 2P-1. The study of Mersenne primeshas been central to number theory since they were first discussed by Euclid in 350 BC. The man whose name they now bear, the French monk Marin Mersenne(1588-1648), made a famous conjecture on which values of p would yield a prime. It took 300 years and several important discoveries in mathematics to settle his conjecture.
With undertakings such as the race to the moon in the 1960's, it is the byproducts that are most useful to society. The same is true in the search for large primes.
This project has led to Entropia.com's advances in distributed computing. That is, using the Internet to effectively apply the unused computing power of thousands of machines. Scott said, "A successful, large Internet-distributed computing network like Entropia.com, with accurate, detailed accounting and great end-user customer service is a complex undertaking. It must be robust, efficient and scalable. Developing PrimeNet for GIMPS has been an opportunity for us to strengthen our business and engineer a basic concept into a practical technology and viable research computing solution." Extrapolating an Arthur Anderson quote, PrimeNet produces an estimated $182,000 to $486,000 per day in CPU time if GIMPS purchased it commercially. However, GIMPS receives its vast computing power from its thoughtful participants for free! "Someday, many problems that require a supercomputer today will be solved using low-cost PCs.", says Scott.
There is a unique history to the arithmetic algorithms underlying this project. The programs that found the recent big Mersenne finds are based on a special algorithm. In the early 1990's, Richard Crandall, Apple Distinguished Scientist, discovered ways to double the speed of what are called convolutions -- essentially big multiplication operations. The method is applicable not only to prime searching but other aspects of computation. During that work he also patented the Fast Elliptic Encryption system, now owned by Apple Computer, which uses Mersenne primes to quickly encrypt and decrypt messages. George Woltman implemented Crandall's algorithm in machine language, thereby producing a prime-search program of unprecedented efficiency, and that work led to the successful GIMPS project.
Several hundred school teachers elementary through high-school grades have used GIMPS to get their students excited about mathematics. Students who run the free software are contributing to mathematical research.
Historically, searching for Mersenne primes has been used as a test for computer hardware. The free GIMPS program used by Nayan has identified hidden hardware problems in many PCs.
Contacts:
Nayan Hajratwala nayan@walanet.com
George Woltman woltman@alum.mit.eduOrlando, FL 407-876-0328 Scott Kurowski kurowski@entropia.comFounder, Entropia.com, Inc. San Jose, CA 408-807-7003 Ernst Mayer mayer@nigel.mae.cwru.edu Dept. of Mechanical & Aerospace Engineering, Case Western Reserve University 216-932-1952 Richard Crandall crandall@reed.eduDirector, Center for Advanced Computation Portland OR
Alex Fowler afowler@eff.orgEFF Director of Public Affairs 415-436-9333 x103
Chris Caldwell, Simon Cooper and Landon Curt Noll coop-award-question@eff.orgEFF Cooperative Computing Award advisory panel