Agravala-Kayala-Saxene test

Test Agrawal-Kayal-Saxena ( AKS test ) je jediným v současnosti známým univerzálním (tj. aplikovatelným na všechna čísla) polynomiálním , deterministickým a nepodmíněným (tj. nezávislým na neprokázaných hypotézách) testem primality čísel, založeným na zobecnění Fermatovy malé věty o polynomech.

Formulace

Pokud existuje takové, že a pro libovolné od 1 do , pak je buď prvočíslo, nebo mocnina prvočísla. $r\in \mathbb {Z}$ $o_{r}(n)>\log ^{2}n$ $A$ $\left\lfloor {\sqrt {\varphi (r)))\log(n)\right\rfloor$ $(x+a)^{n}\equiv (x^{n}+a){\pmod {x^{r}-1,\;n))$
$n$

Zde a níže , označuje exponent modulo , je binární logaritmus a je Eulerova funkce [1] . $o_{r}(n)$ $n$ $r$ $\log$ $\varphi (\cdot)$

Porovnání pomocí dvou modulů formuláře

a(x)\equiv b(x){\pmod {h(x),\;n))

pro polynomy znamená, že existuje takové, že všechny koeficienty polynomu jsou násobky , kde je kruh polynomů z více než celých čísel [1] . $a(x),\;b(x)\in \mathbb {Z} [x]$ $g(x)\in \mathbb {Z} [x]$ $a(x)-b(x)-g(x)h(x)$ $n$ $\mathbb {Z} [x]$ $X$

Historie

Test AKS navrhl indický vědec Manindra Agrawal a jeho dva studenti Niraj Kayal a Nitin Saxena z Indian Institute of Technology Kanpur a byl poprvé publikován 6. srpna. , 2002 [2] . Před touto publikací byla příslušnost problému rozpoznání primality ke třídě P otevřeným problémem .

Výpočetní složitost původního algoritmu je odhadnuta jako . Za předpokladu , že Artinova domněnka je pravdivá , se doba běhu zlepší na . Za předpokladu správnosti hypotézy Sophie Germainové má čas také tendenci [2] . ${\mathcal {O}} (\log ^{21/2}n)$ ${\mathcal {O}} (\log ^{6}n)$ ${\mathcal {O}} (\log ^{6}n)$

V roce 2005 Lenstra a Pomerance publikovali vylepšenou verzi algoritmu s výpočetní složitostí , kde je číslo, které má být zkontrolováno testem [3] [4] . ${\mathcal {O}} (\log ^{6}n)$ $n$

Podle Agrawalova dohadu existuje varianta algoritmu s runtime , ale Lenstra a Pomerans předložili heuristický argument potvrzující nepravdivost této hypotézy [2] . ${\mathcal {O}} (\log ^{3}n)$

Tento algoritmus má velký teoretický význam, ale v praxi se nepoužívá, protože jeho výpočetní náročnost je mnohem vyšší než u nejlepších pravděpodobnostních algoritmů [5] . Za svůj objev obdrželi autoři v roce 2006 Gödelovu cenu a Fulkersonovu cenu [6] .

Základní vlastnosti

Hlavní vlastností algoritmu je, že je současně univerzální , polynomiální , deterministický a nepodmíněný [5] , předchozí algoritmy měly maximálně pouze tři z těchto čtyř vlastností.

Univerzálnost testu znamená, že jej lze použít k testování primálnosti libovolného čísla. Mnoho rychlých testů je navrženo k testování čísel z omezené sady. Například Lucas-Lehmerův test funguje pouze pro Mersennova čísla , zatímco Pepinův test funguje pouze pro Fermatova čísla [6] .

Polynom znamená, že maximální doba běhu algoritmu je omezena polynomem v počtu číslic v kontrolovaném čísle. Zároveň testy jako test eliptické křivky (ECPP) a Adlemann-Pomerance-Rumeliho test (APR) mohou prokázat nebo vyvrátit jednoduchost čísla, ale nebylo prokázáno, že doba běhu bude polynomiální pro libovolné vstupní číslo [6] .

Determinismus zaručuje jedinečný předem definovaný výsledek. Pravděpodobnostní testy , jako je Miller-Rabinův test a Bailey-Pomeranz-Selfridge-Wagstaffův test , mohou testovat, zda je číslo prvočíslo v polynomiálním čase, ale dávají pouze pravděpodobnostní odpověď [6] .

