Test di Lucas-Lehmer-Riesel

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

L'algoritmo

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

Definiamo una sequenza {u_i} per ogni i > 0 da:

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

Allora 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}}}$  o ${\displaystyle n\equiv 3{\pmod {4}}}$ , allora ${\displaystyle u_{0}=5778}$ .
• Se ${\displaystyle k\equiv 1{\pmod {6}}}$  o ${\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 <math>u_0</math.