Largest Known Prime Number Discovered: Why It Matters
SCIENCE, 15 Jan 2018
Anthony Bonato – The Conversation
9 Jan 2018 – 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.
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.
Marin Mersenne. H Loeffel, Blaise Pascal, Basel: Birkhäuser 1987, CC BY-NC
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.
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!
Bitcoin and other crypto-currencies use security that depends on prime numbers. (Shutterstock)
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
Republish The Conversation articles for free, online or in print, under Creative Commons license.
Go to Original – theconversation.com
DISCLAIMER: The statements, views and opinions expressed in pieces republished here are solely those of the authors and do not necessarily represent those of TMS. In accordance with title 17 U.S.C. section 107, this material is distributed without profit to those who have expressed a prior interest in receiving the included information for research and educational purposes. TMS has no affiliation whatsoever with the originator of this article nor is TMS endorsed or sponsored by the originator. “GO TO ORIGINAL” links are provided as a convenience to our readers and allow for verification of authenticity. However, as originating pages are often updated by their originating host sites, the versions posted may not match the versions our readers view when clicking the “GO TO ORIGINAL” links. This site contains copyrighted material the use of which has not always been specifically authorized by the copyright owner. We are making such material available in our efforts to advance understanding of environmental, political, human rights, economic, democracy, scientific, and social justice issues, etc. We believe this constitutes a ‘fair use’ of any such copyrighted material as provided for in section 107 of the US Copyright Law. In accordance with Title 17 U.S.C. Section 107, the material on this site is distributed without profit to those who have expressed a prior interest in receiving the included information for research and educational purposes. For more information go to: http://www.law.cornell.edu/uscode/17/107.shtml. If you wish to use copyrighted material from this site for purposes of your own that go beyond ‘fair use’, you must obtain permission from the copyright owner.