Read articles, including Science News stories written for ages 9-14, on the SNK website.
Largest known prime number found
The Great Internet Mersenne Prime Search, a cooperative computing project, helps find a prime that has nearly 13 million digits.
A+ A- Text Size
Enlarge
Printing out all 13 million digits in 12-point type would create a number 30 miles long. But here are a few of the digits, from the beginning and the end of the full number.Click here for a larger sampling.

Here’s a number to savor: 243,112,609-1.

Its size is mind-boggling. With nearly 13 million digits, it makes the number of atoms in the known universe seem negligible, a mere 80 digits.

And its form is tidy and lovely: 2n-1.

But its true beauty is far grander: It is a prime number. Indeed, it is the largest prime number ever found.

The Great Internet Mersenne Prime Search, or GIMPS, a computing project that uses volunteers’ computers to hunt for primes, found the prime and just confirmed the discovery. It can now claim a \$100,000 prize from the Electronic Frontier Foundation for being the first to find a prime number that has more than 10 million digits.

Prime numbers make up the “periodic table” of numbers, the building blocks that combine to form all numbers. A prime number is a whole number divisible only by 1 and itself. Euclid in 300 B.C. proved that there are infinitely many of them (click for his beautifully simple proof). Still, that doesn’t make them easy to find. At the beginning of the number line, the primes seem to be everywhere — 2, 3, 5, 7, 11, 13… — but in the number line’s more distant reaches, prime numbers become elusive.

Because 243,112,609-1 has the form 2n-1, it’s called a “Mersenne prime,” after a French monk born in the 16th century who made an (incorrect) conjecture about them. Mersenne primes are of particular interest partly because they can be expressed in such a compact form. (It sure is easier to write 243,112,609-1 than to type out all 13 million digits!) More significantly, though, some clever methods have been developed to identify them.

The most obvious way to go about identifying any prime number is to try factoring it. First, try dividing by 3, then 5, then 7, etc., and if none of them work, you’ve got a prime. But the last time a new prime was identified this way was in 1588, because as the numbers get bigger, the division takes longer and longer. So mathematicians have developed clever tests for primeness that are simpler to compute. The best one of all, called the Lucas-Lehmer test, only works for Mersenne primes. Remarkably, the method requires no division at all, making it extremely quick.

Only 46 Mersenne primes have ever been found, and GIMPS has found 12 of them. The project recruits volunteers to donate their computers’ CPU cycles when they would otherwise be idle. Each computer works on a single number, first trying to find small factors. If that fails, it applies the Lucas-Lehmer test. A computer working full-time can test a single 10-million-digit number in eight days.

The processing power of all the individual computers linked together is equivalent to one of the most powerful supercomputers in the world. No supercomputer, though, would devote all its processing time to computing prime numbers.

The finding is unlikely to have significance for number theory, although number theory’s great unanswered question, perhaps, is to find how the prime numbers are distributed. Still, “you never know where discoveries may lead you,” says George Woltman, founder of GIMPS. “But really, it’s like climbing Mt. Everest. You do it because it’s there. It’s a lot safer, though. You can do it from the air-conditioned comfort of your home.”

Or, if you prefer, the air-conditioned comfort of your office. The computer that found the prime was administered by Edson Smith at the University of California, Los Angeles mathematics department. Smith downloaded the GIMPS software, and when the computers in the math department weren’t busy with other work, they searched for primes and communicated their results back to GIMPS.

This prime is the eighth found at UCLA, although the first with GIMPS. Half the prize money will go to the UCLA math department, a quarter will go to charity (probably a math department with an open faculty position for number theory, Woltman says) and most of the remainder will go to those who found previous Mersenne primes using GIMPS.

Remarkably, GIMPS found another Mersenne prime two weeks after this one – after a two-year dry spell with no new primes. This prime had fewer digits, just 11 million.

The Electronic Frontier Foundation became interested in prime hunting because it makes an excellent challenge problem for cooperative, distributed computing. “The award is an incentive to stretch the computational ability of the Internet,” says Landon Noll of Cisco Systems Inc., one of the judges for the Electronic Frontier Foundation prize and a discoverer of a former biggest known prime. More prizes remain to be claimed: a \$150,000 award for a prime with 100 million digits, and a \$250,000 award for one with a billion digits.

