Luke's Simplicity Test

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 7 april 2021; verifiering kräver 1 redigering .

I talteorin är Lucas primalitetsteste primalitetstestet för ett naturligt tal n ; för att det ska fungera måste du känna till faktoriseringen. För ett primtal n utgör primtalsfaktorerna för talet , tillsammans med någon bas a , ett Pratt-certifikat , som gör att man kan bevisa i polynomtid att n är ett primtal. $n-1$ $n-1$

Beskrivning

Låt n > 1 vara ett naturligt tal. Om det finns ett heltal en sådan att och $1<a<n$

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

och för valfri primtalsdelare q av talet $n-1$

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

då är n primtal.

Om det inte finns något sådant tal a , så är n ett sammansatt tal .

Bevis

Om n är primtal är restgruppen cyklisk, det vill säga den har en generator vars ordning sammanfaller med gruppens ordning , vilket innebär att en jämförelse utförs för varje primtalsdelare av talet : $\mathbb {Z} _{n}$ $g$ $|\mathbb {Z} _{n}^{\times }|=n-1$ $q$ $n-1$

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

Om n är sammansatt, då antingen och sedan , eller . Om vi antar att för detta också är a uppfyllt , då, eftersom vi finner att gruppen har ett ordningselement , betyder det att den delar sig , vilket motsäger det faktum att för sammansatt 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}}\not \equiv 1{\pmod {n}}$ ${\frac {n-1}{q}}\mid n-1$ $\mathbb {Z} _{n}^{\times }$ $n-1$ $|\mathbb {Z} _{n}^{\times }|$ $n-1$ $|\mathbb {Z} _{n}^{\times }|=\varphi (n)<n-1$

Enligt kontrapositionslagen får vi Lucas-kriteriet.

Exempel

Låt oss till exempel ta n = 71. Sedan . Låt oss välja slumpmässigt . Vi beräknar: $n-1=70=2\cdot 5\cdot 7$ $a=17$

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

Låt oss kolla jämförelserna för : $a^{\frac {n-1}{q}}\not \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)).

Tyvärr . Därför kan vi ännu inte hävda att 71 är prime. $17^{10}\equiv 1\equiv 1{\pmod {71)).$

Låt oss prova ett annat slumpmässigt nummer a , välj . Vi beräknar: $a=11$

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

Kontrollera jämförelserna igen för : $a^{\frac {n-1}{q}}\not \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 är 71 prime.

Observera att för snabb beräkning av exponenter modulo, används algoritmen för binär exponentiering med att ta resten av modulo n efter varje multiplikation.

Observera också att för ett enkelt n , följer det av den generaliserade Riemann-hypotesen att det bland de första talen finns minst en generator av gruppen , så det kan villkorligt hävdas att basen a kan hittas i polynomtid. $O(\ln ^{2}n)$ $\mathbb {Z} _{n}$

Algoritm

Algoritmen, skriven i pseudokod , är följande:

Inmatning : n > 2 är ett udda tal som testas för primalitet; k - en parameter som bestämmer testets noggrannhet Slutsats : enkelt om n är primtal, annars sammansatt eller möjligen sammansatt ; Vi definierar alla primtalare .

n-1

Slinga1: Välj slumpmässigt a från intervallet [2, n − 1] Om du returnerar en komposit

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

Annat Slinga 2: För alla primtal :

q\mid n-1

Om Om vi inte kontrollerade jämförelsen för alla

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

q

sedan fortsätter vi att köra Loop2 annars returnera en enkel Annars, återgå till Loop1 Det är möjligt att returnera en komposit .

Se även

Enkelhetstest

Litteratur

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

Talteoretiska algoritmer
Enkelhetstest	Mjölnare Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Sachsen Nightingale - Strassen
Hitta primtal	Itererar över divisorer Sil av Eratosthenes Atkins såll Sikt Sundarama
Faktorisering	Itererar över divisorer Fermat-metoden p −1 Pollardmetoden Pollards ρ-algoritm Lehmanns metod Elliptisk kurvmetod (Lenstras algoritm) Dixons algoritm Fyrkantig sil
Diskret logaritm	Gelfond-Shanks algoritm Polig-Hellman algoritm Pollards ρ-metod Pollards kängurualgoritm Adlemans algoritm COS-algoritm
Hitta GCD	Euklids algoritm Avancerad algoritm Binär algoritm
Modulo aritmetik	Montgomerys algoritm Kinesisk restsats
Multiplikation och division av tal	Karatsuba algoritm Toom-Cook algoritm Schönhage-Strassen algoritm Fuhrer algoritm Harvey-van der Hoevens algoritm Burnickel-Ziegler algoritm
Beräkna kvadratroten	Tonelli-Shanks algoritm Berlekamp-Rabin algoritm