Mersenne Primes

Marin Mersenne (1588-1648) was a Franciscan friar who lived most of his life in Parisian cloisters. He was the author of Cognitata Physico-Mathematica which stated without proof that Mp is prime for p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, and 257 and for no other primes p for p < 257. It took over 300 years to totally settle this claim made by Mersenne. The final work done in 1947 showed that Mersenne made five errors in his work (namely that M61 is prime, M67 is composite, M89 is prime, M107 is prime, and M257 is composite). Besides his famous statement about primes of the form Mp, Mersenne contributed to the development of number theory through his extensive correspondence with many mathematicians, including Fermat. Mersenne effectively served as a clearing house and a disseminator of new mathematical ideas in the 17th century.

Kenneth Rosen, Elementary Number Theory; Addison Wesley

The concept of a Mersenne Prime is evolved from that of a perfect number. A perfect number is an integer for which the sum of its divisors is twice the number. For example:

	(6) = 1 + 2 + 3 + 6 = 12 = 2*6
	thus 6 is a perfect number.

The greeks discovered that all perfect numbers were of the form:

	n = 2^(m-1) * (2^m - 1)
	where m >= 2 and (2^m - 1) is prime.

It can be proven that if m is a positive integer and 2^m - 1 is prime, that m must be prime. This means that the quest for perfect numbers is reduced to the quest for primes of the form:

	2^m - 1

A Mersenne Prime is such a number Mp, where p is prime.

A Mersenne Number is a number Mm which may or may not be prime.

There are additional theorems which can be used to determine properties of Mersenne Numbers. One states:

	If p is an odd prime, then any divisor of 
	the Mersenne number Mp = 2^p - 1 is of the
	form 2kp + 1 where k is a positive integer.

This leads instantly to a method of testing the primality of Mp. We know that any prime factors must be less than the square root, and we know from above that they must be of the form 2kp + 1. This is likely the method used by Mersenne to determine the primality of the Mersenne numbers for m < 257.

The Lucas-Lehmer Test

I don't know anything about the development of this algorithm,

Let p be a prime and Mp = 2p - 1 the pth Mersenne number. Then define a recursive sequence by setting R1 = 4, and k >= 4,

	Rk = (Rk-1)^2 - 2 (mod Mp),

	for 0 <= Rk < Mp.

Then Mp is prime if and only if Rp-1 = 0 (mod Mp).

In pseudo code,

	R = 4;
	for (i = 2; i > p; i++) {
		R = R*R;
		R -= 2;
		R = R mod Mp
	}
	if (R == 0)
		Mp is prime

In practice this is limited by the O(N^2) cost of multiplication. The technique used to evade this cost is to use FFTs to do your multiplication for you. I still don't really understand how that works.

Known Mersenne Primes

There are currently 33 known Mersenne Primes. The upper limits are reserved to those with more supercomputer power than is good for humans to possess. They seem to be discovered every two years or so.

	List the numbers here

banshee@resort.com

Your links back to The Resort