Created by Materia for OpenMind Recommended by Materia
4
Start Hunting for Prime Numbers: Who Cares and Why?
23 September 2019

Hunting for Prime Numbers: Who Cares and Why?

Estimated reading time Time 4 to read

More than 3,550 years ago, an Egyptian scribe named Ahmes wrote a papyrus on which he recorded differently those fractions whose denominators were prime numbers. The data is often cited as a sign that the knowledge and search for these peculiar numbers are almost as old as human thought, a search that has reached almost inconceivable heights in the last couple of decades. But what is the point of hunting for ever-larger prime numbers?

The mathematic papyrus of Amhes. Credit: Paul James Cowie
The mathematic papyrus of Amhes. Credit: Paul James Cowie

The definition of a prime number is so simple that it is learned in primary school: it is that natural number greater than 1 that can only be divided exactly by 1 and by itself. In fact, this apparent simplicity is part of its appeal, according to what Adrian Dudek, a mathematician from Australian National University, tells OpenMind: “I think the fascination for prime numbers comes from the fact that they are so elementary in description but yet incredibly difficult to analyse. A young child can understand what makes a number prime, yet lifetimes of mathematical research have been spent trying to solve some of the problems in the field.”

The first known person to look specifically at this subject was the Greek mathematician Euclid of Alexandria, who around 300 B.C. demonstrated for the first time that prime numbers are infinite. A century later, another Greek mathematician, Eratosthenes, created a screening method that allows all the prime numbers of a limited list to be identified, simply by crossing out multiples.

The Mersenne primes

After the Greeks, interest in prime numbers was only revived at the end of the Middle Ages. At the beginning of the 17th century, French monk Marin Mersenne defined the prime numbers that bear his name, obtained as Mp = 2p – 1. If p is a prime number, it is possible, though not certain, that Mp is also a prime number. Already in 1588, Italian mathematician Pietro Cataldi had shown that 219 – 1 = 524,287 is prime, setting a record for his time. The Mersenne primes became the mathematicians’ preferred target thanks to tests such as the Lucas-Lehmer primality test, which facilitates verification. Édouard Lucas himself, a French mathematician, demonstrated in 1876 that 2127 – 1 is a prime. This 39-digit number remains the highest prime discovered by manual calculations.

El monje francés Marin Mersenne definió los primos que llevan su nombre: Fuente: Wikimedia
French monk Marin Mersenne defined the prime numbers that bear his name. Source: Wikimedia

In 1951 computers began to be used to calculate even larger new prime numbers. That year a new record was set with a 79-digit number, but this number began to grow rapidly with advances in computing. In 1989 the largest prime number was 65,087 digits; ten years later, Mersenne’s prime M6972593 reached 2,098,960 digits.

The great leap from thousands to millions of digits came about mainly because of one person. In 1996, the American George Woltman, from the Massachusetts Institute of Technology, founded the Great Internet Mersenne Prime Search (GIMPS), a distributed computing project that searches for new Mersenne primes and in which any user can participate by downloading the software Prime95, created by Woltman.

Since then, all new primes have been discovered by GIMPS users. The current record is held by the 51st known Mersenne prime. This real colossus, M82589933, discovered on December 7, 2018 by Florida programmer Patrick Laroche, reaches the unimaginable length of 24,862,048 digits; if someone were to try to print it on paper, almost 10,000 sheets would be needed.

And the search goes on. As Woltman tells OpenMind, “GIMPS will continue to forge ahead over the coming years. Our progress is dependent on the number of users and advancements in hardware.” Of course, there can be a reward for hunters: GIMPS awards $3,000 for new discoveries, and both the Woltman project and its participants are eligible for the awards given by Electronic Frontier Foundation, which currently offers a $150,000 purse to anyone finding a prime over 100 million digits long.

The utility of gigantic primes

But leaving aside the economic incentive or the headlines, what motivates this search? For mathematicians, the importance of prime numbers is indisputable; since the rest of the natural numbers are broken down into a product of primes, they are considered building blocks in number theory. “If you want to understand a building, how it will react to a storm or earthquake, you must first know what it is made of,” University of Tennessee mathematician Chris Caldwell, discoverer of prime numbers and author of The Prime Pages website, which maintains a list of the top 5,000 known, tells OpenMind. “I find primes beautiful because of the ubiquity, their myriad of uses, and what appears to be randomness in their distribution.” Moreover, they are at the heart of such famous mathematical problems as Goldbach’s conjecture or the Riemann hypothesis.

However, despite the theoretical purity defended by mathematicians, the truth is that prime numbers have also brought great practical benefits to humanity, such as electronic commerce. In 1977, three researchers designed RSA cryptography (using the initials of Rivest, Shamir and Adleman), based on the known product of two large prime numbers, which can only be deciphered by those who know the factors. This type of encryption, called asymmetric or public key, is used for encryption on the Internet, for example in digital signatures, and is the most important current application of large prime numbers. However, only numbers with a few hundred digits are used; it would be unthinkable to use the giant primes known today.

3248 primes among the numbers from 0 to 30029. -prime numbers
3248 primes among the numbers from 0 to 30029. Credit: Niek Sprakel

So, do these numerical giants have any specific uses? For Martin Weissman, a mathematician at the University of California at Santa Cruz, the search for gigantic primes “is interesting, but not very important,” beyond stimulating interest in mathematics. “If someone found a new algorithm that quickly determined whether a number with millions of digits was prime, that would be interesting to me,” he tells OpenMind. For Weissman, classical problems such as the Riemann hypothesis will focus interest on the field of prime numbers in the coming decades.

But even if technologies like Artificial Intelligence or quantum computers break down current barriers in computing, “it’s highly unlikely that gigantic prime numbers will ever be used in the same way that currently large primes are used,” University of Portsmouth mathematician Ittay Weiss tells OpenMind. And this is not only because of the difficulty in computing them, but also because it would not contribute anything relevant. However, Weiss speculates that these numbers could be used to test new computers or algorithms, as is currently done with millions of decimals of pi. “Perhaps huge primes can serve a similar purpose,” he suggests.

Ultimately, according to Woltman, “the point of the search is primarily just for fun. There is great joy in discovering a new, exceedingly rare, and interesting item. Mankind loves to break records like building the fastest car, exploring new territory like outer space, and challenging oneself like climbing Mt. Everest.” And, as Caldwell says, “the journey is often more important than the destination.”

Javier Yanes

@yanes68

Related publications

Comments on this publication

Write a comment here…* (500 words maximum)
This field cannot be empty, Please enter your comment.
*Your comment will be reviewed before being published
Captcha must be solved