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 è la successione definita ricorsivamente come:

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

a partire da

L₁ = 4

Il test è stato sviluppato originariamente dal matematico Edouard 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²¹⁷⁰¹ − 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) \, \operatorname{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 \,\operatorname{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

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$

Moliplicando 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} = \left ( R \, M_p u^{2^{p-2}} -1 \right )^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 $\left ( a+b\sqrt 3 \right )\, \operatorname{mod} \, d$ che sono anche invertibili: G ha al più d² − 1 elementi. Se riscriviamo la 1 e la 2 modulo d, otteniamo $u^{2^{p-1}} \equiv -1 \, \operatorname{mod} \, d$ e $u^{2^p} \equiv 1 \, \operatorname{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 \leq 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

• (EN) Dimostrazione del test di Lucas-Lehmer

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica