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


 s_i=
 \begin{cases}
 4 & \mbox{si }i=0;
 \\
 s_{i-1}^2-2 & \mbox{altrament.}
 \end{cases}

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

s_{p-2}\equiv0\pmod{M_p};

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:

k \equiv (k \hbox{ mod } 2^n) + \lfloor k/2^n \rfloor \pmod{2^n - 1}.

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


 s_i=
 \begin{cases}
 4 & \mbox{si }i=0;
 \\
 s_{i-1}^2-2 & \mbox{altrament.}
 \end{cases}

Llavors el teorema és que Mp és primer si i només si s_{p-2}\equiv0\pmod{M_p}.

Es comença observant que {\langle}s_i{\rangle} és una relació de recurrència amb una solució en forma tancada. Es defineix \omega = 2 + \sqrt{3} i \bar{\omega} = 2 - \sqrt{3}; llavors es pot verificar per inducció que s_i = \omega^{2^i} + \bar{\omega}^{2^i} per a tot i:

s_0 = \omega^{2^0} + \bar{\omega}^{2^0} = (2 + \sqrt{3}) + (2 - \sqrt{3}) = 4.
\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}

on l'últim pas surt de \omega\bar{\omega} = (2 + \sqrt{3})(2 - \sqrt{3}) = 1. Això es farà servir en les dues parts.

Suficiència[modifica | modifica el codi]

En aquesta part s'ha de provar que s_{p-2}\equiv0\pmod{M_p} implica que M_p é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 s_{p-2} \equiv 0 \pmod{M_p}. Then \omega^{2^{p-2}} + \bar{\omega}^{2^{p-2}} = kM_p per a algun enter k, i:

\begin{array}{rcl}
\omega^{2^{p-2}} & = & kM_p - \bar{\omega}^{2^{p-2}} \\
\left(\omega^{2^{p-2}}\right)^2 & = & kM_p\omega^{2^{p-2}} - (\omega\bar{\omega})^{2^{p-2}} \\
\omega^{2^{p-1}} & = & kM_p\omega^{2^{p-2}} - 1.\quad\quad\quad\quad\quad(1) \\
\end{array}

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 X = \{a + b\sqrt{3} | a, b \in \mathbb{Z}_q\} amb q2 elements, on \mathbb{Z}_q són els enters mòdul q, un cos finit. L'operació multiplicació en X es defineix per:

(a + b\sqrt{3})(c + d\sqrt{3}) = [(ac + 3bd) \hbox{ mod } q] + [(bc + ad) \hbox{ mod } q]\sqrt{3}.

Com que q > 2, \omega i \bar{\omega} 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 q^2-1 (donat que 0 no té invers).

Ara, com que M_p \equiv 0 \pmod q, i \omega \in X, es té kM_p\omega^{2^{p-2}} = 0 de X, el qual per l'equació (1) dona \omega^{2^{p-1}} = -1. Elevant al quadrat tots dos cantons dona \omega^{2^p} = 1, que mostra que \omega és invertible i la seva inversa és \omega^{2^{p}-1} i per tant pertany a X*, i a més té un ordre (teoria de grups) ordre que divideix 2^p. De fet l'ordre ha de ser igual a 2^p, donat que \omega^{2^{p-1}} \neq 1 i per tant l'ordre no divideix a 2^{p-1}. Com que l'ordre d'un element és com a màxim l'ordre (mida) del grup, s'arriba a la conclusió de què 2^p \leq q^2 - 1 < q^2. Però com que q és un factor primer no trivial de M_p, ha de ser q^2 \leq M_p = 2^p-1, que dona la contradicció 2^p < 2^p-1. Per tant M_p és primer.

Necessitat[modifica | modifica el codi]

En aquesta altra part, se suposa que M_p és primer i es demostra que s_{p-2} \equiv0\pmod{M_p}. 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 M_p, donat que 2^p - 1 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 (3|M_p) és -1. Llavors el criteri d'Euler dona:

  • 3^{(M_p-1)/2} \equiv -1 \pmod{M_p}.

Per altra banda, 2 és un residu quadràtic mod M_p, donat que 2^p \equiv 1 \pmod{M_p} i per tant 2 \equiv 2^{p+1} = \left(2^{(p+1)/2}\right)^2 \pmod{M_p}. Altre cop el criteri d'Euler dona:

  • 2^{(M_p-1)/2} \equiv 1 \pmod{M_p}.

A continuació, es defineix \sigma = 2\sqrt{3}, i es defineix X* de manera similar a com s'ha fet abans com el grup multiplicatiu de \{a + b\sqrt{3} | a, b \in \mathbb{Z}_{M_p}\}. Es faran servir els següents lemes:

Llavors, en el grup X* es té:

\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}

Es selecciona \sigma tal que \omega = (6+\sigma)^2/24. En conseqüència, es pot fer servir això per a calcular \omega^{(M_p+1)/2} en el grup X*:

\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}

on es fa servir el fet que

  • 24^{(M_p-1)/2} = (2^{(M_p-1)/2})^3(3^{(M_p-1)/2}) = (1)^3(-1) = -1.

Com que M_p \equiv 3 \pmod 4, l'únic que manca és multiplicar els dos cantons d'aquesta equació per \bar{\omega}^{(M_p+1)/4} i fer servir \omega\bar{\omega}=1:

\begin{array}{rcl}
\omega^{(M_p+1)/2}\bar{\omega}^{(M_p+1)/4} & = & -\bar{\omega}^{(M_p+1)/4} \\
\omega^{(M_p+1)/4} + \bar{\omega}^{(M_p+1)/4} & = & 0 \\
\omega^{(2^p-1+1)/4} + \bar{\omega}^{(2^p-1+1)/4} & = & 0 \\
\omega^{2^{p-2}} + \bar{\omega}^{2^{p-2}} & = & 0 \\
s_{p-2} & = & 0. \\
\end{array}

Com que s_{p-2} és un enter i és zero a X*, també és zero mod M_p.

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 fina 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]