Luke's Simplicity Test

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 7. april 2021; verifikation kræver 1 redigering .

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. $n-1$ $n-1$

Beskrivelse

Lad n > 1 være et naturligt tal. Hvis der er et heltal en sådan at og $1<a<n$

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

og for enhver primtal divisor q af tallet $n-1$

a^{\frac {n-1}{q}}\ikke \equiv 1{\pmod {n}}

så er n primtal.

Hvis der ikke er et sådant tal a , så er n et sammensat tal .

Bevis

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: $\mathbb {Z} _{n}$ $g$ $|\mathbb {Z} _{n}^{\times }|=n-1$ $q$ $n-1$

a^{\frac {n-1}{q}}\ikke \equiv 1{\pmod {n}}.

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 . ${\text{gcd}}(a,n)>1$ $a^{n-1} \not\equiv 1 \pmod n$ $a^{n-1} \equiv 1 \pmod n$ $a^{\frac {n-1}{q}}\ikke \equiv 1{\pmod {n}}$ ${\frac {n-1}{q}}\midt n-1$ $\mathbb {Z} _{n}^{\times }$ $n-1$ $|\mathbb {Z} _{n}^{\times }|$ $n-1$ $|\mathbb {Z} _{n}^{\times }|=\varphi (n)<n-1$

Ifølge modsætningsloven opnår vi Lucas-kriteriet.

Eksempel

Lad os for eksempel tage n = 71. Så . Lad os vælge tilfældigt . Vi beregner: $n-1=70=2\cdot 5\cdot 7$ $a=17$

17^{70}\equiv 1{\pmod {71)).

Lad os tjekke sammenligningerne for : $a^{\frac {n-1}{q}}\ikke \equiv 1{\pmod {n}}$ $q=2;5;7$

17^{35}\equiv 70\not \equiv 1{\pmod {71}}

17^{14}\equiv 25\not \equiv 1{\pmod {71}}

17^{10}\equiv 1\equiv 1{\pmod {71)).

Desværre . Derfor kan vi endnu ikke hævde, at 71 er prime. $17^{10}\equiv 1\equiv 1{\pmod {71)).$

Lad os prøve et andet tilfældigt tal a , vælg . Vi beregner: $a=11$

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

Tjek igen sammenligningerne for : $a^{\frac {n-1}{q}}\ikke \equiv 1{\pmod {n}}$ $q=2;5;7$

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)).

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. $O(\ln ^{2}n)$ $\mathbb {Z} _{n}$

Algoritme

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 .

n-1

Loop1: Vælg tilfældigt a fra intervallet [2, n − 1] Hvis du returnerer en komposit

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

Ellers Loop2: For alle primtal :

q\midt n-1

Hvis Hvis vi ikke kontrollerede sammenligningen for alle

a^{\frac {n-1}{q}}\ikke \equiv 1{\pmod {n}}

q

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 .

Se også

Enkelhedstest

Litteratur

Vasilenko O. N. Talteoretiske algoritmer i kryptografi, MTsNMO, 2003
Trost E. - Primzahlen / Primtal - M .: GIFML, 1959, 135 s.

Talteoretiske algoritmer
Enkelthedstest	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Sachsen Nightingale - Strassen
At finde primtal	Iteration over divisorer Sigte af Eratosthenes Atkins si Sigte Sundarama
Faktorisering	Iteration over divisorer Fermat metode p −1 Pollard metode Pollards ρ-algoritme Lehmanns metode Elliptisk kurvemetode (Lenstras algoritme) Dixons algoritme Firkantet sigte
Diskret logaritme	Gelfond-Shanks algoritme Polig-Hellman algoritme Pollards ρ-metode Pollards kængurualgoritme Adlemans algoritme COS algoritme
Finder GCD	Euklids algoritme Avanceret algoritme Binær algoritme
Modulo aritmetik	Montgomerys algoritme Kinesisk restsætning
Multiplikation og division af tal	Karatsuba algoritme Toom-Cook algoritme Schönhage-Strassen algoritme Fuhrer algoritme Harvey-van der Hoeven algoritme Burnickel-Ziegler algoritme
Beregning af kvadratroden	Tonelli-Shanks algoritme Berlekamp-Rabin algoritme