title: Test di Lucas-Lehmer-Riesel
text: # 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:
  
      $u_{i}=u_{i-1}^{2}-2,\,$
  
  per ogni i > 0.
  
  Allora, per un valore di partenza $u_0$ 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_0$ = 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
  
  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.
  
  