Tech revolutionizes centuries-old search for prime numbers

UPI

a day ago

A laptop represents today's tools fueling the global search for massive prime numbers, essential for both mathematics and cybersecurity. Photo by Tony Avelar/EPA
May 30 (UPI) -- A shard of smooth bone etched with irregular marks dating back 20,000 years puzzled archaeologists until they noticed something unique - the etchings, lines like tally marks, may have represented prime numbers. Similarly, a clay tablet from 1800 B.C.E. inscribed with Babylonian numbers describes a number system built on prime numbers.
As the Ishango bone, the Plimpton 322 tablet and other artifacts throughout history display, prime numbers have fascinated and captivated people throughout history. Today, prime numbers and their properties are studied in number theory, a branch of mathematics and active area of research today.
A history of prime numbers
Informally, a positive counting number larger than one is prime if that number of dots can be arranged only into a rectangular array with one column or one row. For example, 11 is a prime number since 11 dots form only rectangular arrays of sizes 1 by 11 and 11 by 1. Conversely, 12 is not prime since you can use 12 dots to make an array of 3 by 4 dots, with multiple rows and multiple columns. Math textbooks define a prime number as a whole number greater than one whose only positive divisors are only 1 and itself.
Math historian Peter S. Rudman suggests that Greek mathematicians were likely the first to understand the concept of prime numbers, around 500 B.C.E.
Around 300 B.C.E., the Greek mathematician and logician Euler proved that there are infinitely many prime numbers. Euler began by assuming that there is a finite number of primes. Then he came up with a prime that was not on the original list to create a contradiction. Since a fundamental principle of mathematics is being logically consistent with no contradictions, Euler then concluded that his original assumption must be false. So, there are infinitely many primes.
The argument established the existence of infinitely many primes, however it was not particularly constructive. Euler had no efficient method to list all the primes in an ascending list.
In the middle ages, Arab mathematicians advanced the Greeks' theory of prime numbers, referred to as hasam numbers during this time. The Persian mathematician Kamal al-Din al-Farisi formulated the fundamental theorem of arithmetic, which states that any positive integer larger than one can be expressed uniquely as a product of primes.
From this view, prime numbers are the basic building blocks for constructing any positive whole number using multiplication - akin to atoms combining to make molecules in chemistry.
Prime numbers can be sorted into different types. In 1202, Leonardo Fibonacci introduced in his book "Liber Abaci: Book of Calculation" prime numbers of the form (2p - 1) where p is also prime.
Today, primes in this form are called Mersenne primes after the French monk Marin Mersenne. Many of the largest known primes follow this format.
Several early mathematicians believed that a number of the form (2p - 1) is prime whenever p is prime. But in 1536, mathematician Hudalricus Regius noticed that 11 is prime but not (211 - 1), which equals 2047. The number 2047 can be expressed as 11 times 89, disproving the conjecture.
While not always true, number theorists realized that the (2p - 1) shortcut often produces primes and gives a systematic way to search for large primes.
The search for large primes
The number (2p - 1) is much larger relative to the value of p and provides opportunities to identify large primes.
When the number (2p - 1) becomes sufficiently large, it is much harder to check whether (2p - 1) is prime - that is, if (2p - 1) dots can be arranged only into a rectangular array with one column or one row.
Fortunately, Édouard Lucas developed a prime number test in 1878, later proved by Derrick Henry Lehmer in 1930. Their work resulted in an efficient algorithm for evaluating potential Mersenne primes. Using this algorithm with hand computations on paper, Lucas showed in 1876 that the 39-digit number (2127 - 1) equals 170,141,183,460,469,231,731,687,303,715,884,105,727, and that value is prime.
Also known as M127, this number remains the largest prime verified by hand computations. It held the record for largest known prime for 75 years.
Researchers began using computers in the 1950s, and the pace of discovering new large primes increased. In 1952, Raphael M. Robinson identified five new Mersenne primes using a Standard Western Automatic Computer to carry out the Lucas-Lehmer prime number tests.
As computers improved, the list of Mersenne primes grew, especially with the Cray supercomputer's arrival in 1964. Although there are infinitely many primes, researchers are unsure how many fit the type (2p - 1) and are Mersenne primes.
By the early 1980s, researchers had accumulated enough data to confidently believe that infinitely many Mersenne primes exist. They could even guess how often these prime numbers appear, on average. Mathematicians have not found proof so far, but new data continues to support these guesses.
George Woltman, a computer scientist, founded the Great Internet Mersenne Prime Search, or GIMPS, in 1996. Through this collaborative program, anyone can download freely available software from the GIMPS website to search for Mersenne prime numbers on their personal computers. The website contains specific instructions on how to participate.
GIMPS has now identified 18 Mersenne primes, primarily on personal computers using Intel chips. The program averages a new discovery about every one to two years.
The largest known prime
Luke Durant, a retired programmer, discovered the current record for the largest known prime, (2136,279,841 - 1), in October 2024.
Referred to as M136279841, this 41,024,320-digit number was the 52nd Mersenne prime identified and was found by running GIMPS on a publicly available cloud-based computing network.
This network used Nvidia chips and ran across 17 countries and 24 data centers. These advanced chips provide faster computing by handling thousands of calculations simultaneously. The result is shorter run times for algorithms such as prime number testing.
The Electronic Frontier Foundation is a civil liberty group that offers cash prizes for identifying large primes. It awarded prizes in 2000 and 2009 for the first verified 1 million-digit and 10 million-digit prime numbers.
Large prime number enthusiasts' next two challenges are to identify the first 100 million-digit and 1 billion-digit primes. EFF prizes of US$150,000 and $250,000, respectively, await the first successful individual or group.
Eight of the 10 largest known prime numbers are Mersenne primes, so GIMPS and cloud computing are poised to play a prominent role in the search for record-breaking large prime numbers.
Large prime numbers have a vital role in many encryption methods in cybersecurity, so every internet user stands to benefit from the search for large prime numbers. These searches help keep digital communications and sensitive information safe.
Jeremiah Bartz is an associate professor of mathematics at University of North Dakota. This article is republished from The Conversation under a Creative Commons license. Read the original article. The views and opinions in this commentary are solely those of the author.