Lucas-Lehmers test

Från Wikipedia
Hoppa till: navigering, sök
Denna artikel handlar om generella Lucas-Lehmer test för primtal. Det finns även ett Lucas-Lehmertest som enbart är applicerbart på Mersenneprimtal; se Lucas-Lehmertest för Mersenneprimtal.

I talteori är Lucas-Lehmertestet ett primtalstest för naturliga talet n; det krävs att primtalsfaktorerna i n − 1 redan är kända

Om det för varje primtalsfaktor q i n-1 finns något a mindre än n och större än 1 så att både

a^{n-1}\ \equiv\ 1 \pmod n

och

a^{({n-1})/q}\ \not\equiv\ 1 \pmod n

gäller för alla primtalsfaktorer q av n -1, så är n ett primtal. Om inget sådant tal a kan hittas, så är n ett sammansatt tal.

Exempelvis, om n = 71, n − 1 = 70 = (2)(5)(7). Testa a = 11 först:

11^{70}\ \equiv\ 1 \pmod {71}

Detta visar inte att multiplikatordningen av 11 mod 71 är 70 då någon faktor av 70 och kan fungera ovan. Så testa 70 delat med dess primtalsfaktorer:

11^{35}\ \equiv\ 70\ \not\equiv\ 1 \pmod {71}
11^{14}\ \equiv\ 54\ \not\equiv\ 1 \pmod {71}
11^{10}\ \equiv\ 32\ \not\equiv\ 1 \pmod {71}

Multiplikatsordnignen av 11 mod 71 är 70, således är 71 ett primtal.

För att göra denna modulära exponentiering bör man alltid börja med att använda binär exponentiering.

Algoritmens korrekthet förklaras som följer: om a klarar första steget av algoritmen kan vi sluta oss till att a och n är relativt primtal. Om a också klarar andra steget, då är a i gruppen (Z/nZ)* lika med n − 1, vilket betyder att den gruppens ordning är n - 1, vilket antyder att n är ett primtal. Omvänt, om n är ett primtal så finns det primitiv rot modulo n, och alla sådana primitiva rötter kommer att klara båda algoritmens steg.

Se även[redigera | redigera wikitext]