Test di Lucas-Lehmer

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

$L_{n+1}=L_n^2-2$

a partire da

$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 $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 $L_n$ cresce molto velocemente, all'aumentare di $n$, per diventare presto intrattabile. Si può sostituire, alla successione precedente, quella specifica per il numero da verificare $M_n$, ricavata come segue:

$L_{n+1}\equiv (L_n^2-2)\mathrm{mod}{M}_p$

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

Enunciato

Sia p un numero primo. Il corrispondente numero di Mersenne $M_p=2^p-1$ è primo se e solo se:

$L_{p-1}\equiv 0\mathrm{mod}{M}_p$

Osservazione

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

Dimostrazione

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

$L_n=u^{2^{n-1}}+v^{2^{n-1}}$

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

$L_{p-1}=R{M}_p$

ossia

$u^{2^{p-2}}+v^{2^{p-2}}=R{M}_p$

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

$1)u^{2^{p-1}}=R{M}_p{u}^{2^{p-2}}-1$

Elevando al quadrato

$2)u^{2^p}={(R{M}_p{u}^{2^{p-2}}-1)}^2$

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

$2^p\le d^2-1<M_p=2^p-1$

Dato che abbiamo una contraddizione, $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

• Template:Cita web