Test di Lucas-Lehmer

Il test di Lucas-Lehmer è un metodo efficace per verificare se un numero primo di Mersenne $ M_p = 2^p - 1 $ è effettivamente primo.

I numeri di Mersenne hanno la forma $ M_p = 2^p - 1 $, dove $ p $ è un numero primo.

La procedura del test è la seguente:

Inizializzazione
Definisco $ S_0 = 4 $, il primo termine della sequenza di Lucas-Lehmer.
Ricorsione
Calcolo la sequenza $ S_n $ usando la relazione ricorsiva: $$ S_{n+1} = S_n^2 - 2 \pmod{M_p} $$ dove $ M_p = 2^p - 1 $.
Iterazione
Eseguo la ricorsione per $ p-2 $ iterazioni, cioè da $ n = 1 $ a $ n = p-2 $.
Verifica finale
Se $ S_{p-2} \equiv 0 \pmod{M_p} $, allora $ M_p $ è un numero primo. Altrimenti, $ M_p $ non è primo.

Nota. Questo test è molto efficiente e la sua complessità è relativamente bassa rispetto ad altri metodi di test di primalità. Tuttavia può essere usato solo per verificare la primalità dei numeri di Mersenne. Non può essere utilizzato per verificare la primalità di numeri generici, nemmeno di altri numeri primi che non siano nella forma di Mersenne. Ad esempio, 11 è un numero primo ma non è un numero di Mersenne perché non posso scriverlo nella forma $ 2^p-1 $.

Un esempio pratico

Considero il numero di Mersenne 31

$$ M_5 = 2^5 - 1 = 31 $$

In questo caso $ p = 5 $.

Inizializzo la sequenza di Lucas-Lehmer con il primo valore ossia 4

$$ S_0 = 4 $$

La scelta del numero 4 come primo valore è la scelta standard, perché produce una sequenza valida per tutti i numeri di Mersenne.

Nota. Teoricamente, si possono scegliere altri valori iniziali $ S_0 $ ma non tutti i valori funzioneranno correttamente. Alcuni potrebbero generare sequenze che non permettono di determinare la primalità di $ M_p $. .

Calcolo la sequenza svolgendo $ p - 2 = 5 -2 = 3 $ iterazioni.

$$ S_1 = (4^2 - 2) \mod 31 = 14 $$

$$ S_2 = (14^2 - 2) \mod 31 = 8 $$

$$ S_3 = (8^2 - 2) \mod 31 = 0 $$

Poiché $ S_3 \equiv 0 \mod 31 $, il numero $ M_5 = 31 $ è primo.

Esempio 2

Considero il numero di Mersenne 2047

$$ M_{11} = 2^{11} - 1 = 2047 $$

In questo caso $ p =11 $.

Inizializzo la sequenza di Lucas-Lehmer con il primo valore ossia 4

$$ S_0 = 4 $$

Calcolo la sequenza svolgendo $ p - 2 = 11 -2 = 9 $ iterazioni.

$$ S_1 = (4^2 - 2) \mod 2047 = 14 $$

$$ S_2 = (14^2 - 2) \mod 2047 = 194 $$

$$ S_3 = (194^2 - 2) \mod 2047 = 788 $$

$$ S_4 = (788^2 - 2) \mod 2047 = 701 $$

$$ S_5 = (701^2 - 2) \mod 2047 = 119 $$

$$ S_6 = (119^2 - 2) \mod 2047 = 1877 $$

$$ S_7 = (1877^2 - 2) \mod 2047 = 240 $$

$$ S_8 = (240^2 - 2) \mod 2047 = 282 $$

$$ S_9 = (282^2 - 2) \mod 2047 = 1736 $$

Alla fine delle $ p - 2 = 9 $ iterazioni, il valore $ S_9 \neq 0 \mod 2047 $. Questo indica che $ M_{11} = 2047 $ non è primo.

In effetti, il numero 2047 è un numero composto $ 2047 = 23 \cdot 89 $.

E così via.