Science

The never-ending quest for enormous prime numbers

That’s Maths: As they get larger, prime numbers spread out, separated by growing gaps which make the search more challenging

Prime numbers play a central role in pure mathematics, in the field of number theory and in a wide range of applications. Photograph: Thinkstock
Prime numbers play a central role in pure mathematics, in the field of number theory and in a wide range of applications. Photograph: Thinkstock
Peter Lynch
Thu Nov 21 2024 - 06:00

The ongoing search for ever-larger prime numbers continues apace. Primes are the atoms of arithmetic: every whole number is a unique product of primes. For example, 21 is the product of primes three and seven, while 23 is itself prime.

The primes play a central role in pure mathematics, in the field of number theory and in a wide range of applications. They are essential in cryptography: the security of financial systems and of the internet depend upon algorithms using the unique properties of prime numbers.

Recently, the record for the largest prime number has been shattered once again. Last month, Luke Durant, a researcher in San Jose, California, discovered a prime number with more than 40 million decimal digits. A printout of this number would require more than 20 reams of paper, comparable to a large encyclopedia and weighing perhaps 50kg. Durant used the sophisticated software of the Great Internet Mersenne Prime Search (GIMPS), running on a cloud computer network distributed over 17 countries.

A ‘Mersennery’ quest

READ MORE

The record for the largest prime is broken on a regular basis. Nearly all the recent examples have been found by GIMPS, a collaborative project in which volunteers use freely available software to search for Mersenne primes. These special primes were first studied by Marin Mersenne, a French friar born in 1588. Mersenne corresponded with mathematical luminaries in many countries, René Descartes and Étienne Pascal among them, providing a vital communication channel – like a one-man internet hub.

Around 300 BC, Euclid proved there is no largest prime number: however far we search, there remains an infinite store of primes awaiting discovery, so the search is never-ending

Mersenne numbers are constructed by repeatedly multiplying two by itself and finally subtracting one. The first few such numbers are one, three, seven, 15 and 31. Some of them are prime while some are not; highly efficient algorithms have been devised to check them for primality. GIMPS seeks Mersenne primes using a clever method called the Lucas-Lehmer test and, since 2018, the Fermat primality test.

While the Lucas-Lehmer test is deterministic, giving an unequivocal result, the Fermat test is only probabilistic; however, pseudoprimes which pass the Fermat test but are not prime are exceedingly rare and are easily detected by further checks. To date, the GIMPS project has found 18 record primes, averaging a new one every year or two. But the latest find has come nearly six years after the previous one. As they get larger, the prime numbers spread out, separated by growing gaps which make the search more challenging.

Value for money?

The study of prime numbers dates back at least to the ancient Greeks. Around 300 BC, Euclid proved there is no largest prime number: however far we search, there remains an infinite store of primes awaiting discovery, so the search is never-ending. So why would we bother searching for more?

To find the new prime, Luke Durant availed of supercomputer power from a global assembly of processors. In a recent interview on YouTube, he estimated the cost to be “under $2 million”.

Was this money well spent? It depends on who you ask. One argument in support of it is the spin-off benefits of mathematical advances made during the quest. Another is the incentive to devise better computational algorithms. A third is the sheer joy of the quest: we seek ever-larger primes “because they are there”.

Peter Lynch is emeritus professor at the School of Mathematics & Statistics, University College Dublin. He blogs at thatsmaths.com