Table of Contents (click to expand)
There are a few different algorithms that can be used to find prime numbers, but the most common ones are the Mersenne Prime Method and the Fermat Prime Number Method.
Beautiful anomalies occur in every subject, but if there is one area of beauty that most mathematicians would agree upon, it is the prime number.
To ordinary folk, these might look like a random set of numbers in the vast array of numbers that we can comprehend. However, these numbers hold a unique pedestal in mathematics, especially in the field of number theory. Great minds have poured countless investigative hours into this issue, including great minds like Paul Erdős, G.H. Hardy and Srinivasa Ramanujan, to name but a few. Now, before we dive into the different algorithms to find prime numbers, let’s first establish a preliminary understanding of prime numbers.
Recommended Video for you:
What Are Prime Numbers?
The most technical definition of a prime number is that it is a natural number greater than 1 and can only be obtained by multiplying 1 and itself. If natural numbers were to be understood more intuitively, we could state that these are numbers we use to count.
To understand this more precisely, let’s pick two numbers—5 and 6. Now, 5 is a number that can only be obtained by the multiplication of 1 and 5 (the number itself). However, when we take the number 6, we notice that it can be obtained in another way, apart from multiplying 1 and 6 (the number itself). It can also be obtained by multiplying the number 2 and 3 which means it is not a prime number. A number that isn’t a prime number is known as a composite number.
Mersenne Prime Method
The Mersenne Prime Method is a special method of finding a particular kind of prime, known as the Mersenne Primes. The name for this method is derived from the French monk, Marin Mersenne, who first defined it. Mersenne primes are those that are reducible to the form 2n-1, where n is a prime number. The first few numbers in this method are 2, 3, 5, 7, 13, 17, 19, 31, 61, and 89. For a long time, the Mersenne prime method was a drudgery, as it was highly computation-intensive once you go on to higher prime numbers.
However, with the advent of computers, they could now perform these number-crunching calculations, which had formerly been done by humans in the most painstaking and time-consuming fashion. We’ve definitely reached higher Mersenne Primes and primes on an overall level. The search for primes is just as fervent as other numerical searches done by computers. Another numerical search, similar to the drive for primes, lies in furthering the decimal places in certain irrational numbers, such as pi (the ratio of the circumference to the diameter). However, the continual search for the next largest prime is substantially more difficult than the search for the next digit of pi.
Even the largest computers (supercomputers) take a substantial amount of time to verify if a new number (which is usually mind-bogglingly huge) is a prime in itself, and it takes even more time to check if the number is a Mersenne Prime. For this reason, Mersenne numbers have been of great interest in the field of Cybersecurity and Cryptography, especially pertaining to encryption.
In August 2008, Edson Smith, a system administrator at UCLA, found the most significant prime number known to that point. Smith had installed software for the Great Internet Mersenne Prime Search (Gimps), a volunteer-based distributed computing project. The number was a Mersenne Prime that is 12,978,189 digits long. To give some perspective as to how large that is, it would take nearly two-and-a-half months to write it out and, if printed, would stretch for 30 miles!
Fermat’s Prime Number Method
A Fermat number, just like a Mersenne number, is a specific kind of prime number. The name stems from the 17th century mathematician and lawyer, Pierre De Fermat. A Fermat number is similar to the Mersenne Prime… with one little tweak. Let’s take a Fermat number Fm, where we can define Fm as 2m+1. Here, m is again 2 raised to the power n or 2n.
Fermat was of the firm belief that all numbers of the above form were prime numbers. To further this, he said that it would produce prime numbers for all integer values of m. This went on to to be true. What makes these number unique and beautiful, yet highly tricky, is that the primes become extremely big very fast, even within the limit of the first four iterations. To prove this, let’s take n as the following values, n=0, 1, 2, 3 and 4.
When n = 0, m = 20 = 1; therefore F0 = 2 1 + 1 = 2 + 1 = 3, which is prime. When n = 1, m = 21 = 2; therefore F1= 22 + 1 = 4 + 1 = 5, which is prime. When n = 2, m = 22 = 4; therefore F2 = 24 + 1 = 16 + 1 = 17, which is prime. When n = 3, m = 23 = 8; therefore F3 = 28 + 1 = 256 + 1 = 257, which is prime. When n = 4, m = 24 = 16; therefore F4 = 216 + 1 = 65536 + 1 = 65537, which is prime. Now, as you can observe, just by the time we reach F5, the value reaches 4,294,967,297.
To date, we have only reached F11, even with all the best computer and parallel computing and a great deal of precision. In the end, though, we can say that the search for prime numbers will always go to infinity—and beyond!
