Executive SummaryDescription of ProjectResultsConclusionAcknowledgments

Result Graphics2^21701-1Team DynamicsProgram CodeReferences

II. Description of Project

In 1644, Marin Mersenne stated in Cogitata Physica-Mathmatica that numbers in the form of 2n-1 were prime when n=2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257. Although he was not the first person to demonstrate this pattern in prime numbers, his name became associated with it.

By 1996, only 35 Mersenne numbers have been found and proven to be prime, the latest of which took thousands of computational hours on the worldís most powerful computers. This number was over 420,000 digits in length. Mathematicians have been usi ng various programming languages and algorithms to search for large prime numbers. Thirty-five Mersenne numbers have been found; the number 2216091-1 is the thirty-first Mersenne prime, and all numbers less than that have been tested. The reg ions between this number and the other four known Mersenne primes has not been fully tested. Computers around the world continue to scan these regions, and the vast realm beyond the largest known prime.

Numbers of this length can be used for high powered encryption, allowing secure data transfer on any computer. Data can be encrypted into a key using prime numbers. Without the proper key, it is virtually impossible to decrypt the data, as one has to go through the lengthy process of finding the key to decrypt the numbers. With the advent of faster computers, computer users must use larger primes in encryption to secure their data and deter hackers.

Programs that generate or factor Mersenne primes are also used to test the speed and accuracy of new computer chips. These programs require everything a chip will need in normal usage, and thus make perfect tests for them. For example, Cray compu ters are tested using this type of program before they are sold to ensure quality performance.

The purpose of this project is to generate large Mersenne numbers to investigate number theory and to test the speed of various computers. With this program we can explore patterns in large numbers, performance in the computer systems that we are using and other applications into which time did not permit us to delve.

Mersenne numbers, numbers in the form 2n-1, are generated and used in the search for prime numbers because there is a higher probability that these numbers will lead to a prime number, specifically if n is prime. Mersenne numbers also g ive us an easy way to write the prime, as n is much smaller and easier to work with than the prime number 2n-1 itself, of which the last prime number is over 100 pages long, while n is only seven digits long. This allows for easy referencing an d compatibility in testing.

There are many methods of testing suspected prime numbers, including the Sieve of Eratosthenes, which is the only program which gains speed as it progresses but requires huge resources to implement effectively. Another method of finding Mersenne p rimes is the Lucas-Lehmer test:

For p odd, the Mersenne number 2p-1 is prime if and only if 2p-1 divides S(p-1) where S(n)2-2, and S(1)=4.

In programs, however, it can be faster to factor a suspected prime by trial-and-error than run through such algorithms.

Our initial expedition to the libraries around New Mexico and to the Internet led us to Mersenne primes. This topic was simple enough for the diversity of our group, yet immense enough to merit the use of high-performance machines. Using resources on the Internet, we found a cross-reference list of known Mersenne primes with which we could compare and test the results of our program for smaller numbers before we moved on to larger numbers.

We initially tried to create a program that would allow input of any value of n into a factoring algorithm that would test whether or not 2n-1 was a Mersenne prime number. In testing our program we ran into a problem with the precision r ange of the computer. Computers have different accuracy depending on the compiler; for example, a computer may add one to a million and still believe that it is the number one million. This is due to the fact that most computers are used for physical si mulations where the power of ten is more important than the actual number. With that problem in hand we decided to create a program that would work with these limitations. At the time that we ran into that problem, we had an almost completed generation program, which created Mersenne numbers of any size that would be allowed by the computerís memory. The completed program allows us to generate all the Mersenne prime numbers to date. We could not factor them, however, due to the precision problem descr ibed above and decided to change the scope of our program.

With this problem in mind, we decided to work more heavily on the creation of Mersenne numbers instead of the testing of them. Every form of factorization that we could have tested didnít work because of this same problem, and with the consultatio n of our coaches we decided that it would be best to leave our program with a plain trial and error factorization algorithm, instead of trying other methods. The trial and error algorithm starts out by factoring a number and dividing it in a counting loo p starting with two until it finds a factor, at which point in time it will print the factor to a file. The loop will then restart with the quotient and will continue dividing by trial and error, starting with the divisor, until the number is factored co mpletely, which will be the point in time when the divisor equals the dividend.

The generator program uses an array to avoid the problem of precision in the computer by making each member of the array account for one digit of the number. The program starts with a set length of the array and places the number two in the last d igit. It then loops, multiplying each member of the array by two; if any member of the array becomes greater than nine, it then changes the number so that each member of the array consists of one member of the number being generated. For example, 8 x 2 = 16, so the program adds 1 to the next member of the array for the tenís place and leaves the 6 in the original array. By checking each member of the array, we ensure that each member of the array will be correct. To ensure that it is a Mersenne prime w e must subtract one from the last member of the array. We do not have to check the last member of the array to make sure that we are not subtracting one from zero because the last digit of any 2n number will always end in 2, 4, 6, or 8.

Our final project includes the generation program that we have tested on the Supercomputers Pi and Rho and a factor program that factors all numbers less than 261-1.

With more time, we would have liked to work around the problem with precision such as to allow us to factor the Mersenne numbers to test whether they are prime. If we had done this, we might have been able to scan the regions between the larger kn own Mersenne primes. We would have also investigated encryption more. Amber and Alan integrated the code for generating Mersenne Primes and the factorization program into an HTML document for the World Wide Web. The web page utilizes simple forms to se lect which program you wish to use and allows you to enter a number and a "nickname" you wish to give the results so that you can easily find it when the results are posted every Tuesday. The page is at: http://mode.lanl.gov/~ch006acr/input.html