AKS test primality - AKS primality test

Test primality AKS (také známý jako test primarity Agrawal – Kayal – Saxena a cyklotomický test AKS ) je deterministický algoritmus prokazující primalitu vytvořený a publikovaný Manindrou Agrawalem , Neerajem Kayalem a Nitinem Saxenou , počítačovými vědci z Indického technologického institutu Kanpur , 6. srpna 2002, v článku s názvem „PRIMES je v P“. Algoritmus byl první, který dokázal prokazatelně určit, zda je dané číslo v polynomiálním čase prvočíselné nebo složené , aniž by se spoléhalo na matematické dohady , jako je zobecněná Riemannova hypotéza . Důkaz je také pozoruhodný tím, že se nespoléhá na oblast analýzy . V roce 2006 obdržel autoři oba Cenu Gödel a fulkersonova cena za jejich práci.

Důležitost

AKS je první algoritmus prokazující primalitu, který je současně obecný , polynomický , deterministický a bezpodmínečný . Předchozí algoritmy byly vyvíjeny po staletí a dosahovaly maximálně tří z těchto vlastností, ale ne všech čtyř.

Algoritmus AKS lze použít k ověření primality jakéhokoli obecného čísla. Je známo mnoho rychlých testů primality, které fungují pouze pro čísla s určitými vlastnostmi. Například test Lucas – Lehmer funguje pouze pro čísla Mersenne , zatímco Pépinův test lze použít pouze pro čísla Fermat .
Maximální doba běhu algoritmu může být vyjádřena jako polynom přes počet číslic v cílovém čísle. ECPP a APR přesvědčivě dokazují nebo vyvracejí, že dané číslo je prvočíslo, ale není známo, že by měly polynomické časové limity pro všechny vstupy.
Algoritmus zaručeně deterministicky rozlišuje, zda je cílové číslo primární nebo složené. Randomizované testy, jako jsou Miller – Rabin a Baillie – PSW , mohou testovat libovolné dané číslo na primalitu v polynomiálním čase, ale je známo, že produkují pouze pravděpodobnostní výsledek.
Správnost AKS není podmíněna žádnou dceřinou neprokázanou hypotézou . Naproti tomu Millerova verze Miller-Rabinova testu je plně deterministická a probíhá v polynomiálním čase na všech vstupech, ale jeho správnost závisí na pravdivosti dosud neprokázané generalizované Riemannovy hypotézy .

Přestože má tento algoritmus obrovský teoretický význam, v praxi se nepoužívá, což z něj činí galaktický algoritmus . U 64bitových vstupů je test primality Baillie – PSW deterministický a běží o mnoho řádů rychleji. U větších vstupů je výkon (také bezpodmínečně správných) testů ECPP a APR mnohem lepší než AKS. Navíc ECPP může vydávat osvědčení primality , který umožňuje nezávislé a rychlé ověření výsledků, což není možné u algoritmu AKS.

Pojmy

Test primality AKS je založen na následující větě: Vzhledem k tomu, že celočíselné a celočíselné coprime je , je primární právě tehdy, pokud je vztah polynomické kongruence ${\ Displaystyle n \ geq 2}$ ${\ displaystyle a}$ ${\ displaystyle n}$ ${\ displaystyle n}$

{\ Displaystyle (X+a)^{n} \ equiv X^{n}+a {\ pmod {n}}}

( 1 )

drží v polynomiálním kruhu . Všimněte si, že označuje neurčitý, který generuje tento polynomiální kruh. ${\ Displaystyle \ mathbb {Z} _ {n} [X]}$ ${\ displaystyle X}$

Tato věta je zobecněním polynomů Fermatovy malé věty . V jednom směru to lze snadno dokázat pomocí binomické věty společně s následující vlastností binomického koeficientu :

{\ displaystyle {n \ choose k} \ equiv 0 {\ pmod {n}}}

pro všechny, pokud je primární.

{\ Displaystyle 0 <k <n}

{\ displaystyle n}

Zatímco vztah ( 1 ) představuje test primality sám o sobě, jeho ověření vyžaduje exponenciální čas : přístup hrubou silou by vyžadoval expanzi polynomu a redukci výsledných koeficientů. ${\ displaystyle (X+a)^{n}}$ ${\ displaystyle {\ pmod {n}}}$ ${\ displaystyle n+1}$

Shoda je rovnost v polynomiálním kruhu . Vyhodnocení v kvocientovém kruhu vytvoří horní hranici pro stupeň zahrnutých polynomů. AKS vyhodnotí rovnost v , takže složitost výpočtu závisí na velikosti . Pro srozumitelnost je to vyjádřeno jako shoda ${\ Displaystyle \ mathbb {Z} _ {n} [X]}$ ${\ Displaystyle \ mathbb {Z} _ {n} [X]}$ ${\ Displaystyle \ mathbb {Z} _ {n} [X]/(X^{r} -1)}$ ${\ displaystyle r}$