Bezpodmínečnost je vlastnost, že správnost algoritmu nezávisí na žádných neprokázaných hypotézách. Tuto vlastnost nemá například Millerův test , který je sice deterministický a pracuje v polynomiálním čase pro libovolné vstupní číslo, ale jeho správnost závisí na neprokázané zobecněné Riemannově hypotéze [6] .

Hlavní myšlenka

Hlavní myšlenkou algoritmu je zobecnění Fermatovy Malé věty na polynomy, které uvádí, že pro všechny (kde kruh je brán bez inverzí násobením a nulovým prvkem) a , je jednoduchý tehdy a jen tehdy, když [2] [7] [8] : $a\in \mathbb {Z} _{n}^{*}$ $\mathbb {Z} _{n}$ $n\in \mathbb {N}$ $n$

$(x+a)^{n}\equiv (x^{n}+a){\pmod {n)).$

jeden

Jinými slovy, jestliže , , a gcd , potom je prvočíslo právě tehdy, když je splněna podmínka (1) . $a\in \mathbb {Z}$ $n\in \mathbb{N}$ $n\geqslant 2$ $(a,\;n)=1$ $n$

Testování tohoto výrazu vyžaduje čas, odhadovaný na , protože v nejhorším případě by měly být vyhodnoceny koeficienty na levé straně. Pro snížení počtu koeficientů a složitosti výpočtů bylo zvoleno použití výrazu [2] jako testu pro jednoduchost : $\omega(n)$ $n$ $r$

(x+a)^{n}\equiv (x^{n}+a){\pmod {x^{r}-1,\;n)),

který získáme vydělením obou částí původního výrazu [7] . $x^{r}-1$

Zde je počet hodnot ke kontrole a hodnota již omezena polynomem z [8] . $A$ $r$ $\log n$

V tomto případě místo kvocientového kruhu uvažujeme pole , kde je ireducibilní dělitel nad konečným polem , odlišné od . Počet polynomů tohoto pole, pro které se provádí srovnání, se odhaduje: $\mathbb {F} _{p}[x]/\langle x^{r}-1\rangle$ $F=\mathbb {F} _{p}[x]/\langle h\rangle$ $h=h(x)$ ${x^{r}-1}$ $\mathbb {F} _{p}$ $x-1$

(x+a)^{n}\equiv (x^{n}+a){\pmod {x^{r}-1,\;n)).

Algoritmus a jeho modifikace

Vstup: celé číslo .

n>1

Pokud pro celá čísla a , vraťte "složený" . ${\displaystyle n=a^{b))$ $a>1$ $b>1$
Najděte nejmenší takový, že . $r$ $o_{r}(n)>(\log _{2}(n))^{2}$
Pokud je gcd pro některé , vraťte "složený" . $1<$ $(a,\;n)<n$ $a\leqslant r$
Pokud , vraťte "jednoduché" . $n\leqslant r$
Pokud pro všechny od 1 do platí, že , vraťte "simple" . $A$ $\left\lfloor {\sqrt {\varphi (r)))\log(n)\right\rfloor$ $(x+a)^{n}\equiv x^{n}+a{\pmod {x^{r}-1,\;n))$
Jinak vraťte "složený" .

Agrawal, Kayal a Saxena dokázali, že algoritmus vrátí "prvočíslo" tehdy a jen tehdy, když je prvočíslo. $n$

Lenstra a Pomerance zveřejnili vylepšenou verzi algoritmu [8] [4] :

Vstup: ,

n\in \mathbb{N}

n>1

Pokud for a integer , vraťte "složený" . ${\displaystyle n=a^{b))$ $a\in \mathbb {N}$ $b>1$
Pojďme najít nejmenší takový, že . $r$ $o_{r}(n)>(log_{2}(n))^{2}$
Pokud je gcd pro any , vraťte "složený" . $(a,\;n)\neq 1$ $a\leqslant r$
Pokud pro všechny od 1 do platí, že , vraťte "simple" . $A$ $\left\lfloor {\sqrt {r}}\log n\right\rfloor$ $(x+a)^{n}\equiv x^{n}+a{\pmod {\varphi (x),\;n))$
Jinak vraťte "složený" .

Zde je funkce stejná, jedná se o polynom stupně většího než , takže za určitých dalších podmínek [1] [8] . $\varphi(x)$ $x^{r}-1$ $\log ^{2}n$ $\varphi (x^{n})\equiv 0{\pmod {\varphi (x)))$

