I talteorien er Lucas primalitetstesten primalitetstesten for et naturligt tal n ; for at det virker, skal du kende faktoriseringen. For et primtal n udgør primtalsfaktorerne for tallet sammen med nogle grundtal a , et Pratt-certifikat , som gør det muligt i polynomisk tid at bevise, at n er et primtal.
Lad n > 1 være et naturligt tal. Hvis der er et heltal en sådan at og
og for enhver primtal divisor q af tallet
så er n primtal.
Hvis der ikke er et sådant tal a , så er n et sammensat tal .
Hvis n er primtal, så er restgruppen cyklisk, det vil sige, den har en generator, hvis rækkefølge falder sammen med rækkefølgen af gruppen , hvilket betyder, at for enhver prime divisor af tallet udføres en sammenligning:
Hvis n er sammensat, så enten og derefter , eller . Hvis vi antager, at for dette er a også opfyldt , så, da vi finder, at gruppen har et ordenselement , betyder det, at den deler sig , hvilket modsiger det faktum, at for sammensat n .
Ifølge modsætningsloven opnår vi Lucas-kriteriet.
Lad os for eksempel tage n = 71. Så . Lad os vælge tilfældigt . Vi beregner:
Lad os tjekke sammenligningerne for :
Desværre . Derfor kan vi endnu ikke hævde, at 71 er prime.
Lad os prøve et andet tilfældigt tal a , vælg . Vi beregner:
Tjek igen sammenligningerne for :
Således er 71 prime.
Bemærk, at til hurtig beregning af eksponenter modulo, bruges algoritmen for binær eksponentiering med at tage den resterende modulo n efter hver multiplikation.
Bemærk også, at for en simpel n følger det af den generaliserede Riemann-hypotese , at der blandt de første tal er mindst én generator af gruppen , så det kan betinget hævdes, at basen a kan findes i polynomisk tid.
Algoritmen, skrevet i pseudokode , er følgende:
Input : n > 2 er et ulige tal, der testes for primalitet; k - en parameter, der bestemmer nøjagtigheden af testen Konklusion : simpelt , hvis n er prime, ellers sammensat eller eventuelt sammensat ; Vi definerer alle primdivisorer . Loop1: Vælg tilfældigt a fra intervallet [2, n − 1] Hvis du returnerer en komposit Ellers Loop2: For alle primtal : Hvis Hvis vi ikke kontrollerede sammenligningen for alle så fortsætter vi med at udføre Loop2 ellers returnere en simpel Ellers vender du tilbage til Loop1 Det er muligt at returnere en komposit .Talteoretiske algoritmer | |
---|---|
Enkelthedstest | |
At finde primtal | |
Faktorisering |
|
Diskret logaritme | |
Finder GCD | |
Modulo aritmetik | |
Multiplikation og division af tal | |
Beregning af kvadratroden |