# How do you prove a number is prime?

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).

• This particular number is a Mersenne prime, primality of which can be proved using the Lucas-Lehmer Test. – Rebecca J. Stones Sep 3 '13 at 20:26
• @Rebecca -- Thanks for the link. The method has a step in it where it says $M_p$ is prime iff $s_{p-2}=0 mod M_p$ where $M_p$ is the potential prime of form $2^p-1$. How would you calculate the mod against such a large number? – Mufasa Sep 3 '13 at 20:32
• Using arbitrary precision arithmetic. I know also that this process is sped up using something called a discrete weighted transform, but I don't know much about this. – Rebecca J. Stones Sep 3 '13 at 20:34
• Repeated squaring and mod reduction, or similar optimized methods, using an infinite precision math library. – Amzoti Sep 3 '13 at 20:34
• @Mufasa Yes, you do need to perform some 57 million bit calculations - but at least you don't have to do trial division with $\approx \sqrt {M_p}$ potential divisors ... – Hagen von Eitzen Sep 3 '13 at 20:36

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).

• Thanks for all this - this should keep me busy for the next few weeks. :) – Mufasa Sep 3 '13 at 21:54
• $2^{19}$ should be $2^{19}-1$ or $M_{19}$ (twice). And the RHS in the recursion for $U_i$ should contain $U_{i-1}$ instead of $U_i$, I suppose. – ccorn Aug 12 '18 at 13:24
• ... and the $\pmod{n}$ in the theorem with the $U_i$ should likely be a $\pmod{M_n}$. – ccorn Aug 12 '18 at 15:07
• Reading Lehmer's paper (p. 445), your proposition around the $U_i$ seems to be based on a misunderstanding. The $U_i$ are possible starting terms for the recursion $S_i=S_{i-1}^2-2$. – ccorn Aug 12 '18 at 15:53