Výpočetní složitost tohoto algoritmu je . ${\mathcal {O}} (\log ^{6}n)$

Odůvodnění

Odůvodnění používá skupinu — skupinu všech čísel, která jsou modulo zbytky pro čísla z množiny [9] : $G$ $r$

I=\left\{\left({\frac {n}{p}}\right)^{i}\cdot p^{j}\colon i,\;j\geqslant 0\right\} .

Tato podskupina, nazvěme ji skupina , již obsahuje . Skupina je generována modulo a od té doby . $G$ $(n,\;r)=(p,\;r)=1$ $G$ $n,p$ $r$ $o_{r}(n)>\log ^{2}n$ $|G|=t>\log ^{2}n$

Druhá skupina použitá v důkazu, , je množina všech polynomických zbytků v (prvoprostoru) modulo a . Tato skupina je generována prvky v poli a je podskupinou multiplikativní skupiny pole [9] . $|{\mathcal {G}}|$ $P$ $h(x)$ $p$ $x,\;x+1,\;x+2,\;\ldots ,\;x+l$ $F=\mathbb {F} _{p}[x]/\langle h(x)\rangle$ $\mathbb {F} _{p}$

Hlavní přechodná lemmata a definice použité při zdůvodnění algoritmu [2] :

Nechte , , a gcd . Pak je prvočíslo tehdy a jen tehdy $a,\;n\in \mathbb {Z}$ $n\geqslant 2$ $(a,\;n)=1$ $n$ $(x+a)^{n}\equiv x^{n}+a{\pmod {n)).$
Nechť LCM označuje nejmenší společný násobek prvních čísel. Pak platí následující nerovnost: $(m)$ $m$ $m\geqslant 7$ NOC $(m)\geqslant 2^{m}.$
Existuje takové to , takové to . $r$ ${\displaystyle r\leqslant \max {\big (}3,\;\lceil \log ^{5}n\rceil {\big )))$ $o_{r}(n)>\log ^{2}n$
Definice. U polynomu a čísla říká, co je zahrnuto v if . $f(x)$ $m\in \mathbb {N}$ $m$ $f(x)$ $\lceil f(x)\rceil ^{m}\equiv f(x^{m}){\pmod {x^{r}-1,\;p))$
Pokud jsou čísla a zahrnuta v , pak je zahrnut i jejich produkt . $m$ $m'$ $f(x)$ $m\cdot m'$
Pokud je číslo zahrnuto v a , pak je zahrnuto také v . $m$ $f(x)$ $g(x)$ $m$ $f(x)\cdot g(x)$
Lenstrovo lemma . . $|{\mathcal {G}}|\geqslant {\tbinom {t+l}{t-1}}$
Pokud to není titul , pak . $n$ $p$ $|{\mathcal {G}}|\leqslant n^{\sqrt {t}}$

Praktická aplikace

Při vyhodnocování parametru vyžaduje algoritmus 1 000 000 000 GB ( gigabajtů ) paměti pro čísla 1024 bitů. Pro moderní operační systémy je to příliš mnoho informací. Za předpokladu správnosti Artinovy hypotézy a hypotézy Sophie Germainové o hustotě množiny prvočísel bude pro algoritmus dostatečná hodnota parametru odhadnutá na . V tomto případě bude stačit 1 GB paměti. Ale dokud není správnost těchto hypotéz prokázána, algoritmus není aplikován kvůli složitému provádění. Donald Knuth , který umístil algoritmus do druhého dílu The Art of Programming (Vol. 3), zaznamenal v soukromé korespondenci jeho čistě teoretický charakter [6] . $r={\mathcal {O}}(\log ^{5}n)$ $r$ ${\mathcal {O}}(\log ^{2}n)$

Poznámky

↑ 1 2 3 Agafonova, 2009 .
↑ 1 2 3 4 5 6 Agrawal, Kayal, Saxena, 2004 .
↑ H. W. Lenstra Jr. a Carl Pomerance, " Primality Testing with Gaussian Periods Archived 28. dubna 2021 na Wayback Machine ", předběžná verze 20. července 2005.
↑ 1 2 H. W. Lenstra Jr. a Carl Pomerance, „ Testování primality s gaussovskými periodami , archivováno 25. února 2012 na Wayback Machine “, verze z 12. dubna 2011.
↑ 1 2 Barash, 2005 .
↑ 1 2 3 4 5 6 Cao, Liu, 2014 .
↑ 12 Menon , 2007 , s. 10-11.
↑ 1 2 3 4 Salembier, Southerington, 2005 .
↑ 1 2 Agrawal, Kayal, Saxena, 2004 , str. 5.

Literatura

Barash L. Yu. Algoritmus AKS pro kontrolu primality čísel a hledání konstant generátorů pseudonáhodných čísel // Bezpečnost informačních technologií. - 2005. - č. 2 . - S. 27-38 . Archivováno z originálu 18. října 2014.
Agafonova IV Kontrola čísel pro jednoduchost: polynomiální algoritmus // Seminář o diskrétní harmonické analýze a geometrickém modelování. — 2009.

v angličtině

Agrawal M. , Kayal N. , Saxena N. PRIMES je v P // Ann . Matematika. / J. Bourgain - Princeton University , 2004. - Sv. 160, Iss. 2. - S. 781-793. — ISSN 0003-486X ; 1939-8980 - doi:10.4007/ANNALS.2004.160.781
R. Crandall, Apple ACG, J. Papadopoulos, O implementaci testů primality třídy AKS , 2003.
Salembier R. G. , Southerington P. An Implementation of the AKS Primality Test - 2005. - porovnání implementací původního algoritmu a Lenstrova algoritmu pomocí různých knihoven.
Zhengjun Cao, Lihua Liu. Poznámky k algoritmu testování primality AKS a chyba v definici P . - 2014. - arXiv : 1402.0146v1 .
Granville A. Je snadné určit, zda je dané celé číslo prvočíslo // Bull . , New Ser., Am. Matematika. soc. / S. Friedlander - Providence, RI : American Mathematical Society , 2005. - Vol. 42, Iss. 1. - S. 3-38. — ISSN 0273-0979 ; 1088-9485 – doi:10.1090/S0273-0979-04-01037-7
Agrawal, M. a Kayal, N. a Saxena, N. Polynomiální časově deterministická metoda pro testování prvočíselnosti čísel . Patent US 20050027764A1 . Staženo: 15. prosince 2013.
Rotella C. Efektivní implementace algoritmu aks polynomial-time dokazování primality . — Pittsburgh, Pennsylvania, USA: School of Computer Science-Carnegie Mellon University, 2005.
Vidžaj Menon. Deterministické testování primality - porozumění algoritmu AKS // CoRR . - 2007. - Sv. abs/1311,3785 .

Odkazy

Weisstein, Eric W. AKS Primality Test (anglicky) na webu Wolfram MathWorld . – stručné informace o testu AKS
Phil Carmody. Zdroj algoritmu AKS "PRIMES in P" . Získáno: 19. října 2014. - recenze materiálů o algoritmu
Li, H. Analýza a implementace algoritmu AKS a jeho vylepšení . — 2013.
Pedro Berrizbetia. Ostření "Primes is in P" pro velkou rodinu čísel. (anglicky) . — 2011.

Číselné teoretické algoritmy
Testy jednoduchosti	Mlynář Miller - Rabin Luca - Lemaire pepina Agravala - Kayala - Sasko Slavík - Strassen
Hledání prvočísel	Iterace přes dělitele Eratosthenovo síto Atkinovo síto Síto Sundarama
Faktorizace	Iterace přes dělitele Fermatova metoda p −1 Pollardova metoda Pollardův ρ-algoritmus Lehmannova metoda Metoda eliptické křivky (Lenstrův algoritmus) Dixonův algoritmus Čtvercové síto
Diskrétní logaritmus	Gelfond-Shanksův algoritmus Polig-Hellmanův algoritmus Pollardova ρ-metoda Pollardův algoritmus klokana Adlemanův algoritmus COS algoritmus
Hledání GCD	Euklidův algoritmus Pokročilý algoritmus Binární algoritmus
Modulová aritmetika	Montgomeryho algoritmus Čínská věta o zbytku
Násobení a dělení čísel	Algoritmus Karatsuba Toom-Cookův algoritmus Schönhage-Strassenův algoritmus Fuhrerův algoritmus Algoritmus Harvey-van der Hoeven Burnickel-Zieglerův algoritmus
Výpočet druhé odmocniny	Tonelli-Shanksův algoritmus Algoritmus Berlekamp-Rabin