Welcome to the Great Internet Mersenne Prime Search! In case you ever forget, the URL is http://www.mersenne.org/prime.htm. FILE LIST --------- readme.txt This file. mprime The program to factor and run Lucas-Lehmer tests on Mersenne numbers. whatsnew.txt A list of new features in this version. database This required file is downloaded separately. It contains all the Mersenne exponents that still need testing. results Mprime writes its results to this file. Email this file to woltman@magicnet.net. pnnnnnnn & qnnnnnnn Intermediate files produced by mprime to resume computation where it left off. WHAT IS THIS PROGRAM? --------------------- This program is used to find Mersenne Prime numbers. See http://www.utm.edu/research/primes/mersenne.shtml for a good description of Mersenne primes. Mersenne numbers can be proved composite (not prime) by either finding a factor or by running a Lucas-Lehmer primality test. COMMAND LINE INTERFACE ---------------------- mprime [-c] [-d] [-f] [-m] [-q] [-r] [-s] [-t] range_start range_end -c The program needs to know your CPU type and speed to accurately estimate the time it takes to finish a range. Examples: -c3/166 Cyrix 6x86-P166+ -c4/80 80 MHz 486 -c5/133 133 MHz Pentium -c6/200 200 MHz Pentium Pro The program assumes you are running a 100 MHz Pentium unless you use this option. -d Double check a range. This option will run Lucas-Lehmer tests on exponents that have been checked once before. The purpose is to verify the results of the earlier Lucas-Lehmer test. -f Only find factors. Some people opt to find small factors of Mersenne numbers rather than run Lucas-Lehmer tests. -m Machine torture test. Runs a continuous self-test. Great for testing your systems cooling ability and memory subsystem. -q Be quiet. Normally, if the program finds a new Mersenne prime, it will beep like crazy. This option will prevent that. -r Range status. Prints the number of exponents that are left to be tested in a range. Also estimates the time it will take to complete that range. For example, to get a status report on the range 1234000 to 1234999 on a 166 MHz Pentium, type: mprime -c5/166 -r 1234000 1234999 -s Self-test. You should do this once on every machine you install this program. THREE PERCENT OF ALL COMPUTERS FAIL THIS TEST. This self-test will take about 9 hours. -t Test a specific prime. You do not need to use this option. Some people like to put mprime to the test by testing known Mersenne primes. For example, to see if M1279 is a Mersenne prime, type: mprime -t 1279 NOTE: Only the self-test (-s) and the range status (-r) options will print any results to the screen. All other options write their results to the "results" file. INSTRUCTIONS ------------ 1) Use the Web to select a range of exponents to test. Send me e-mail on the range you've chosen. This prevents others from testing the same range. Make sure you download the database too. After using pkunzip, you will need to rename the database from "DATABASE" to "database". If you do not have access to pkunzip, the database can be downloaded from http://www.magicnet.net/~woltman/database.gz. 2) Run mprime to get an idea of how long it will take to test the range you have selected. For example, if you checked out range 1234 to run on your Pentium Pro 180, type: mprime -c6/180 -r 1234000 1234999 3) Run mprime with a self-test a very low priority. Note that by including your range on the command line, mprime will start testing your range after completing the nine-hour self-test. Using the example above, type: nice -19 mprime -c6/180 -s or nice -19 mprime -c6/180 -s 1234000 1234999 or nice -19 mprime -c6/180 -s 1234000 1234999 > output & 4) Once the self-test completes, you can safely interrupt the program using ^C or kill. A checkpoint file will be written so the testing can resume where it left off. The last line of the results file will indicate how far along mprime is in testing your range. 5) The next time you run the program, you should not use the -s option. Using the example above, type: nice -19 mprime -c6/180 1234000 1234999 & You should do this whenever the computer is booted. 6) Let it run -- it runs at the lowest priority, making use of all your idle CPU cycles. Let it run overnight and on weekends. Never turn your computer off. Turn off your monitor to conserve energy. NOTE: Running your computer non-stop can increase your electric bill by $30 per year or more. 7) Once a month or when done with your range, send the file "results" to woltman@magicnet.net. It is important to do this so the exponents you've tested can be removed from the master list. NOTES ----- If you have chosen to help by finding factors of Mersenne numbers, you can omit steps 2 and 3 above. Also add the -f option to all the examples above. If you have chosen to help by double-checking previously tested exponents, then execute all the steps above except that you should add the -d option to every command line. Depending on the exponent being tested, the program may decide that it would be wise to invest a small amount of time checking for factors before running a Lucas-Lehmer test. Once you've started testing a range, there is no advantage in downloading a new database. After your range complets, you can download a new database before you start your next range. It can take many CPU days to test a large Mersenne number. This program can be safely interrupted by using the CTRL+C key or kill command. Intermediate results will be saved to disk. The program also saves intermediate results to disk every 30 minutes in case there is a power failure. If you have a dual processor machine, create two directories - each containing mprime and the database. Run two copies of the program giving half of your range to each copy of mprime. PROGRAM OUTPUT -------------- The results file will contain lines like: Factored M400037 through 17517*2^32 (pass 3 of 16). This means mprime is in the third pass of a 16 pass process to find a small factor of 2^400037-1. Iteration: 941400 / 1667747. This means mprime just finished the 941400th iteration of a Lucas-Lehmer primality test. The program must execute 1667747 iterations to complete the primality test. M2645701 has a factor: 13412891051374103 This means to 2^2645701-1 is not prime. It is divisible by 13412891051374103. M2123027 no factor to 2^57, WP0a: 14780E25 This means 2^2123027-1 has no factors less than 2^57. The Mersenne number may or may not be prime. A Lucas-Lehmer test is needed to determine the primality of the Mersenne number. WP0a is the program version number. 14780E25 is a checksum to guard against email transmission errors. M1992031 is not prime. Res64: 6549369F4962ADE0. WP0: B253EF24 This means 2^1992031-1 is not prime - a Lucas-Lehmer test says so. The last 64 bits of the last number in the Lucas-Lehmer sequence is 6549369F4962ADE0. At some future date, another person using another program will run the same Lucas-Lehmer test. If his last 64 bits match yours, then both machines ran flawlessly and it is 100% certain that the Mersenne number is composite. WP0 is the program version number. B253EF24 is a checksum to guard against email transmission errors. M11213 is prime! WP0: 579A579A This means 2^11213-1 is a Mersenne prime! WP0 is the program version number. 579A579A is a checksum to guard against email transmission errors. POSSIBLE HARDWARE FAILURE ------------------------- If the message, "Possible hardware failure, consult the readme file.", appears in the results file, then mprime's error-checking has detected a problem. Mprime will continue from the last save file. If you do not get the message, "Disregard last error...", then the problem is not reproducible - a definite sign of hardware problems. How can this be when none of your other programs have problems? The answer is that mprime stresses your machine more than any other program you run. The operating system usually shuts down the floating-point unit when no programs are using it. Mprime continuously uses the FPU, consuming more electricity and generating more heat. If the CPU is not properly cooled, errors can occur. Mprime also constantly accesses main memory - up to 60MB per second. This constant activity will detect memory problems that other programs do not. This is why Cray Research has used a program similar to this one as part of its supercomputer diagnostics package for over a decade. Could it be a software problem? There is a small chance that a device driver is not saving and restoring CPU state correctly. If the problem occurs only when a specific device is active, this could be the cause. How can you track down the hardware problem? Unfortunately, this is not easy. To see if your CPU is overheating, run mprime for several hours. Open the box. Is the CPU too hot to touch? If so, a heat sink or CPU fan should solve the problem. Memory problems are not as easy to diagnose. My only advice is to try swapping memory SIMMs with a coworker's or friend's machine. If the errors go away, then you can be confidant that the original problems were memory related. What can you do if you are unwilling or unable to find the hardware problem? If you are only getting an error once in a while, then your results are probably OK. The error-checking code is not infallible, so your results will need to be double-checked. If you are getting several errors during each primality test, then I would recommend using your machine to factor Mersenne numbers. DETAILS ------- This program uses the Lucas-Lehmer method to test if 2**p-1 is prime. The Lucas sequence is defined as: L[1] = 4 L[n+1] = (L[n]**2 - 2) mod (2**p - 1) 2**p-1 is prime if and only if L[p-1] = 0. This program uses a discrete weighted transform (see Mathematics of Computation, January 1994) to square numbers in the Lucas-Lehmer sequence. THANKS ------ Happy hunting and thanks for joining the search, George Woltman woltman@magicnet.net