Lucas-Lehmers test

Den här artikeln behöver källhänvisningar för att kunna verifieras. (2020-06) Åtgärda genom att lägga till pålitliga källor (gärna som fotnoter). Uppgifter utan källhänvisning kan ifrågasättas och tas bort utan att det behöver diskuteras på diskussionssidan.

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

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

och

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

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

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

${\displaystyle 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:

${\displaystyle 11^{35}\ \equiv \ 70\ \not \equiv \ 1{\pmod {71}}}$

${\displaystyle 11^{14}\ \equiv \ 54\ \not \equiv \ 1{\pmod {71}}}$

${\displaystyle 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 prima. 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 finns det primitiv rot modulo n, och alla sådana primitiva rötter kommer att klara båda algoritmens steg.