Lucas-Lehmers test
Wikipedia
 |
Denna artikel innehåller ifrågasatta faktauppgifter. |
| Se diskussionssidan, eller historiken, för mer information. Rätta gärna felaktigheter. |
- 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-Lehmertets för Mersenneprimtal.
I talteori så är Lucas-Lehmertestet ett primtalstest för naturliga talet n; det krävs att primtalsfaktorn n − 1 redan är känt.
Om det finns något a mindre än n och större än 1 så att först
och sen
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 definieras 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. Motsatt, 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.
[redigera] Se även
- Edouard Lucas
- Derrick Henry Lehmer
- Lucas–Lehmer test för Mersenneprimtal
- Primtal