GIMPS has used well-established methods, while continuing to refine its implementations for greatest efficiency. Finding the numbers for the larger awards, though, will require major innovations, Noll says: “People are going to have to go back to the drawing board.” He points out that testing a single 100-million–digit number for primeness would take a single desktop computer more than four years, and testing a billion-digit number would take it more than 500 years. So at a minimum, he says, algorithms will have to be developed that allow multiple computers to test a single prime.

Current cryptographic systems rely on the challenge of factoring large primes. This task is distinct from verifying primeness, but the root difficulty is the same: limited computing power. Through this prize, “we maintain a pulse on what people might be able to do in breaking cryptosystems,” Noll says.

Comment

GIMPS website: [Go to]

For an enormous amount of additional information on prime numbers, go to [Go to]

ARTICLES ON PAST BIGGEST PRIMES:

“New largest prime discovered” (2005; ~ 7.8 million digits) [Go to]

“Math Trek: Priming upward” (2004; ~ 7 million digits) [Go to]

“Searchers capture a champion megaprime” (2001; ~ 4 million digits) [Go to]

Please alert Science News to any inappropriate posts by clicking the REPORT SPAM link within the post. Comments will be reviewed before posting.

• "Factoring large primes"? Seriously?
Micah Transparent-Pseudonym
Sep. 26, 2008 at 1:57pm
• The discovery of the 13-million-digit prime number by UCLA mathematicians is really interesting.

I have always had an interest in very large numbers and number theory and the many, in fact in theory, the infinite number of possible future discoveries, patterns, and relationships among numbers in number theory.

The really cool thing about "numbers" themselves, especially positive integers is that one has to admit that they are relevant to absolutely every entity that exists. For those who believe in a Holy Trinity as God as I do, due to my Catholic upbringing, I have to say that the Three Divine Persons are simply that; "3" Divine Persons. Obviously, one can arrange these Persons in terms of the set of subsets of the Three Persons with the number of elements being equal (2 EXP 3) - 1. One can form the set of subsets of this set of subsets and so on to produce sets with infinitely many subsets.

For those who believe that each human being is an individual, or that each human soul is an individual entity, as well as the same for each angel, a similar argument applies.

It does not matter whether we are Atheists, Agnostic, Catholic, Born Again Christians, Jewish, Muslim, Buddhist, Taoist, Hindu, New Age, or whatever, we can all realize how ever present are numbers within the very order of creation and in the entire physical and spiritual cosmos.

Numbers are that intangible reality, that although embodied within even any spiritual realities, are not known to be spiritual realities in them selves. Neither are the numbers known to be physical realities. They seem to have their very own form of existence or being.

Knowing this should not cause those who believe in an absolutely ontologically simple God as I do to fret, for perhaps GOD created the numbers themselves, thus leading to the conclusion that God is even more ephemeral, sublime, and mysterious then any reified object of a number or reality of ordinality.

Just as physicists and cosmologists have perhaps an infinite universe to explore, so there is also and infinite mathematical landscape of topology, geometry, number theory, etc to explore.

Since the number of numbers in the set of the Cardinality of Aleph 1, which is the infinity that defines the number of real numbers, is larger than the cardinality of Aleph 0, the number of integers, there is an infinte number of relations between both the real numbers among themselves as well as between the positive integers among themselves. There are also an infinite number of species of algebraic equations, integral equations, differential equations, partial differential equations, integrals, derivatives, and the list goes on and on. There are also an infinite number spatial dimensions in abstract space and an infinite number of classes of manifolds in the infinite dimensional space.

The numbers of such mathenatical objects that can be contemplated by humanity is limitless, and thus, there is a whole eternity for mankind to explore the wonders of mathematics, which although perhaps being created by God, are the existential principles that underwrite the existence of all creatures, and the inter-relations between creatures.

Realities that defy being numbered or explained mathematically such as Truth, Beauty, Goodness, Love, Wisdom etc. completely trancend mathematics or ordinality. We do no speak of there being only one moral truth, because there can be an infinite number of aspects or laws of moral truth. Also we define the Moral Truth Incarnate as an aspect of God. The same non-ordinality applies to all of the other ontologically transcendent realities such as wisdom, goodness, peace, life, love etc. So all you artists who fear math, do not fret, because there are higher realities then math, not just as aspects of God, but also aspects of our moral, ontological, and existential makeup as children of God.
James Essig
Sep. 30, 2008 at 2:23pm