Test di Lucas-Lehmer-Riesel: differenze tra le versioni

Versione delle 23:39, 19 gen 2011

Versione delle 23:48, 19 gen 2011

Riga 1:

In [[matematica]], il '''test di Lucas-Lehmer-Riesel''' è un [[test di primalità]] per i numeri della forma ''N'' = ''k''2^''n'' − 1, con 2^''n'' > ''k''. Il test è stato elaborato da [[Hans Riesel]] e si basa sul [[Test di Lucas-Lehmer|test di primalità di Lucas-Lehmer]]. CostituisceÈ il più veloce l'[[algoritmo]] deterministico più velocenoto per iverificare la primalità dei numeri della suddetta forma. Similmente, il '''test di Brillhart–Lehmer–SelfridgeBrillhart-Lehmer-Selfridge''' è il più veloce per i numeri della forma ''N'' = ''k''2^''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 unala sequenza[[successione (matematica)|successione]] {''u''_''i''}, per ogni ''i'' > 0 daponendo:

: <math>u_i = u_{i-1}^2-2., \, </math>

per ogni ''i''&nbsp;>&nbsp;0.

Allora ''N'' è primo [[se e solo se]] esso divide &nbsp;''u''_{''n''&minus;2}.

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 &nbsp;''u''_{''n''&minus;2}.

== Trovare il valore di partenza ==

=== Trovare il valore di partenza ===

* Se ''k'' = 1 e ''n'' è primo, allora ci troviamo di fronte ad un [[Numero primo di Mersenne|numero di Mersenne]] e possiamo prendere ''u''₀&nbsp;=&nbsp;4.

Riga 22 ⟶ 24:

== Software LLR ==

L'LLR è un programma in grado di effettuare dei test LLRdi Lucas-Lehmer-Riesel. Il programma è stato elaborato da Jean Penné. Vincent Penné ha modificato il programma, rendendolo capace di ottenereeffettuare 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 ==