Largest prime number discovered: Why that matters
Special to The Weather Network
Wednesday, January 10, 2018, 8:01 PM - In the movie Contact, based on the novel of the same name by Carl Sagan, Dr. Ellie Arroway searches for intelligent extraterrestrial life by scanning the sky with radio telescopes. When Arroway, played by Jodie Foster, recognizes prime numbers in an interplanetary signal, she believes it’s proof that an alien intelligence has sent the human race a message.
A number is considered prime if it is only divisible by one and itself. For example, two, three, five and seven are prime. The number 15, which is three times five, is not prime. It’s no coincidence that Arroway believes the aliens in Contact use prime numbers as a cosmic “hello” — they are building blocks of other numbers. Every number is a product of primes.
In December 2017, the largest known prime number was discovered using a computer search. The prime was discovered by Jonathan Pace, an electrical engineer who currently works at FedEx. Why is this important? Because without prime numbers your banking information, Paypal transactions or Amazon purchases could be compromised.
Large primes, like the one just discovered, play a critical role in cyber-security. Cryptography is the science of encoding and decoding information, and many of its algorithms, such as RSA, rely heavily on prime numbers.
Bitcoin and other crypto-currencies use security that depends on prime numbers. (Shutterstock)
Mersenne primes
While there are infinitely many primes, there is no known formula to generate them all. A race is ongoing to find larger primes using a mixture of math techniques and computation.
One way to get large primes uses a mathematical concept discovered by the 17th-century French monk and scholar, Marin Mersenne.
A Mersenne prime is one of the form 2ⁿ - 1, where n is a positive integer. The first four of these are three, seven, 31 and 127.
Not every number of the form 2ⁿ - 1 is prime, however; for example, 2⁴ - 1 = 15. If 2ⁿ - 1 is prime, then it can be shown that n itself must be prime. But even if n is prime, there is no guarantee the number 2ⁿ - 1 is prime: 2¹¹ - 1 = 2,047, which is not prime becauase it equals 23 times 89.
There are only 50 known Mersenne primes. An unresolved conjecture is that there is an infinite number of them.
VIDEO: NASA CHIEF SCIENTIST PREDICTS ALIEN DISCOVERY BY 2025:
The search for new primes
The Great Internet Mersenne Prime Search (or GIMPS) is a collaborative effort of many individuals and teams from around the globe to find new Mersenne primes. George Woltman began GIMPS in 1996, and in 2018 it includes more than 183,000 volunteer users contributing the collective power of over 1.6 million CPUs.
The most recently discovered Mersenne prime is succinctly written as 2⁷⁷²³²⁹¹⁷ - 1; that’s two multiplied by itself 77,232,917 times, minus one. Jonathan Pace’s discovery took six days of computation on a quad-core Intel i5-6600 CPU, and was independently verified by four other groups.
The newly discovered prime has a whopping 23,249,425 digits. To get a sense of how large that is, suppose we filled up a book with digits, each digit counted as a word and each book having 100,000 words. Then the digits of 2⁷⁷²³²⁹¹⁷ - 1 would fill up about 232 books!
How does GIMPS find primes?
GIMPS uses the Lucas-Lehmer test for primes. For this, form a sequence of integers starting with four, and whose terms are the previous term squared and minus two. The test says that the number 2ⁿ - 1 is prime if it divides the (n-2)th term in the sequence.
While the Lucas-Lehmer test looks easy enough to check, the computational bottleneck in applying it comes from squaring numbers. Multiplication of integers is something every school-aged kid can do, but for large numbers, it poses problems, even for computers. One way around this is to use Fast Fourier Transforms (FFT), algorithms that speed up computations.
Anyone can get involved with GIMPS — as long as you have a decent computer with an internet connection. Free software to search for Mersenne primes can be found on the GIMPS website.
While the largest known prime is stunningly massive, there are infinitely many more primes beyond it waiting to be discovered. Like Ellie Arroway did in Contact, we only have to look for them.
Anthony Bonato, Professor of Mathematics, Ryerson University
This article was originally published on The Conversation. Read the original article.
VIDEO: HERE'S WHAT THE INTERSTELLAR EXPLORER IS LEARNING:
