What is a Mersenne number

A Mersenne number is an integer number in the the form

     M(p) = 2^p - 1

The number p is the Mersenne exponent. Its binary representation is just a chain of p ones. This kind of numbers have a lot of nice properties which make them easier than a general integer. You can read a lot more about Mersenne numbers at Chris Caldwell's Mersenne Primes pages.

The special form of Mersenne numbers gives us three big advantages:

• There is a fast test (See Lucas-Lehmer test.) If it succeeds we are sure the analyzed number is a prime number. If it fails then we are sure the number is not prime.

• The modular reduction we need can be made in a easy way. (See Glucas internals.)
• The algorithm used to multiply the very big numbers we usually need (about some million bits) uses a special form of Fast Fourier Transform, the Discrete Weighted Transform (DWT) described by R. Crandall and Fagin (1994). With DWT, the speed is almost double than traditional FFT schemes.

Mersenne primes

It is a well known result that M(p) is prime only if p is prime. Unfortunately, if p is prime this does not mean M(p) is prime. Actually, up to 13 June 2009 there are only 47 known Mersenne primes.

The values of mersenne exponents p for M(p) prime are:

     2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281,
     3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243,
     110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377,
     6972593, 13466917, 20996011, 24036583, 25964951, 30402457, 32582657,
     37156667, 42643801, 43112609