Viquipèdia

Prova de Lucas-Lehmer per a nombres de Mersenne: diferència entre les revisions

Exploració interactiva de l'historial
← Edició anteriorEdició següent →
Contingut suprimit Contingut afegit
VisualWikitext
m r2.7.1) (Robot afegeix: ko:루카스–레머 소수판별법
m Robot: Reemplaçament automàtic de text (- + )
Línia 1:
:''Aquest article es refereix a la prova de Lucas–Lehmer que s'aplica només als nombres de Mersenne. Hi ha també una prova generalitzada de primalitat de Lucas–Lehmer; vegeu [[prova de Lucas–Lehmer]].''
 
En [[matemàtiques]], la '''prova de Lucas–Lehmer''' és una [[prova de primalitat]] per [[Nombre primer de Mersenne|nombres de Mersenne]]. La prova va ser desenvolupada inicialment per [[Edouard Lucas]] el [[1856]] [http://primes.utm.edu/notes/by_year.html][http://primes.utm.edu/curios/page.php?number_id=135], i posteriorment millorada per Lucas el [[1878]] i [[Derrick Henry Lehmer]] a la dècada del [[1930]].
 
==La prova==
Línia 7:
La prova de Lucas-Lehmer funciona tal com s'explica tot seguit. Sia ''M''<sub>''p''</sub>&nbsp;=&nbsp;2<sup>''p''</sup>−&nbsp;1 el nombre de Mersenne a provar amb ''p'' un [[Nombre primer]] senar (com que ''p'' és exponencialment més petit que ''M''<sub>''p''</sub>, es pot fer servir un algorisme senzill com a ara el de [[divisions successives]] per tal d'establir la seva primalitat). Es defineix una successió {''s''<sub>''i''</sub>} per a tot ''i'' ≥ 0 com
:<math>
s_i=
\begin{cases}
4 & \mbox{si }i=0;
\\
s_{i-1}^2-2 & \mbox{altrament.}
\end{cases}
</math>
Els primers termes d'aquesta successió són 4, 14, 194, 37634, ... {{OEIS|id=A003010}}.
Línia 21:
''// Determinar se M<sub>''p''</sub> = 2<sup>''p''</sup> − 1 és primer
'''Lucas-Lehmer'''(p)
'''var''' s ← 4
'''var''' M ← 2<sup>''p''</sup> − 1
'''repetir''' p − 2 cops:
s ← ((s &times; s) − 2) mod M
'''si''' s = 0 '''retorna''' PRIMER '''sinó''' '''retorna''' COMPOST
 
Al realitzar l'operació <code>mod M</code> a cada iteració, s'assegura que tots els resultats intermedis tenen com a màxim ''p'' bits (altrament el nombre de bits es doblaria a cada iteració). És exactament la mateixa estratègia que es fa servir en la [[exponenciació modular]].
Línia 40:
|916 mod 2<sup>5</sup>−1 || = || 1110010100<sub>2</sub> mod 2<sup>5</sup>−1
|-
| || = || 11100<sub>2</sub> + 10100<sub>2</sub> mod 2<sup>5</sup>−1
|-
| || = || 110000<sub>2</sub> mod 2<sup>5</sup>−1
|-
| || = || 1<sub>2</sub> + 10000<sub>2</sub> mod 2<sup>5</sup>−1
|-
| || = || 10001<sub>2</sub> mod 2<sup>5</sup>−1
|-
| || = || 10001<sub>2</sub>
|-
| || = || 17.
|}
 
Línia 85:
La demostració original que va donar Lehmer per aquest algorisme és complexa, per tant aquí se segueix un camí que aplica refinaments més actuals. Recordant la definició:
:<math>
s_i=
\begin{cases}
4 & \mbox{si }i=0;
\\
s_{i-1}^2-2 & \mbox{altrament.}
\end{cases}
</math>
Llavors el teorema és que ''M''<sub>''p''</sub> és primer [[si i només si]] <math>s_{p-2}\equiv0\pmod{M_p}.</math>
Línia 98:
:<math>s_0 = \omega^{2^0} + \bar{\omega}^{2^0} = (2 + \sqrt{3}) + (2 - \sqrt{3}) = 4.</math>
:<math>\begin{array}{lcl}s_n & = & s_{n-1}^2 - 2 \\
& = & \left(\omega^{2^{n-1}} + \bar{\omega}^{2^{n-1}}\right)^2 - 2 \\
& = & \omega^{2^n} + \bar{\omega}^{2^n} + 2(\omega\bar{\omega})^{2^{n-1}} - 2 \\
& = & \omega^{2^n} + \bar{\omega}^{2^n}, \\
\end{array}</math>
on l'últim pas surt de <math>\omega\bar{\omega} = (2 + \sqrt{3})(2 - \sqrt{3}) = 1</math>. Això es farà servir en les dues parts.
 
Línia 121:
Com que ''q''&nbsp;>&nbsp;2, <math>\omega</math> i <math>\bar{\omega}</math> són a X. Qualsevol producte de dos nombres de ''X'' és un nombre de ''X'', peró no és un [[grup (matemàtiques)|grup]] amb la multiplicació perquè no tot element ''x'' té un element invers ''y'' tal que ''xy'' = 1. Si es consideren només els elements que tenen inversos, es té un grup ''X''* de mida com a màxim <math>q^2-1</math> (donat que 0 no té invers).
 
Ara, com que <math>M_p \equiv 0 \pmod q</math>, i <math>\omega \in X</math>, es té <math>kM_p\omega^{2^{p-2}} = 0</math> de ''X'', el qual per l'equació (1) dona <math>\omega^{2^{p-1}} = -1</math>. Elevant al quadrat tots dos cantons dona <math>\omega^{2^p} = 1</math>, que mostra que <math>\omega</math> és invertible i la seva inversa és <math>\omega^{2^{p}-1}</math> i per tant pertany a ''X''*, i a demés té un [[ordre (teoria de grups) ordre]] que divideix <math>2^p</math>. De fet l'ordre ha de ser igual a <math>2^p</math>, donat que <math>\omega^{2^{p-1}} \neq 1</math> i per tant l'ordre no divideix a <math>2^{p-1}</math>. Com que l'ordre d'un element és com a màxim l'ordre (mida) del grup, s'arriba a la conclusió de què <math>2^p \leq q^2 - 1 < q^2</math>. Però com que ''q'' és un factor primer no trivial de <math>M_p</math>, ha de ser <math>q^2 \leq M_p = 2^p-1</math>, que dona la contradicció <math>2^p < 2^p-1</math>. Per tant <math>M_p</math> és primer.
 
=== Necessitat ===
Línia 142:
:<math>\begin{array}{lcl}
(6+\sigma)^{M_p} & = & 6^{M_p} + (2^{M_p})(\sqrt{3}^{M_p}) \\
& = & 6 + 2(3^{(M_p-1)/2})\sqrt{3} \\
& = & 6 + 2(-1)\sqrt{3} \\
& = & 6 - \sigma.
\end{array}</math>
 
Línia 151:
:<math>\begin{array}{lcl}
\omega^{(M_p+1)/2} & = & (6 + \sigma)^{M_p+1}/24^{(M_p+1)/2} \\
& = & (6 + \sigma)^{M_p}(6 + \sigma)/(24 \times 24^{(M_p-1)/2}) \\
& = & (6 - \sigma)(6 + \sigma)/(-24) \\
& = & -1.
\end{array}</math>
 
Obtingut de «https://ca.wikipedia.org/wiki/Prova_de_Lucas-Lehmer_per_a_nombres_de_Mersenne»