{\ Displaystyle (X+a)^{n} \ equiv (X^{n}+a) {\ pmod {X^{r} -1, n}}}

( 2 )

což je stejné jako:

{\ Displaystyle (X+a)^{n}-(X^{n}+a) = (X^{r} -1) g+nf}

( 3 )

u některých polynomů a . ${\ displaystyle f}$ ${\ displaystyle g}$

Všimněte si, že všechny prvočísla splňují tento vztah (výběr v ( 3 ) dává ( 1 ), který platí pro prvočíslo). Tuto shodu lze zkontrolovat v polynomiálním čase, kdy je polynomický vůči číslicím . Algoritmus AKS vyhodnotí tuto shodu pro velkou sadu hodnot, jejichž velikost je polynomiální k číslicím . Důkaz platnosti algoritmu AKS ukazuje, že je možné najít a sadu hodnot s výše uvedenými vlastnostmi tak, že pokud kongruence platí, pak je to síla prvočísla. ${\ displaystyle g = 0}$ ${\ displaystyle n}$ ${\ displaystyle r}$ ${\ displaystyle n}$ ${\ displaystyle a}$ ${\ displaystyle n}$ ${\ displaystyle r}$ ${\ displaystyle a}$ ${\ displaystyle n}$

Historie a doba běhu

V první verzi výše citovaného článku autoři dokázali, že asymptotická časová složitost algoritmu je (pomocí Õ z velké O notace )-dvanáctá mocnina počtu číslic v n násobku polylogaritmického faktoru počet číslic. Tato horní hranice však byla poněkud volná; široce rozšířené dohady o distribuci prvočísel Sophie Germainové by v případě pravdy okamžitě omezily nejhorší případ . ${\ displaystyle {\ tilde {O}} (\ log (n)^{12})}$ ${\ displaystyle {\ tilde {O}} (\ log (n)^{6})}$

V měsících následujících po objevu se objevily nové varianty (Lenstra 2002, Pomerance 2002, Berrizbeitia 2002, Cheng 2003, Bernstein 2003a/b, Lenstra a Pomerance 2003), které výrazně zlepšily rychlost výpočtu. Vzhledem k existenci mnoha variant odkazují Crandall a Papadopoulos na „třídu AKS“ algoritmů ve své vědecké práci „O implementaci testů primality třídy AKS“, publikované v březnu 2003.

V reakci na některé z těchto variant a na další zpětnou vazbu byl článek „PRIMES is in P“ aktualizován o novou formulaci algoritmu AKS a jeho důkaz správnosti. (Tato verze byla nakonec publikována v Annals of Mathematics .) Přestože základní myšlenka zůstala stejná, r bylo vybráno novým způsobem a důkaz správnosti byl koherentněji organizován. Nový důkaz se téměř výhradně opíral o chování cyklotomických polynomů nad konečnými poli . Nová horní hranice časové složitosti byla později snížena pomocí dalších výsledků z teorie sít na . ${\ displaystyle {\ tilde {O}} (\ log (n)^{10.5})}$ ${\ displaystyle {\ tilde {O}} (\ log (n)^{7.5})}$

V roce 2005 Pomerance a Lenstra předvedli variantu AKS, která běží v operacích, což vedlo k další aktualizované verzi papíru. Agrawal, Kayal a Saxena navrhli variantu, která by se objevila, kdyby byly Agrawalovy dohady pravdivé; heuristický argument Pomerance a Lenstra však naznačoval, že je pravděpodobně nepravdivý. ${\ displaystyle {\ tilde {O}} (\ log (n)^{6})}$ ${\ displaystyle {\ tilde {O}} (\ log (n)^{3})}$

Algoritmus

Algoritmus je následující:

Vstup: celé číslo

n > 1

.

Zkontrolujte, zda n je dokonalá mocnina : pokud $n = a b$ pro celá čísla $a > 1$ a $b > 1$ , výstup složený .
Najděte nejmenší r tak, aby $ord r (n)> (log 2 n) 2$ . (pokud r a n nejsou coprime, pak toto r přeskočte )
U všech 2 ≤ a ≤ min ( r , n −1) zkontrolujte, zda a nedělí n : Pokud a | n pro nějaké 2 ≤ a ≤ min ( r , n −1), výstupní kompozit .
Pokud n ≤ r , výstup primární .
Pro $= 1$ až dělat ${\ Displaystyle \ left \ lfloor {\ sqrt {\ varphi (r)}} \ log _ {2} (n) \ right \ rfloor}$
pokud ( X + a ) ⁿ ≠ X ⁿ + a (mod X ^r - 1, n ), výstupní složený ;
Výstup primární .

