Prova de Lucas-Lehmer per a nombres de Mersenne

De Viquipèdia
Dreceres ràpides: navegació, cerca
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 nombres de Mersenne. La prova va ser desenvolupada inicialment per Edouard Lucas el 1856 [1][2], i posteriorment millorada per Lucas el 1878 i Derrick Henry Lehmer a la dècada del 1930.

La prova[modifica | modifica el codi]

La prova de Lucas-Lehmer funciona tal com s'explica tot seguit. Sia Mp = 2p− 1 el nombre de Mersenne a provar amb p un Nombre primer senar (com que p és exponencialment més petit que Mp, es pot fer servir un algorisme senzill com ara el de divisions successives per tal d'establir la seva primalitat). Es defineix una successió {si} per a tot i ≥ 0 com

Els primers termes d'aquesta successió són 4, 14, 194, 37634, ... (successió A003010 a l'OEIS). Llavors Mp és primer si i només si

Del nombre sp − 2 mod Mp se'n diu el residu de Lucas–Lehmer de p. (Alguns autors estableixen de forma equivalent s1=4 i proven sp−1 mod Mp). En pseudocodi, la prova s'escriu:

// Determinar se Mp = 2p − 1 és primer
Lucas-Lehmer(p)
var s ← 4
var M ← 2p − 1
repetir p − 2 cops:
s ← ((s × s) − 2) mod M
si s = 0 retorna PRIMER sinó retorna COMPOST

Al realitzar l'operació mod M 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.

Complexitat[modifica | modifica el codi]

A l'algorisme que s'ha escrit més amunt, hi ha dues operacions pesades a cada iteració: la multiplicació s × s, i l'operació mod M. L'operació mod M es pot realitzar de forma particularment eficient en ordinadors binaris estàndard observant la següent propietat senzilla:

.

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 això es repeteix fins que com a màxim quedin n bits, es pot calcular el residu de dividir k pel nombre de Mersenne 2n−1 sense fer servir la divisió. Per exemple:

916 mod 25−1 = 11100101002 mod 25−1
= 111002 + 101002 mod 25−1
= 1100002 mod 25−1
= 12 + 100002 mod 25−1
= 100012 mod 25−1
= 100012
= 17.

És més, com que s × s mai serà més gran que M2 < 22p, 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 2n−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(p2) 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(p3). 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(p2 log p log log p) o Õ(p2).[1]

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 p2 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 Õ(p6) operacions binàries en la seva millor variant coneguda i a la pràctica és dramàticament més lent.

Exemples[modifica | modifica el codi]

Suposeu que es vol verificar que M3 = 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:

  • s ← ((4 × 4) − 2) mod 7 = 0

Com que s'acaba amb s igual a zero, M3 és primer.

Per altra banda, M11 = 2047 = 23 × 89 no és primer. Per provar-ho, es comença amb s igual a 4 i s'actualitza 11−2 = 9 cops, prenent els resultats mod 2047:

  • s ← ((4 × 4) − 2) mod 2047 = 14
  • s ← ((14 × 14) − 2) mod 2047 = 194
  • s ← ((194 × 194) − 2) mod 2047 = 788
  • s ← ((788 × 788) − 2) mod 2047 = 701
  • s ← ((701 × 701) − 2) mod 2047 = 119
  • s ← ((119 × 119) − 2) mod 2047 = 1877
  • s ← ((1877 × 1877) − 2) mod 2047 = 240
  • s ← ((240 × 240) − 2) mod 2047 = 282
  • s ← ((282 × 282) − 2) mod 2047 = 1736

Com que s no és zero, M11=2047 no és primer. Fixeu-vos que no se'n sap res dels factors de 2047, tret del seu residu de Lucas–Lehmer, 1736.

Demostració[modifica | modifica el codi]

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ó:

Llavors el teorema és que Mp és primer si i només si

Es comença observant que és una relació de recurrència amb una solució en forma tancada. Es defineix i ; llavors es pot verificar per inducció que per a tot i:

on l'últim pas surt de . Això es farà servir en les dues parts.

Suficiència[modifica | modifica el codi]

En aquesta part s'ha de provar que implica que és primer. S'explica una demostració directa que explita la teoria de grups elemental. Aquesta demostració la va obtenir en J. W. Bruce,[2] aquí s'exposa tal com la presenta en Jason Wojciechowski.[3]

Se suposa que . Then per a algun enter k, i:

Ara se suposa que Mp és compost amb un factor primer no trivial q > 2 (tots els nombres de Mersenne són senars). Es defineix el conjunt amb q2 elements, on són els enters mòdul q, un cos finit. L'operació multiplicació en X es defineix per:

.

Com que q > 2, i són a X. Qualsevol producte de dos nombres de X és un nombre de X, però no és un 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 (donat que 0 no té invers).

Ara, com que , i , es té de X, el qual per l'equació (1) dona . Elevant al quadrat tots dos cantons dona , que mostra que és invertible i la seva inversa és i per tant pertany a X*, i a més té un ordre (teoria de grups) ordre que divideix . De fet l'ordre ha de ser igual a , donat que i per tant l'ordre no divideix a . Com que l'ordre d'un element és com a màxim l'ordre (mida) del grup, s'arriba a la conclusió de què . Però com que q és un factor primer no trivial de , ha de ser , que dóna la contradicció . Per tant és primer.

Necessitat[modifica | modifica el codi]

En aquesta altra part, se suposa que és primer i es demostra que . Es presenta una simplificació de la demostració de Öystein J. R. Ödseth.[4] Primer, fixeu-vos que 3 no és un residu quadràtic mod , donat que 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 és -1. Llavors el criteri d'Euler dona:

  • .

Per altra banda, 2 és un residu quadràtic mod , donat que i per tant . Altre cop el criteri d'Euler dona:

  • .

A continuació, es defineix , i es defineix X* de manera similar a com s'ha fet abans com el grup multiplicatiu de . Es faran servir els següents lemes:

Llavors, en el grup X* es té:

Es selecciona tal que . En conseqüència, es pot fer servir això per a calcular en el grup X*:

on es fa servir el fet que

Com que , l'únic que manca és multiplicar els dos cantons d'aquesta equació per i fer servir :

Com que és un enter i és zero a X*, també és zero mod .

Aplicacions[modifica | modifica el codi]

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.[5] 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.

Vegeu també[modifica | modifica el codi]

Referències[modifica | modifica el codi]

  1. 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 Mp from O(p3) to O(p2 log p log log p) bit operations."
  2. 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.
  3. Jason Wojciechowski. Mersenne Primes, An Introduction and Overview. January 2003. http://wonka.hampshire.edu/~jason/math/smithnum/project.ps
  4. Ö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
  5. GIMPS Home Page. Frequently Asked Questions: General Questions: What are Mersenne primes? How are they useful? http://www.mersenne.org/faq.htm#what

Enllaços externs[modifica | modifica el codi]