Prova de Lucas-Lehmer per a nombres de Mersenne

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

La prova de Lucas-Lehmer funciona tal com s'explica tot seguit. Sia M_p = 2^p− 1 el nombre de Mersenne a provar amb p un Nombre primer senar (com que p és exponencialment més petit que M_p, 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_i} 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 M_p és primer si i només si

$s_{p-2}\equiv 0{\pmod {M_{p}}};$

Del nombre s_{p − 2} mod M_p se'n diu el residu de Lucas–Lehmer de p. (Alguns autors estableixen de forma equivalent s₁=4 i proven s_p−1 mod M_p). 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 altrament 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

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 2ⁿ−1 sense fer servir la divisió. Per exemple:

916 mod 2⁵−1	=	1110010100₂ mod 2⁵−1
	=	11100₂ + 10100₂ mod 2⁵−1
	=	110000₂ mod 2⁵−1
	=	1₂ + 10000₂ mod 2⁵−1
	=	10001₂ mod 2⁵−1
	=	10001₂
	=	17.

És més, com que s × s mai serà més gran que M² < 2^2p, 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ⁿ−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²) 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³). 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² log p log log p) o Õ(p²).

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

Exemples

Suposeu que es vol verificar que M₃ = 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, M₃ és primer.

Per altra banda, M₁₁ = 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, M₁₁=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ó

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 M_p és primer si i només si $s_{p-2}\equiv 0{\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

En aquesta part s'ha de provar que $s_{p-2}\equiv 0{\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, aquí s'exposa tal com la presenta en Jason Wojciechowski.

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 M_p é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 q² 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

En aquesta altra part, se suposa que $M_{p}$ és primer i es demostra que $s_{p-2}\equiv 0{\pmod {M_{p}}}$. Es presenta una simplificació de la demostració de Öystein J. R. Ödseth. 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:

• $(x+y)^{M_{p}}\equiv x^{M_{p}}+y^{M_{p}}{\pmod {M_{p}}}$ (de Demostracions del petit teorema de Fermat#Demostració fent servir el teorema binomial)
• $a^{M_{p}}\equiv a{\pmod {M_{p}}}$ per a tot enter a (petit teorema de Fermat)

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

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. 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é

• Prova de Lucas-Lehmer
• Conjectura de Mersenne

Referències

• Richard Crandall and Carl Pomerance. Prime Numbers: A Computational Perspective. 1st edition. Springer, 2001. ISBN 0387947779.  Section 4.2.1: The Lucas–Lehmer test, pp.167–170.

Enllaços externs

• MathWorld: Lucas–Lehmer test
• GIMPS (The Great Internet Mersenne Prime Search)
• A proof of Lucas–Lehmer test Arxivat 2008-11-08 a Wayback Machine.
• Lucas–Lehmer test Arxivat 2016-02-16 a Wayback Machine. at MersenneWiki