Från Rilpedia

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 så ä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

och

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:

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:

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

• Edouard Lucas
• Derrick Henry Lehmer
• Lucas–Lehmer test för Mersenneprimtal
• Primtal