Prova de Lucas-Lehmer per a nombres de Mersenne: diferència entre les revisions
Contingut suprimit Contingut afegit
m Tipografia |
|||
Línia 36:
{|
|916 mod
|-
| || = || 11100<sub>2</sub> + 10100<sub>2</sub> mod
|-
| || = || 110000<sub>2</sub> mod
|-
| || = || 1<sub>2</sub> + 10000<sub>2</sub> mod
|-
| || = || 10001<sub>2</sub> mod
|-
| || = || 10001<sub>2</sub>
Línia 55:
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 això s'ha de fer O(''p'') cops, la complexitat total és O(''p''<sup>3</sup>). El mètode de multiplicació més eficient conegut, l'[[algorisme de Schönhage-Strassen]] basat en la [[Transformada Ràpida de Fourier]], necessita O(''p'' log ''p'' log log ''p'') operacions per a elevar al quadrat un nombre de ''p'' bits, amb lo que es redueix la complexitat a O(''p''<sup>2</sup> log ''p'' log log ''p'') o Õ(''p''<sup>2</sup>).<ref>W. N. Colquitt, L. Welsh, Jr. A New Mersenne Prime. ''Mathematics of Computation'', Vol.56, No.194, pp.867–870. April 1991. "The use of the FFT speeds up the asymptotic time for the Lucas-Lehmer test for M<sub>''p''</sub> from O(''p''<sup>3</sup>) to O(''p''<sup>2</sup> log ''p'' log log ''p'') bit operations."</ref>
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 Õ(
== Exemples ==
| |||