Be a part of history: Search for the biggest prime number

Lim Tri Santosa

BANDUNG (JP): If you have enough people, you can accomplish enormous tasks even with the lamest methods. This principle also lies behind the small movement of computing that has been slowly building since the rise of the Internet.

The theory is that certain interactable computing problems can be solved by tapping a little of the power from millions of computers connected to the Internet. Nearly 200 million personal computers mostly using Pentium or Power PC chips have been shipped here since 1995.

Most of the time these computers sit idle, waiting for their masters to order them to do some routine tasks, like playing 3D games, writing letters, browsing the Internet and so on.

What major scientific applications require this kind of massive social cooperation? There are many problems that require massive amounts of computation.

Social cooperation through cooperative computing is one way people participate in solving such a problem. But the problems have to lend themselves to being broken into small pieces that can be tackled with an ordinary personal computer.

They also cannot be real-time problems, since organizing people to submit the output in an orderly time manner can take a long time and is inefficient.

Prime Numbers

One of the best known and most successful projects involves the search for Mersenne prime numbers (http://www.mersenne.org/prime.htm), numbers that can be expressed in the form 2^n - 1 (read: 2 exponent n then minus 1). A prime number is a whole number that can only be divided exactly by one and itself.

For example, the first five prime numbers are: two, three, five and seven and 11. Six is not a prime number because it can be divided by one, two, three and six. By definition, M (n) = 2^n - 1. Thus the Mersenne prime for n=2 is 2^2 - 1, or 4 - 1, which equals 3, yes the output is a prime number.

A prime number is not always a Mersenne prime number, but a Mersenne prime number is always prime number. Hence, even though 11 is a prime number, you cannot express 11 in 2^n - 1 Mersenne prime number format, because the n variable has to be a prime number. If the n variable is not a prime number, it will absolutely not result in a prime number. This has been proven by the Lucas-Lehmer Theory. The bottom-line is if you enter a nonprime number into the n variable, you will definitely not get a prime number.

Therefore the basic principle of the Mersenne prime number is a Mersenne prime number always has a prime number for the n variable, but giving prime number for the n variable does not always yield a prime number.

Here is the proof of theory, 11 is a prime number, but 2^11 - 1 = 2,048 - 1 = 2,047 is not a prime number. If you don't believe it, please try to find a dividing factor of 2,047 using a spreadsheet program, like Excel(r) or Lotus 123(r). You will find that 2,047 is divisible by 23 and 89.

That's why we need the Lucas-Lehmer test to disprove a potential prime number by searching for a dividing factor. You can download the Lucas-Lehmer test program at http://www.mersenne.org/freesoft.htm. The program itself is written by George Woltman who is a retired computer programmer living in Orlando, Florida. A life-long number theory enthusiast, he founded the Great Internet Mersenne Prime Number Search (GIMPS) project in January 1996.

For your information, it took about 60 hours on a Pentium PC to verify 2^1,398,269 - 1, which is also known as M 1,398,269. But the beauty of the program is that it can run in the background, while your computer is working. It will not interfere with other programs or slow down your computer speed, because the program is a standalone exe file. You don't need to turn the power on your computer for a full 24 hours, because intermediate files are produced by the program itself to resume computation where it left off.

A total of 38 Mersenne prime numbers have been discovered. The current record holder for 38th Mersenne number is M (6,972,593) = 2^6,972,593 - 1. It is the largest prime number yet discovered.

It contains 2,098,960 digits. It was found on June 1, 1999 by Nayan Hajratwala. He used a 350 MHz Pentium II IBM Aptiva computer running part-time for 111 days to prove the number is a prime one. If run uninterrupted, it would take about three weeks to test the "prime behavior" of this number.

For comparison, imagination how big the 38th prime number is, M (17) = 2^17 - 1 = 131,072 - 1 = 131,071, thus M (17) is only six digits long. Can you imagine that? Sorry, I cannot write the digits of the 38th in this article, because I would have to key in 2,098,960 digits, my hands would get cramps and The Jakarta Post's today edition would not accommodate it. The use of the Mersenne prime number symbol M (n)= 2^n - 1 is to simplify the prime number symbol.

Other Purposes

You might be wondering what is the purpose of finding a Mersenne prime number? Prime numbers are interesting because they are not predictable, but can be discovered even though it takes a long time.

They are also a cornerstone of cryptography science since secured Websites, E-commerce and privacy protected e-mail use this technology. For your information, the U.S. government bans some specific cryptography software being exported outside U.S. territory.

This is because there are fears that the technology could infringe upon and jeopardize U.S. national security information and could be used in computer terrorism.

It is a fascinating idea of encouraging people to pool their computing power over the Internet, to work together to accomplish the time-consuming problem.

Perhaps it is the beginning of a new movement, call it global computational volunteerism. The concept and implementation reminds me of the Coca Cola company, which dreams of millions of dollars in revenue if it could only sell one-six pack a year to all 1.2 billion residents of China.

Providing a way to solve these problems efficiently, as well as large science problems, would make a better society, by using currently wasted resources to solve these people's problems.

By the way, if your computer is the one that hits the number, you will win US$100,000 (please read the official rules at http://www.eff.org/coop-awards/) and your name will be written in history as the person who found the 39th Mersenne prime number.

So if you can't do this for the love of science, do it for the love of money.