How to verify large Mersenne Primes

Question

As of December 2017, the largest known prime number was the Mersenne prime $2^{77232917} – 1$.

For such a large Mersenne prime, what are the techniques available for one to verify that it is in fact a prime? Is it simply a matter of brute force checking, or are there other more elegant techniques available?

Answer 1

Lucas–Lehmer primality test:

Let $p$ be an odd prime.

Define a sequence $\{s_i\}_{i \ge 0}$ by:

1. $s_0 = 4$
2. $s_{n+1} = s_n^2 - 2$

Then $2^p - 1$ is prime iff $s_{p-2} \equiv 0 \pmod {2^p - 1}$.

(For your case, $p = 77232917$.)