Prova de Lucas-Lehmer per a nombres de Mersenne: diferència entre les revisions
Contingut suprimit Contingut afegit
Pàgina nova, amb el contingut: «:''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 Luc...». |
m Robot: substitució automàtica de text: (- es s + se s, - apren + aprèn , - aprén + aprèn , - exitós + reeixit , - exitosa + reeixida , -ïnt +int, -ïsme +isme, -ïsta +ista, - derrotar als + derrotar els , - derrotar al + derrotar el , - |
||
Línia 35:
:<math>k \equiv (k \hbox{ mod } 2^n) + \lfloor k/2^n \rfloor \pmod{2^n - 1}</math>.
En altres paraules, si s'agafen els ''n'' bits més significatius de ''k'', i se sumen a la resta de bits de ''k'', i
{|
Línia 55:
És més, com que <code>s × s</code> mai serà més gran que M<sup>2</sup> < 2<sup>2p</sup>, aquesta tècnica senzilla convergeix en, com a màxim 2 ''p'' sumes de bits, que es poden fer en temps lineal. Com a cas excepcional, poc probable, l'algorisme de més amunt pot donar 2<sup>''n''</sup>−1 com a múltiple del mòdul, en comptes del valor correcte zero; això cal tenir-ho en compte.
Amb el problema del mòdul resol, la complexitat asimptòtica de l'algorisme només depèn de l'[[algorisme de multiplicació]] que es fa servir per a elevar al quadrat ''s'' a cada pas. L'algorisme elemental per a la multiplicació necessita O(''p''<sup>2</sup>) operacions a nivell de bit o a nivell de paraula per a elevar al quadrat un nombre de ''p'' bits, i com que
En comparació, el [[test de primalitat]] més eficient conegut per a nombres primers aleatoris, el [[test de primalitat de Miller-Rabin]], necessita O(''k'' ''p''<sup>2</sup> log ''p'' log log ''p'') operacions binàries fent servir la multiplicació FFT (transformada ràpida de Fourier), on ''k'' és el nombre d'iteracions i està relacionat amb el percentatge d'error. Sembla que la diferència sigui un factor constant ''k'', però a la pràctica el cost de fer moltes iteracions i altres diferències porten al test de Miller-Rabin a una eficiència pitjor. La prova determinística més eficient per enters en general, la [[prova de primalitat AKS]], necessita Õ(p<sup>6</sup>) operacions binàries en la seva millor variant coneguda i a la pràctica és dramàticament més lent.
Línia 121:
Com que ''q'' > 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
=== Necessitat ===
| |||