Zde ord _r ( n ) je multiplikativní pořadí z n modulo r , log ₂ je binární logaritmus , a je Eulerova totient funkce z r . ${\ Displaystyle \ varphi (r)}$

Krok 3 je v papíru uveden jako kontrola 1 <( a , n ) < n pro všechna a ≤ r . Je vidět, že je to ekvivalentní zkušebnímu dělení do r , které lze provést velmi efektivně bez použití gcd . Podobně porovnání v kroku 4 lze nahradit tím, že má zkušební divize zpáteční prime jakmile bude kontrolovat všechny hodnoty až do ${\ Displaystyle \ left \ lfloor {\ sqrt {n}} \ right \ rfloor.}$

Krok za velmi malými vstupy ovládá čas 5. Zásadního snížení složitosti (z exponenciálního na polynom) je dosaženo provedením všech výpočtů v konečném prstenci

{\ Displaystyle R: = {\ Bigl (} {\ bigl (} \ mathbb {Z} /(n) {\ bigr)} [X] {\ Bigr)} {\ Bigl /} (X^{r} \ ! \!-\! \! 1) {\ Bigr.}}

skládající se z prvků. Tento prstenec obsahuje pouze monomialy a koeficienty jsou ve kterých má všechny prvky kódovatelné v bitech. ${\ Displaystyle n \ cdot r}$ ${\ displaystyle r}$ ${\ Displaystyle \ {X^{0}, X^{1}, \ ldots, X^{r-1} \}}$ ${\ Displaystyle \ mathbb {Z} /(n) =: \ mathbb {Z} _ {n}}$ ${\ displaystyle n}$ ${\ displaystyle \ log _ {2} (n)}$

Většina pozdějších vylepšení algoritmu se soustředila na zmenšení velikosti r, což činí operaci jádra v kroku 5 rychlejší, a na zmenšení velikosti s počet smyček provedených v kroku 5. Obvykle tyto změny nemění výpočet složitost, ale může vést k tomu, že mnoho řádů zabere méně času, např. Bernsteinova konečná verze má teoretické zrychlení více než 2 miliony.

Osvědčení o platnosti

Aby byl algoritmus správný, musí být správné všechny kroky, které identifikují n . Kroky 1, 3 a 4 jsou triviálně správné, protože jsou založeny na přímých testech dělitelnosti n . Krok 5 je také správné: od (2) platí pro jakoukoliv volbu a coprime k n a r , jestliže n je prvočíslo, nerovnost znamená, že n musí být kompozitní.

Obtížným případem algoritmu je iterované tvrzení v kroku 5. Pokud toto v konečném prstenci R náhodou způsobí nesoulad

{\ Displaystyle u \ not \ equiv v \; {\ bigl (} {\ text {mod}} (X^{r} \! \!-\! \! 1), n ​​{\ bigr)}}

toto je ekvivalentní

{\ Displaystyle u \ equiv v \; {\ bigl (} {\ text {mod}} (X^{r} \! \!-\! \! 1) {\ bigr)} \ quad \ implikuje \ quad u \ not \ equiv v \; ({\ text {mod}} n)}

,

takže po redukci na r monomial pomocí pouze musí být zkontrolováno. ${\ displaystyle {\ text {mod}} (X^{r} \! \!-\! \! 1)}$ ${\ Displaystyle u \ not \ equiv v \; ({\ text {mod}} n)}$

Příklad 1: n = 31 je prvočíslo

