
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] [-n] [-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.

-n	Output process ID to a file.  Sometimes you need to know the pid
	of mprime to work with daemons and auto-run scripts.  You can
	write this number out to a file via -nFILENAME like:
		mprime -q -N/var/lock/mprime.pid 1234000 1234999 

-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
