In matematica, il test di Lucas-Lehmer è un test di primalità specializzato per i numeri di Mersenne. L'algoritmo è stato originariamente sviluppato nel 1878 da Édouard Lucas e formalizzato nel 1930 da Derrick Norman Lehmer.
L'algoritmo Consideriamo il -esimo numero di Mersenne, . Possiamo assumere che sia primo, e quindi considerare con primo; se fosse composto, ossia per certi fattori e , allora è composto:
Il test esso è primo se e solo se divide , dove è l'-esimo termine della successione definita ricorsivamente come:
La successione di Lucas-Lehmer , nota in letteratura anche come , cresce molto velocemente all'aumentare di . I suoi primi termini sono
Nel test viene sostituita dalla "successione dei residui di Lucas-Lehmer", definita come
sfruttando l'aritmetica modulo . La prima successione consente di testare ogni numero di Mersenne, mentre questa è specifica per i numeri di Mersenne minori o uguali di .
Il codice Python dell'algoritmo diventa:# Verifica se Mp = 2^p − 1 è primo, p > 2 def LucasLehmer(p): s = 4 M = (2 ** p) - 1
for _ in range(p - 2): s = (s * s - 2) % M
return (s == 0)
Dimostrazione di correttezza
Sia un numero primo. Il corrispondente numero di Mersenne è primo se e solo se
Sufficienza Per la sufficienza: siano e . È facile allora mostrare per induzione che
Poiché divide , esiste un intero tale che
ossia
Moltiplicando per , si ottiene
Elevando al quadrato
Procediamo per assurdo. Supponiamo che sia composto e prendiamo un suo divisore minore della sua radice quadrata. Sia il gruppo dei numeri nella forma che sono anche invertibili: ha al più elementi. Se riscriviamo la 1 e la 2 modulo , otteniamo e rispettivamente. Quindi è un elemento di di periodo . Dato che il periodo di un elemento può al massimo essere uguale al numero degli elementi del gruppo, abbiamo la seguente disuguaglianza:
Dato che abbiamo una contraddizione, non ha divisori, e dunque è primo.
Applicazioni Nel 1978 Landon Curt Noll e Laura Nickel, due studenti delle superiori, utilizzarono il supercomputer CDC Cyber 174 per dimostrare che il numero di Mersenne è primo. Questo superò il precedente record del più grande numero primo conosciuto.
Fino al 2021, Lucas-Lehmer è stato il test di primalità utilizzato dal progetto Great Internet Mersenne Prime Search (GIMPS) per la ricerca di primi di Mersenne molto grandi. Dal 2021 viene usato solo per verificare la correttezza dei risultati suggeriti da una variante del test di Fermat, più veloce e di facile verifica.
Note
Voci correlate Test di Lucas-Lehmer-Riesel Algoritmo AKS Fattorizzazione Test di primalità Test di Miller - Rabin Test di Fermat
Collegamenti esterni
Categoria:Test di primalità