Test di Lucas-Lehmer-Riesel

Da Wikipedia, l'enciclopedia libera.

In matematica, il test di Lucas-Lehmer-Riesel è un test di primalità per i numeri della forma N = k2n − 1, con 2n > 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 = k2n + 1.

L'algoritmo[modifica | modifica wikitesto]

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

Definiamo la successione {ui}, ponendo:

u_i = u_{i-1}^2-2, \,

per ogni i > 0.

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

Trovare il valore di partenza[modifica | modifica wikitesto]

  • Se k = 1 e n è primo, allora ci troviamo di fronte ad un numero di Mersenne e possiamo prendere u0 = 4.
  • Se n \equiv 3 \pmod{4}, allora possiamo prendere u_0 = 3.
  • Se k = 3, e n \equiv 0 \pmod{4} oppure n \equiv 3 \pmod{4}, allora u_0 = 5778.
  • Se k \equiv 1 \pmod{6} oppure k \equiv 5 \pmod{6}, e N non è divisibile per 3, allora possiamo prendere 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 u_0.

Software LLR[modifica | modifica wikitesto]

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

Collegamenti esterni[modifica | modifica wikitesto]

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