Post by Acid Burn on Jun 21, 2006 12:51:05 GMT
Mersenne Numbers - A short tutorial for those of you wondering what the hell they are...
Mersenne numbers are named so after the franciscan friar Marin Mersenne and are simply numbers in the form M(n) = 2^n - 1 such that:
M(1) = 2^1 - 1 = 1
M(2) = 2^2 - 1 = 3
M(3) = 2^3 - 1 = 7 etc.
Mersenne primes are numbers in the Mersenne form which happen to be prime: M(p) = 2^n - 1 if 2^n - 1 is prime. E.g.
M(1) = 2^2 - 1 = 3
M(2) = 2^3 - 1 = 7
M(3) = 2^5 - 1 = 31 etc.
As a significant portion of the really large primes have been found to be Mersenne numbers, people searching for new 'biggest' prime numbers these days take the next untried Mersenne number and try to determine whether or not it is prime. If not, they move onto the next. However, this isn't a half an afternoon's processor time on a PC, the numbers being tested for primality to find the next Mersenne prime (number 40*) have over 4 million digits. The people in the prime race now use distributed computing programs. This is a plus for both sides: the software authors get access to the equivalent processing time of many supercomputers (for free!); the layman gets a chance to break the world record biggest prime number without having the mathematical or programming knowledge that would have otherwise been required. The distributed search is called GIMPS (Great Internet Mersenne Prime Search) and although the name really does suck, you can download the software and join the search here: www.mersenne.org
I will try and stick a sort of sequel on here soon dealing with primality testing (mainly the Lucas-Lehmer method).
* At the time I wrote this, they had found 39, but weren't sure if there were any more between the 38th and the largest. (i.e. their 39th could actually have now turned out to be the 41st). Also, they may be looking for number 46 when you read this, or 47 or 48 etc
Mersenne numbers are named so after the franciscan friar Marin Mersenne and are simply numbers in the form M(n) = 2^n - 1 such that:
M(1) = 2^1 - 1 = 1
M(2) = 2^2 - 1 = 3
M(3) = 2^3 - 1 = 7 etc.
Mersenne primes are numbers in the Mersenne form which happen to be prime: M(p) = 2^n - 1 if 2^n - 1 is prime. E.g.
M(1) = 2^2 - 1 = 3
M(2) = 2^3 - 1 = 7
M(3) = 2^5 - 1 = 31 etc.
As a significant portion of the really large primes have been found to be Mersenne numbers, people searching for new 'biggest' prime numbers these days take the next untried Mersenne number and try to determine whether or not it is prime. If not, they move onto the next. However, this isn't a half an afternoon's processor time on a PC, the numbers being tested for primality to find the next Mersenne prime (number 40*) have over 4 million digits. The people in the prime race now use distributed computing programs. This is a plus for both sides: the software authors get access to the equivalent processing time of many supercomputers (for free!); the layman gets a chance to break the world record biggest prime number without having the mathematical or programming knowledge that would have otherwise been required. The distributed search is called GIMPS (Great Internet Mersenne Prime Search) and although the name really does suck, you can download the software and join the search here: www.mersenne.org
I will try and stick a sort of sequel on here soon dealing with primality testing (mainly the Lucas-Lehmer method).
* At the time I wrote this, they had found 39, but weren't sure if there were any more between the 38th and the largest. (i.e. their 39th could actually have now turned out to be the 41st). Also, they may be looking for number 46 when you read this, or 47 or 48 etc