Test di Lucas-Lehmer

Da Wikipedia, l'enciclopedia libera.

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 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^{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) \, \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[modifica | modifica sorgente]

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[modifica | modifica sorgente]

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[modifica | modifica sorgente]

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^2-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[modifica | modifica sorgente]

Collegamenti esterni[modifica | modifica sorgente]

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