Test di Lucas-Lehmer-Riesel

In matematica, il test di Lucas-Lehmer-Riesel è un test di primalità per i numeri della forma N = k2^n − 1, con 2^n > k. Il test è stato elaborato da Hans Riesel e si basa sul test di primalità di Lucas-Lehmer. È il più veloce algoritmo deterministico noto per verificare la primalità dei numeri della suddetta forma. Similmente, il test di Brillhart-Lehmer-Selfridge è il più veloce per i numeri della forma N = k2^n + 1.

L'algoritmo

L'algoritmo è molto simile al test di Lucas-Lehmer, ma con un punto iniziale variabile dipendente dal valore di k.

Definiamo la successione {u_i}, ponendo:

${\displaystyle u_{i}=u_{i-1}^{2}-2,\,}$

per ogni i > 0.

Allora, per un valore di partenza u₀ scelto opportunamente (si veda la sezione seguente), si ha che N è primo se e solo se esso divide  u_n−2.

Trovare il valore di partenza

• Se k = 1 e n è primo, allora ci troviamo di fronte ad un numero di Mersenne e possiamo prendere u₀ = 4.
• Se ${\displaystyle n\equiv 3{\pmod {4}}}$, allora possiamo prendere ${\displaystyle u_{0}=3}$.
• Se ${\displaystyle k=3}$, e ${\displaystyle n\equiv 0{\pmod {4}}}$ oppure ${\displaystyle n\equiv 3{\pmod {4}}}$, allora ${\displaystyle u_{0}=5778}$.
• Se ${\displaystyle k\equiv 1{\pmod {6}}}$ oppure ${\displaystyle k\equiv 5{\pmod {6}}}$, e N non è divisibile per 3, allora possiamo prendere ${\displaystyle u_{0}=(2+{\sqrt {3}})^{k}+(2-{\sqrt {3}})^{k}}$.
• Altrimenti, ci troviamo nel caso in cui k è un multiplo di 3, ed è più difficile selezionare il valore giusto di ${\displaystyle u_{0}}$.

Software LLR

L'LLR è un programma in grado di effettuare dei test di Lucas-Lehmer-Riesel. Il programma è stato elaborato da Jean Penné. Vincent Penné ha modificato il programma, rendendolo capace di effettuare test via Internet. Il software è utilizzato sia dai ricercatori di numeri primi sia da alcuni progetti sul calcolo distribuito, inclusi Riesel Sieve e PrimeGrid.

Voci correlate

• Test di Lucas-Lehmer

Collegamenti esterni

• Hans Riesel, Lucasian Criteria for the Primality of N = h·2^n − 1, in Mathematics of Computation, vol. 23, n. 108, American Mathematical Society, 1969, pp. 869–875, DOI:10.2307/2004975.
• Download Jean Penné's LLR, su pagesperso-orange.fr.