Vstup: celé číslo n = 31> 1.

  If n = a^b for integers a > 1 and b > 1, output composite.
    For [ b=2, b <= log₂(n), b++,
      a=n^1/b;
      If [ a is integer, Return[Composite]]
    ];
    a=n^1/2...n^1/4={5.568, 3.141, 2.360}

  Find the smallest r such that O_r(n) > (log₂ n)².
    maxk=⌊(log₂ n)²⌋;
    maxr=Max[3, ⌈(Log₂ n)⁵⌉]; (*maxr really isn't needed*)
    nextR=True;
    For [r=2, nextR && r < maxr, r++,
      nextR=False;
      For [k=1,(!nextR) &&k ≤ maxk, k++,
        nextR=(Mod[n^k, r]==1 || Mod[n^k, r]==0)
      ]
    ];
    r--; (*the loop over increments by one*)
     
    r = 29

  If 1 < gcd(a,n) < n for some a ≤ r, output composite.
    For [a=r, a > 1, a--,
      If [(gcd=GCD[a,n]) > 1 && gcd < n, Return[Composite]]
    ];
     
    gcd={GCD(29,31)=1, GCD(28,31)=1, ..., GCD(2,31)=1} ≯ 1

  If n ≤ r, output prime.
    If [n ≤ r, Return[Prime]]; (* this step may be omitted if n > 5690034 *)
     
    31 > 29

  For a = 1 to  $\left\lfloor {\sqrt {\varphi (r)}}\log _{2}(n)\right\rfloor$  do
    if (X+a)ⁿ≠ Xⁿ+a (mod X^r − 1,n), output composite;
     
    φ[x_]:=EulerPhi[x];
    PolyModulo[f_]:=PolynomialMod[ PolynomialRemainder[f,x^r-1,x],n];
    max=Floor[Log[2,n]√φ[r]];
    For[a=1, a ≤ max, a++,
      If[PolyModulo[(x+a)ⁿ-PolynomialRemainder[xⁿ+a, x^r-1], x]≠0,
        Return[Composite]
      ]
    ];
     
    (x+a)³¹ =
      a³¹ +31a³⁰x +465a²⁹x² +4495a²⁸x³ +31465a²⁷x⁴ +169911a²⁶x⁵ +736281a²⁵x⁶ +2629575a²⁴x⁷ +7888725a²³x⁸ +20160075a²²x⁹ +44352165a²¹x¹⁰ +84672315a²⁰x¹¹ +141120525a¹⁹x¹² +206253075a¹⁸x¹³ +265182525a¹⁷x¹⁴ +300540195a¹⁶x¹⁵ +300540195a¹⁵x¹⁶ +265182525a¹⁴x¹⁷ +206253075a¹³x¹⁸ +141120525a¹²x¹⁹ +84672315a¹¹x²⁰ +44352165a¹⁰x²¹ +20160075a⁹x²² +7888725a⁸x²³ +2629575a⁷x²⁴ +736281a⁶x²⁵ +169911a⁵x²⁶ +31465a⁴x²⁷ +4495a³x²⁸ +465a²x²⁹ +31ax³⁰ +x³¹
     
    PolynomialRemainder [(x+a)³¹, x²⁹-1] =
      465a² +a³¹ +(31a+31a³⁰)x +(1+465a²⁹)x² +4495a²⁸x³ +31465a²⁷x⁴ +169911a²⁶x⁵ +736281a²⁵x⁶ +2629575a²⁴x⁷ +7888725a²³x⁸ +20160075a²²x⁹ +44352165a²¹x¹⁰ +84672315a²⁰x¹¹ +141120525a¹⁹x¹² +206253075a¹⁸x¹³ +265182525a¹⁷x¹⁴ +300540195a¹⁶x¹⁵ +300540195a¹⁵x¹⁶ +265182525a¹⁴x¹⁷ +206253075a¹³x¹⁸ +141120525a¹²x¹⁹ +84672315a¹¹x²⁰ +44352165a¹⁰x²¹ +20160075a⁹x²² +7888725a⁸x²³ +2629575a⁷x²⁴ +736281a⁶x²⁵ +169911a⁵x²⁶ +31465a⁴x²⁷ +4495a³x²⁸
     
    (A) PolynomialMod [PolynomialRemainder [(x+a)³¹, x²⁹-1], 31] = a³¹+x²
     
    (B) PolynomialRemainder [x³¹+a, x²⁹-1] = a+x²
     
    (A) - (B) = a³¹+x² - (a+x²) = a³¹-a
     
    max =  $\left\lfloor \log _{2}(31){\sqrt {\varphi (29)}}\right\rfloor$  = 26
     
    {1³¹-1=0 (mod 31), 2³¹-2=0 (mod 31), 3³¹-3=0 (mod 31), ..., 26³¹-26=0 (mod 31)}

```
  Output prime.
    31 Must be Prime
```

Kde PolynomialMod je termínově modulo redukce polynomu. např. PolynomialMod [x +2x ² +3x ³ , 3] = x +2x ² +0x ³

Reference

Další čtení

Dietzfelbinger, Martin (2004). Testování primality v polynomiálním čase. Z randomizovaných algoritmů PRIMES je v P . Přednášky z informatiky. 3000 . Berlín: Springer-Verlag . ISBN 3-540-40344-2. Zbl 1058.11070 .

externí odkazy

Weisstein, Eric W. „Test prvenství AKS“ . MathWorld .
R. Crandall, Apple ACG a J. Papadopoulos (18. března 2003): O implementaci testů primality třídy AKS (PDF)
Článek Bornemana, obsahující fotografie a informace o třech indických vědcích (PDF)
Andrew Granville: Je snadné určit, zda je dané celé číslo prvočíslo
Hlavní fakta: Od Euclida po AKS , Scott Aaronson (PDF)
PRIMES je v P little FAQ od Anton Stiglic
2006 Citace Gödelovy ceny
2006 Citace Fulkersonovy ceny
Prostředek algoritmu AKS „PRIMES in P“
Grime, doktor James. „Fool -proof test pro prvočísla - Numberphile“ (video) . Brady Haran . [video popisuje exponenciální časový vztah (1), kterému se říká AKS]

Languages

In other projects