Test di Lucas-Lehmer

Il test di Lucas-Lehmer è una verifica della primalità dei primi di Mersenne. In sintesi, per ${\displaystyle p}$ numero primo, detto ${\displaystyle M_{p}=2^{p}-1}$ il ${\displaystyle p}$-esimo numero di Mersenne, esso è primo se e solo se divide ${\displaystyle L_{p-1}}$, dove ${\displaystyle L_{n}}$ è l'n-esimo termine della successione definita ricorsivamente come:

${\displaystyle L_{n+1}=L_{n}^{2}-2}$

a partire da

${\displaystyle L_{1}=4}$

Il test è stato sviluppato originariamente dal matematico Édouard Lucas nel 1870 e semplificato da Derrick Norman Lehmer nel 1930. Il test è talmente rapido e facile da programmare, che nel 1978 due studenti delle superiori dimostrarono che il numero di Mersenne ${\displaystyle 2^{21701}-1}$ è primo, battendo il precedente record del più grande numero primo allora conosciuto.

È possibile anche un'ottimizzazione nel tempo di calcolo, per poter trattare numeri maggiori, dato che ${\displaystyle L_{n}}$ cresce molto velocemente, all'aumentare di ${\displaystyle n}$, per diventare presto intrattabile. Si può sostituire, alla successione precedente, quella specifica per il numero da verificare ${\displaystyle M_{n}}$, ricavata come segue:

${\displaystyle L_{n+1}\equiv (L_{n}^{2}-2)\,\operatorname {mod} \,M_{p}}$

dove mod è il modulo, ossia il resto della divisione per ${\displaystyle M_{p}}$. Questa successione ha però lo svantaggio di essere utile solo per i numeri di Mersenne minori o uguali a ${\displaystyle M_{p}}$.