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
You are correct that (as far as we know) the only way to know for sure that a number is prime is to do something like the whole square root of the number thing.
But there are some tricks around it.
For starters, there’s some algorithms like the [Miller-Rabin test](https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test).
You run it many times on a number.
Each time your run it, it either confirms that the number is not prime, or that it’s maybe a prime.
So if you run it many many times, you can be pretty sure that a number is a prime number, but don’t have to crunch every single number to the square root.
A surprising amount of real world encryption works on numbers we only suspect as prime, because of this algorithm.
There’s also [prime-counting functions](https://en.wikipedia.org/wiki/Prime-counting_function) which tell you how many prime numbers there are less than a particular number, but just not what the prime numbers are.
So we can focus our efforts where we know prime numbers are going to be.
~~Also if we ever get every single prime number in order, we can make a brand new prime number, by multiplying them all up and adding 1.
There are likely to be many primes in between the last one we found and the new one we made.~~
There’s no formula that will just take you straight to a prime number, it has to be found, kinda like what you’re saying. There are formulas that can predict where a prime might be, or give you a smaller amount of numbers to check. But those just help find a prime, not actually give it to you.
I’m not there person to be talking about this because I probably know less than you. I do watch a lot of YouTube videos on math related subjects though. Both previous comments described methods that are used to find primes and another one that I can think of is the simplest of all. A lot of the multi-million figure primes that we find tend to be (2^x)-1. On a side note, computer systems run on 32 or 64 bit systems which is just that formula with x being 32 or 64.
There are some formulas that can be used to quickly determine if a number is/is not a prime.
Most of the larger primes they are finding are of the form 2^n – 1 (Mersenne primes). They can also use some form of Fermat’s Little Theorem (if p is prime, a^p – a is an integer multiple of p).
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