Prova de Lucas-Lehmer per a nombres de Mersenne: diferència entre les revisions
Contingut suprimit Contingut afegit
m Bot elimina espais sobrants |
m neteja i estandardització de codi |
||
Línia 4:
==La prova==
La prova de Lucas-Lehmer funciona tal com s'explica tot seguit. Sia ''M''<sub>''p''</sub> = 2<sup>''p''</sup>− 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 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>
Linha 30 ⟶ 29:
== Complexitat ==
A l'algorisme que s'ha escrit més amunt, hi ha dues operacions pesades a cada iteració: la multiplicació <code>s × s</code>, i l'operació <code>mod M</code>. L'operació <code>mod M</code> es pot realitzar de forma particularment eficient en ordinadors binaris estàndard observant la següent propietat senzilla:
Linha 60 ⟶ 58:
== Exemples ==
Suposeu que es vol verificar que M<sub>3</sub> = 7 és primer fent servir la prova de Lucas-Lehmer. Es comença amb ''s'' igual a 4 i llavors s'actualitza 3−2 = 1 cop, agafant els resultats mod 7:
Linha 82 ⟶ 79:
== Demostració ==
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>
Linha 105 ⟶ 101:
=== Suficiència ===
En aquesta part s'ha de provar que <math>s_{p-2}\equiv0\pmod{M_p}</math> implica que <math>M_p</math> és primer. S'explica una demostració directa que explita la [[teoria de grups]] elemental. Aquesta demostració la va obtenir en J. W. Bruce,<ref>J. W. Bruce. A Really Trivial Proof of the Lucas-Lehmer Test. ''The American Mathematical Monthly'', Vol.100, No.4, pp.370–371. April 1993.</ref> aquí s'exposa tal com la presenta en Jason Wojciechowski.<ref>Jason Wojciechowski. Mersenne Primes, An Introduction and Overview. January 2003. http://wonka.hampshire.edu/~jason/math/smithnum/project.ps</ref>
▲En aquesta part s'ha de provar que <math>s_{p-2}\equiv0\pmod{M_p}</math> implica que <math>M_p</math> és primer. S'explica una demostració directa que explita la [[teoria de grups]] elemental. Aquesta demostració la va obtenir en J. W. Bruce,<ref>J. W. Bruce. A Really Trivial Proof of the Lucas-Lehmer Test. ''The American Mathematical Monthly'', Vol.100, No.4, pp.370–371. April 1993.</ref> aquí s'exposa tal com la presenta en Jason Wojciechowski.<ref>Jason Wojciechowski. Mersenne Primes, An Introduction and Overview. January 2003. http://wonka.hampshire.edu/~jason/math/smithnum/project.ps</ref>
Se suposa que <math>s_{p-2} \equiv 0 \pmod{M_p}</math>. Then <math>\omega^{2^{p-2}} + \bar{\omega}^{2^{p-2}} = kM_p</math> per a algun enter ''k'', i:
Linha 124 ⟶ 119:
=== Necessitat ===
En aquesta altra part, se suposa que <math>M_p</math> és primer i es demostra que <math>s_{p-2} \equiv0\pmod{M_p}</math>. Es presenta una simplificació de la demostració de Öystein J. R.
Ödseth.<ref>Öystein J. R. Ödseth. A note on primality tests for N = h • 2n − 1. Department of Mathematics, University of Bergen. http://www.uib.no/People/nmaoy/papers/luc.pdf</ref> Primer, fixeu-vos que 3 no és un [[residu quadràtic]] mod <math>M_p</math>, donat que <math>2^p - 1</math> per a ''p''>1 senars només pren el valor 7 mod 12, i per tant les propietats del [[símbol de Legendre]] diuen que <math>(3|M_p)</math> és -1. Llavors el [[criteri d'Euler]] dona:
Linha 173 ⟶ 167:
== Aplicacions ==
La prova de Lucas-Lehmer és la prova de primalitat que fa servir el [[GIMPS]] ("Great Internet Mersenne Prime Search") per a localitzar nombre primers grans, i ha tingut èxit en la localització de molts del nombres primers més grans coneguts fins a la data.<ref>GIMPS Home Page. Frequently Asked Questions: General Questions: What are Mersenne primes? How are they useful? http://www.mersenne.org/faq.htm#what</ref> Es considera valuós per a trobar nombres primers molt grans perquè es considera que els nombres de Mersenne és més fàcil que siguin primers que no pas els nombres senars triats a l'atzar de la mateixa mida. Addicionalment, es considera que la prova és valuosa perquè es pot fer servir com a [[test de primalitat]] per a nombres molt grans en un temps accessible i (en contrast amb l'equivalent test ràpid de Pépin per a qualsevol [[nombre de Fermat]]) es pot provar en un espai de nombres de cerca gran i amb la forma requerida abans d'assolir el límits computacionals.
Linha 181 ⟶ 174:
== Referències ==
* {{ref-llibre|autor = [[Richard Crandall]] and [[Carl Pomerance]] | any = 2001 | títol = Prime Numbers: A Computational Perspective | editorial = Springer | edició = 1st edition | isbn = 0387947779}} Section 4.2.1: The Lucas–Lehmer test, pp.167–170.
{{Referències}}
| |||