Test di Lucas-Lehmer-Riesel: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m migrazione automatica di 2 collegamenti interwiki a Wikidata, d:q3459114 |
m Bot: passaggio degli url da HTTP a HTTPS |
||
| (3 versioni intermedie di 3 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<sup>''n''</sup>
== L'algoritmo ==
Riga 10:
per ogni ''i'' > 0.
Allora, per un valore di partenza ''u''<sub>0</sub> scelto opportunamente (si veda la sezione seguente), si ha che ''N'' è primo [[se e solo se]] esso divide ''u''<sub>''n''
=== 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''<sub>0</sub> = 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>.
Riga 30 ⟶ 26:
== Collegamenti esterni ==
* {{Cita pubblicazione |cognome=Riesel |nome=Hans
*
{{portale|Matematica}}
| |||