# Proving the primality of these large numbers?

In 2007, Vautier claimed that the largest known consecutive pair of prime numbers (at the time) was $2003663613\cdot2^{195000}-1$ and $2003663613\cdot2^{195000}+1$.

I was wondering how Vautier found these two extremely large numbers to be prime numbers and if there was any way I could determine if a random and extremely large number were prime.

## 1 Answer

Proth's theorem allows very fast proofs for numbers of the form $k \times 2^n+1$ ($k$ odd, $k < 2^n$).

Lucas-Lehmer-Riesel allows fast proof for numbers of the form $k \times 2^n-1$ ($k < 2^n$).

There were some press releases (e.g. these at MersenneForum) that briefly describe the process of how they were found. It was a distributed computing project looking for numbers of that form since we have fast ways to prove primality (mentioned above) for those numbers. LLR was used for the primality testing. NewPgen was used for sieving (to quickly remove numbers that have small factors, leaving a much smaller set of candidates), and over 1M numbers were tested before one was found.

As for "[...] if there was any way I could determine if a random and extremely large number were prime." Yes if you think "extremely large" is under 30k digits and you have quite a bit of time on a decent workstation. See Primo which is, by far, the fastest public software for large numbers. There are quite a few others which work up to ~5000 digits, and some others in research labs that aren't available for general use. Using a number of special form is going to allow much faster operation.

Also a note that quite good probable prime tests run very quickly as well -- testing compositeness for 100k digit numbers is not that hard, and the likelihood of a composite passing e.g. BPSW and a Frobenius test and some random-base M-R tests is extraordinarily small. Whether that is adequate vs. a proof depends on what your goal is. Among other things if you're discussing or publishing it, with a proof you don't have to constantly point out the asterisk of it being a probable prime and then spend an hour explaining primality testing and probabilities.