Lucas-Lehmer primality test

Theorem: Let $p>2$ be a prime, and let $M_p$ be a Mersenne number, then $M_p$ is prime iff $M_p$ divides $s_{p-1}$ where the numbers ${(s_n)}_{n\ge 1}$ are given by the following recurrence relation: $s_1=4$, and

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

for $n\ge 1$.