Xrfgtjtk

So I've found multiple ways of determining if a number is prime but I was wondering how they pick a number in the first place. For example the GIMPS project I assume is just trying different numbers to square 2 by but what about other methods? Or is it just a process of testing each and every unknown number?

GIMPS just considers Mersenne primes, so there is a fixed formula.

However if you are looking for a "biggish" prime, say 1024-bits well suited for cryptography, that is a prime $p$ with $2^{1024} < p < 2^{1025}$. Out of the $2^{1024}$ numbers in the range, approximately
$$frac{2^{1025}}{log 2^{1025}} - frac{2^{1024}}{log 2^{1024}}$$
are prime. So the fraction which are prime is
$$frac{2}{log 2^{1025}} - frac{1}{log 2^{1024}}=
frac{2}{1025log 2} - frac{1}{1024log 2} = 0.001406$$
Since you can test as many as you want, that's not such bad odds.

By the frivolous theorem of arithmetic, the large primes that have been found are quite small. Let's say $p$ is the largest known prime. Then between $p$ and $p^p$ there are roughly $$frac{p^p}{log p^p} - frac{p}{log p}$$ primes that are bigger than $p$, and of course $p^p$ still falls quite short of infinity. This is quite a large number (to us) when we plug in something like $p = 2^{74207281} - 1$, the largest known prime number right now according to the Prime Pages.

It's not surprising that this largest known prime is a Mersenne prime, a number of the form $2^n - 1$ (and $n$ is also prime). The other answerers have already mentioned the Lucas-Lehmer test. Just for fun try it on $2^{31} - 1$, you might find it to be quite faster than trial division up to $sqrt{2^{31} - 1} approx 46340$.

But it's still time-consuming. Take note of these remarks from Chris Caldwell regarding $2^{74207281} - 1$:

This prime was first detected by a machine on September 17, 2015, but was not notice[d] by a human until January 7th at 22:30 UTC--so this becomes the official discovery date.

The primality proof took 31 days of non-stop computing on a PC with an Intel I7-4790 CPU. To prove there were no errors in the prime discovery process, the new prime was independently verified using both different software and hardware. Andreas Hoglund and David Stanfill each verified the prime using the CUDALucas software running on NVidia Titan Black GPUs in 2.3 days. David Stanfill verified it using ClLucas on an AMD Fury X GPU in 3.5 days. Serge Batalov also verified it using Ernst Mayer's MLucas software on two Intel Xeon 18-core Amazon EC2 servers in 3.5 days.

The largest known non-Mersenne prime as of today is $10223 times 2^{31172165} + 1$. This prime is special because it pertains to the problem of Sierpinski numbers, which I'm not going to go into detail here.

So what projects like GIMPS and Seventeen or Bust do is look for primes that can be expressed in a certain compact way. But they are limited in how far they can go. For example, is $2^{2^{127} - 1} - 1$ prime? Some say there aren't enough resources in the universe to answer that question.

There was a related question a few months ago, something like what is the largest prime number $p$ such that the value of $pi(p)$ is known exactly? (e.g., $pi(7) = 4$, $pi(11) = 5$, etc.) Obviously $pi(2^{74207281} - 1)$ can at present only be estimated.

But, if we define $pi_M(n)$ to tell us how many Mersenne primes there are less than or equal to $n$, it turns out that $pi_M(2^{74207281} - 1)$ is also unknown. It's believed to be 49, but could just as easily be 50 or 51 (I suppose it could also be 52 or higher, but I'd wager money against that).

I suppose I could talk about this for hours. Perhaps the most useful thing I could tell you to do is to play around with Wolfram Alpha. Type NextPrime[ then some "random" 20-digit number, ], press Enter. You might get a prime number that is too small for practical applications in cryptography, but is too large and unlikely to come up in casual everyday conversation.

By using the power of distributed computing to test potential prime numbers of specific forms.

The most famous is of course the search for Mersenne primes, which are of the form $2^p - 1$, where $p$ is also prime. That right there helps to narrow the search. For example, we immediately know that $2^{91} - 1$ is not prime, because it's divisible by $2^7 - 1$ and $2^{13} - 1$.

But not all primes give primes as Mersenne exponents. For example, $2^{23} - 1 = 47 times 178481$. There are ways to detect a lot of primes like $23$, further narrowing down the search. According to the Great Internet Mersenne Prime Search (GIMPS), the slower computers in the network are assigned the task of ferreting out primes like $23$, so that the faster computers can concentrate on testing primes likelier to be Mersenne prime exponents.

Once in a while, however, large prime numbers are found almost by accident. For instance, if $a_0 = 20615674205555510$ and $a_1 = 3794765361567513$, the sequence defined by $a_n = a_{n - 2} + a_{n - 1}$ for $n > 1$ contains no primes. However, if you swap $a_0$ and $a_1$, then $a_{138} = 439351292910452432574786963588089477522344721$ is prime.

On November $9$, $2005$, Eric W. Weisstein announced that $a_{156075}$ is also prime. See Mathworld for more details. These are small numbers compared to the largest known Mersenne prime, and even smaller compared to prime numbers large beyond our comprehension.

One can generate prime numbers using Fermat's little theorem. This theorem states that if $p$ is prime and $aneq 0 bmod p$ then:

$$a^{p-1} = 1 bmod p$$

Suppose then that for some number $n$ and some $aneq 0 bmod n$ the above equation would hold when taking $p$ equal to $n$. Then that doesn't prove that $n$ is prime. To get to a rigorous primality test, more tests need to be done, see. e.g. here. But the reverse of Fermat's little theorem is true if $n$ is of the form $h p + 1$ or $h p^2 + 1$ and $h < p$ for some known prime $p$. So, this then allows you to generate ever larger primes using just Fermat's little theorem as the primality test.

Here is a simple example using my HP calculator that allows integer computation with a maximum of 12 digits. I'm then restricted to finding primes smaller than $10^6$ due to having to repeatedly compute the square modulo $n$ to compute large powers. If I start with $p = 13$, then $n_1 = 10times p + 1 = 131$ passes the Fermat test, therefore $n_1$ is prime. Then $n_2 = 50times n_1 + 1 = 6551$ passes the test, therefore $n_2$ is prime. Then I find that $n_3 = 122times n_2 + 1 = 799,223$ passes the test, so $n_3$ is prime. So, within minutes I could find this large prime using only my antique HP calculator.

Most recent record-breaking large primes have been Mersenne numbers, i.e. of the form $2^p-1$ (which can only be prime for prime $p$), because they have an especially easy test: https://en.wikipedia.org/wiki/Lucas-Lehmer_primality_test So we just keep trying successively larger $p$ in the tens of millions. Sometimes, this is used instead: https://en.wikipedia.org/wiki/Lucas-Lehmer-Riesel_test