How do you prove a number is prime?

Question

I am a software engineer but try to keep up with maths as I really enjoyed the subject at school. I just saw a great TED talk: Why I fell in love with monster prime numbers

The talk states that the current largest known prime is $2^{57885161}-1$

This got me thinking - how does one actually prove whether a number this large is prime or not?

Is it just done by brute force via a computer algorithm or are there any well known mathematical techniques for doing so?

I would be really grateful for any pointers as I am eager to learn about these techniques (if they exist).

Answer 1

This particular number is a Mersenne prime, primality of which can be proved using the Lucas-Lehmer Test. Proving these numbers prime must be performed on a computer, and it can take months to perform the relevant computations. GIMPS hosts a distributed computing project to search for Mersenne primes.

Multiplication modulo $M_p:=2^p-1$ can be performed using arbitrary precision arithmetic. Highly optimized libraries by George Woltman (and others) are used to perform the actual computation; they make use of discrete weighted transforms to speed up the computation.

R. Crandall and B. Fagin, Discrete weighted transforms and large-integer arithmetic, Math. Comp. 62 (1994) 305-324. (pdf)

---

In fact, there are several tests similar to the Lucas Lehmer Test. The Lucas Lehmer Test is favoured because it's necessary and sufficient (i.e., a pass implies primality, and a fail implies compositeness).

Lucas Lehmer Test: $M_n:=2^n-1$ is prime if and only if $S_{n-2} \equiv 0 \pmod {M_n}$, where $S_0=4$ and $S_i=S_{i-1}^2-2$ for $i \geq 1$.

To verify that $2^{19}$ is prime, we compute $S_i \pmod {M_{19}}$ for $0 \leq i \leq 17$, which is $$4, 14, 194, 37634, 218767, 510066, 386344, 323156, 218526, 504140, 103469, 417706, 307417, 382989, 275842, 85226, 523263, 0.$$

Theorem: If $n \equiv -1 \pmod 4$, then $M_n$ is prime if $T_{n-2} \equiv 0 \pmod {M_n}$, where $T_0=3$ and $T_i=T_{i-1}^2-2$ for $i \geq 1$.

To verify that $2^{19}$ is prime, we compute $T_i \pmod {M_{19}}$ for $0 \leq i \leq 17$, which is $$3, 7, 47, 2207, 152264, 354554, 244924, 420095, 86240, 326503, 409010, 208425, 132664, 470878, 399999, 439061, 523263, 0.$$

Theorem: Let $U_0=4$, $U_1=52$ and $U_i=14U_i-U_{i-2}$ for $i \geq 2$. If $U_{n-2} \equiv \pm 2^{(n+1)/2} \pmod n$ then $M_n$ is prime.

To verify that $2^{19}$ is prime, we compute $T_i \pmod {19}$ for $0 \leq i \leq 17$, which is $$4, 14, 2, 14, 4, 4, 14, 2, 14, 4, 4, 14, 2, 14, 4, 4, 14, 2.$$ We now check that $2^{(n+1)/2} \equiv -2 \pmod {19}$.

There are several other such theorems in the following paper (not all for Mersenne primes):

D. H. Lehmer, An Extended Theory of Lucas' Functions, Ann. Math. (2), 31 (1930), 419-448. (link)

---

Similar efficient algorithms exist for other numbers, such as $$k \times 2^n+1$$ with $2^n<k$, which are called Proth numbers (the Brillhart-Lehmer-Selfridge test; see also Proth's Theorem), and $$k \times 2^n-1$$ with $2^n<k$ (the Lucas–Lehmer–Riesel test).