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$ è la 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 Henry Lehmer nel 1930. Il test è talmente rapido e facile da programmare, che nel 1978 due studenti delle superiori dimostrarono che il numero di Mersenne $221701 - 1$ è primo, battendo il precedente record del più alto 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$ .

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

[modifica] 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 è.

[modifica] 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 almeno $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