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}}$.

Enunciato

Sia p un numero primo. Il corrispondente numero di Mersenne ${\displaystyle M_{p}=2^{p}-1}$ è primo se e solo se:

${\displaystyle L_{p-1}\equiv 0\,\operatorname {mod} \,M_{p}}$

Osservazione

Non è restrittivo considerare i numeri di Mersenne ${\displaystyle M_{p}}$ con ${\displaystyle p}$ primo anziché ${\displaystyle M_{n}}$ con ${\displaystyle n}$ numero naturale. Si dimostra infatti che se ${\displaystyle n}$ è composto, allora anche ${\displaystyle M_{n}}$ lo è.

Dimostrazione

Per la sufficienza: siano ${\displaystyle u=2+{\sqrt {3}}}$ e ${\displaystyle v=2-{\sqrt {3}}}$. È facile allora mostrare per induzione che

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

Poiché ${\displaystyle M_{p}}$ divide ${\displaystyle L_{p-1}}$, esiste un intero ${\displaystyle R}$ tale che

${\displaystyle L_{p-1}=R\,M_{p}}$

ossia

${\displaystyle u^{2^{p-2}}+v^{2^{p-2}}=R\,M_{p}}$

Moltiplicando per ${\displaystyle u^{2^{p-2}}}$, ottengo

${\displaystyle 1)\,\,\,\,\,u^{2^{p-1}}=R\,M_{p}u^{2^{p-2}}-1}$

Elevando al quadrato

${\displaystyle 2)\,\,\,\,\,u^{2^{p}}=\left(R\,M_{p}u^{2^{p-2}}-1\right)^{2}}$

Procediamo per assurdo. Supponiamo che ${\displaystyle M_{p}}$ sia composto e prendiamo un suo divisore d minore della sua radice quadrata. Sia G il gruppo dei numeri nella forma ${\displaystyle \left(a+b{\sqrt {3}}\right)\,\operatorname {mod} \,d}$ che sono anche invertibili: G ha al più ${\displaystyle d^{2}-1}$ elementi. Se riscriviamo la 1 e la 2 modulo d, otteniamo ${\displaystyle u^{2^{p-1}}\equiv -1\,\operatorname {mod} \,d}$ e ${\displaystyle u^{2^{p}}\equiv 1\,\operatorname {mod} \,d}$ rispettivamente. Quindi u è un elemento di G di periodo ${\displaystyle 2^{p}}$. Dato che il periodo di un elemento può al massimo essere pari al numero degli elementi del gruppo, abbiamo la seguente disuguaglianza

${\displaystyle 2^{p}\leq d^{2}-1<M_{p}=2^{p}-1}$

Dato che abbiamo una contraddizione, ${\displaystyle M_{p}}$ non ha divisori, e dunque è primo.

Voci correlate

• Test di Lucas-Lehmer-Riesel
• Algoritmo AKS
• Fattorizzazione
• Resto di Lucas-Lehmer
• Test di primalità
• Test di Miller - Rabin
• Test di Fermat

Collegamenti esterni

• (EN) Dimostrazione del test di Lucas-Lehmer (PDF), su 140.122.140.53. URL consultato l'8 agosto 2005 (archiviato dall'url originale il 16 giugno 2006).