Prime Number Record Smashed Again

Once again the record for the largest prime number has been shattered. As with all recent records, the new number is a Mersenne prime, a number of the form

Mp = 2p 1

where p itself is a prime. Participants in a distributed computing project called GIMPS (Great Internet Mersenne Prime Search) continue without rest to search for ever-larger primes of this form.

Most of the recent large primes have been found in the GIMPS project (for an earlier post on GIMPS, click Mersennery Quest. The project uses a search algorithm called the Lucas-Lehmer primality test, which is particularly suitable for finding Mersenne primes. The test, which was originally devised by Edouard Lucas in the nineenth century and extended by Derek Lehmer in 1930, is very efficient on binary computers.

Recently at the University of Central Missouri a mathematics professor, Curtis Cooper, found the new Mersenne prime,

M(74,207,281) = 274 207 281 – 1.

Using the approximation 210 103, we can see that it has approximately 22 million decimal digits. The previous record had “only” 17 million digits. The new prime was found last September but, due to email glitches, was not confirmed until 7 January. With 5,000 digits per page, the new record number would require about 4400 pages to print in decimal form.

Mersenne numbers are defined as numbers of the form

Mk = 2k – 1.

It is simple to show that if k is composite then so is Mk. But if p is a prime, then Mp may or may not be prime too. Prime numbers of the form Mp = 2p – 1 are called Mersenne primes, and almost all the largest known primes are of this form.

Lucas-Lehmer Test (LLT)

We define a sequence of numbers Lk called the Lucas-Lehmer sequence, as follows:

L1 = 4 and Ln = (Ln-1)2 – 2 for n > 1 .

This rule yields the sequence { 4, 14, 194, 37 634, 1 416 317 954, … } in which the terms rapidly grow. The Lucas-Lehmer Test (LLT) may be stated as a

Theorem: Mp is prime if and only if Lp-1 0 mod Mp.

In other words, Mp is prime if and only if Mp divides Lp-1 exactly. The Lucas-Lehmer numbers grow rapidly, and soon break the limits of most computers, but it is sufficient to compute the terms modulo Mp, keeping them within reasonable bounds.

The Lucas-Lehmer Test can be implemented in just a few lines of computer code. The following is a Mathematica version of the test:

LLT-Program

This is simple to implement in any other high-level computer language. Much of the computation time is taken up squaring the Lucas-Lehmer numbers repeatedly, but faster algorithms can be used to reduce the computation time drastically.

Some results for the first few values of p are shown in the following table. We see that some of the examples are prime whereas others, M11 and M23 are composite. For example, M11 = 2047 = 23*89 and M23 = 8388607 = 47*178481.

LLT-Table

 A more detailed discussion of the Lucas-Lehmer test, and proofs of the results, can be found in standard works on number theory, such as Hardy and Wright. See also the Mersenne Wiki (URL below).

Sources

  • Hardy, Godfrey Harold and Wright, E. M. (1960): An introduction to the theory of numbers (Fourth Ed.), Oxford, at the Clarendon Press.

  • Mersenne Wiki: The wiki is for the Great Internet Mersenne Prime Search.


Last 50 Posts

Categories