My understanding is that most (all?) newly-discovered large prime numbers are found via computer programs. I tried reading upon the methodology to find those numbers but I got lost in the mathematical formulas. My guess is it’s not as simple as “find an odd number then start dividing it by all numbers that are approximately 50% of that number or less, and send an alert when you run the whole series and always get remainders.” I mean…that would work but it seems like the slowest and least efficient way to find primes. Is here some way of explaining this that doesn’t rely on me understanding a formula?
In: Mathematics
The largest primes are what are called *Mersenne primes*. *Mersenne numbers* are in the form of 2^(n) – 1, and are often prime when n is prime. 3, 7, 31, 127, and 8191 are all Mersenne primes, 2^(11) – 1 = 2047 = 23 * 89 is the first Mersenne number that is not a prime for a prime n.
To tell if an arbitrary number is prime, you have to essentially check all the primes up to its square root and see if any are factors. With a Mersenne number, the factors have to have specific mathematical properties that allow us to greatly reduce the factors we must check. There are other kinds of large primes, such as Proth primes (k * 2^(n) + 1) that have similar properties that make them easier to check. The largest primes have millions of digits, but for a general prime, 500 digits are beyond our current capabilities.
There is something called a *probable prime*. There are tests that can tell if a number is probably prime, only one in billions or trillions of numbers that pass these tests wind up being composite. These tests are much easier to apply than a 100% rigorous test, and are used to generate what are sometimes called industrial grade primes, numbers than can be treated as prime and used in cryptography.
Latest Answers