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

Versione delle 23:34, 19 gen 2011

Versione attuale delle 22:16, 4 mag 2019

(7 versioni intermedie di 6 utenti non mostrate)

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−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.

* Se <math>n \equiv 3 \pmod{4}</math>, allora possiamo prendere <math>u_0 = 3</math>.

* Se <math>k = 3</math>, e <math>n \equiv 0 \pmod{4}</math> oppure <math>n \equiv 3 \pmod{4}</math>, allora <math>u_0 = 5778</math>.

* Se <math>k \equiv 1 \pmod{6}</math> oppure <math>k \equiv 5 \pmod{6}</math>, e ''N'' non è divisibile per 3, allora possiamo prendere <math>u_0 = (2+\sqrt{3})^k+(2-\sqrt{3})^k</math>.

* Altrimenti, ci troviamo nel caso in cui ''k'' è un multiplo di 3, ed è più difficile selezionare il valore giusto di <math>u_0</math>.

== 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 ==

* [[nl:Test di Lucas-Lehmer-Rieseltest]]

== Collegamenti esterni ==

* {{citeCita journalpubblicazione |lastcognome=Riesel |firstnome=Hans |authorlink= |coauthors= |yearanno=1969 |month= |titletitolo=Lucasian Criteria for the Primality of ''N'' = ''h''·2^''n''&nbsp;&minus;−&nbsp;1 |journalrivista=Mathematics of Computation |volume=23 |issuenumero=108 |pagespagine=869–875 |doi=10.2307/2004975 |url= httphttps://jstor.org/stable/2004975|accessdate= |quote= |publishereditore=American Mathematical Society }}

* [{{cita web|http://pagesperso-orange.fr/jean.penne/index2.html |Download Jean Penné's LLR]}}

{{portale|Matematica}}

[[Categoria:Test di primalità]]

[[en:Lucas–Lehmer–Riesel test]]

[[nl:Lucas-Lehmer-Rieseltest]]