Primeco-testo AKS

La primeco-testo AKS aŭ primeco-testo de Agrawal-Kayal-Saxena estas determinisma algoritmo de primeco-testo. Ĝi estis kreita kaj publikigita de Manindra Agrawal, Neeraj Kayal kaj Nitin Saxena de barata instituto de teknologio Kanpur en la 6-a de aŭgusto, 2002 ^[1] La aŭtoroj ricevis multaj respektatestoj pro ĉi tiu laboro.

La algoritmo kontrolas ĉu nombro estas primo aŭ komponita en polinoma tempo de kvanto de ciferoj en la testata nombro. En la komenca varianto de la algoritmo, la tempo estas O((log n)^12+ε), kie n estas la testata nombro, aŭ O(b^12+ε), kie b estas la kvanto de ciferoj.

La algoritmo estis baldaŭ plibonigita de la aliaj. En 2005, Carl Pomerance kaj Hendrik W. Lenstra kreis varianton de AKS kiu ruliĝas en O((log n)^6+ε) operacioj, kio estas signifa plibonigo ^[2].

Graveco

La signifeco de AKS estas en tio ke ĝi estas la unua publikigita algoritmo de primeco-testo, kiu estas samtempe ĝenerala, polinoma, determinisma, kaj pruvita. Antaŭaj algoritmoj havas ne pli ol 3 propraĵojn el la 4.

La AKS algoritmo estas ĝenerala ĉar ĝi povas esti uzata por kontroli primecon por ĉiu donita nombro. Multaj rapidaj primeco-testoj estas povas labori nur por nombroj kun certaj propraĵoj. La primeco-testo de Lucas-Lehmer laboras nur por nombroj de Mersenne kaj testo de Pépin laboras nur por nombroj de Fermat.
La maksimuma rula tempo de la algoritmo estas polinoma de kvanto de ciferoj en la povata nombro. Elipso-kurba primeco-testo kaj primeco-testo de Adleman-Pomerance-Rumely povas pruvi ke ĉiu donita nombro estas primo aŭ komponita, sed ne estas sciataj polinomaj tempaj baroj por ili por ĉiuj enigoj.
La algoritmo estas determinisma ĉar ĝi garantias distingi ĉu la nombro estas primo aŭ komponita. Hazardigitaj testoj, ekzemple primeco-testo de Miller-Rabin kaj primeco-testo de Solovay-Strassen povas testi donitan nombron por primeco en polinoma tempo, sed produktas nur probablecan rezulton.
AKS estas pruvita ĉar ĝi ne baziĝas sur iu nepruvita hipotezo. En kontrasto, la primeco-testo de Miller-Rabin havas varianton kiu estas plene determinisma kaj ruliĝas en polinoma tempo por ĉiuj enigoj sed ĝia vereco dependas de vereco de ankoraŭ nepruvita ĝeneraligita Rimana hipotezo.

Bazo de la testo

La primeco-testo AKS estas bazita sur la ekvivalenteco (kongrueca rilato en modula aritmetiko)

(x-a)^{n}\equiv (x^{n}-a){\pmod {n}}

por a reciproke prima kun n, kiu estas vera se kaj nur se n estas primo. Ĉi tiu estas ĝeneraligo de malgranda teoremo de Fermat etendita al polinomoj kaj povas esti facile pruvita per la duterma teoremo kaj ankaŭ la fakto ke : ${n \choose k}\equiv 0{\pmod {n}}$ por ĉiuj 0 < k < n se n estas primo. Dum ĉi tiu ekvivalento konsistigas per si primeco-teston, kontrolo de ĝi prenas eksponentan tempon. Pro tio AKS uzas parencan ekvivalenton

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

kiu povas esti kontrolita en polinoma tempo. Ĉiuj primoj kontentigas ĉi tiu ekvivalento sed ankaŭ iuj komponitaj kontentigas ĝin. La pruvo de praveco de AKS konsistas el pruvo ke ekzistas konvene malgranda r kaj konvene malgranda aro de entjeroj A tiaj ke se la ekvivalento veras por ĉiuj a el A do n estas primo.

La algoritmo de primeco-testado de iu entjero n konsistas el du partoj. La unua ŝtupo trovas taŭgan primon r=kq+1, tian ke:

P(r-1)=q kie P(x) estas la plej granda prima faktoro de x,
$q\geq 4{\sqrt {r}}\log _{2}(n),$
$n^{k}\not \equiv 1{\pmod {r}}.$

Dum ĉi tiu ŝtupo, estas grave konfirmi ke n estas ne dividebla per ĉiu primo p tia ke p<r. Se ĝi estas dividebla do la algoritmo povas finiĝi tuj al raporti ke n estas komponita.

En la dua ŝtupo, iu kvanto de testoj estas farata en la finia kampo $GF(n^{r})$ , en ĉiu okazo testante ekvivalentecon de du polinomoj en la kampo: se

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

por ĉiuj pozitivaj entjeroj a tiaj ke

a\leq 2{\sqrt {r}}\log _{2}(n)

tiam n estas garantiita primo. En ĉiuj aliaj okazoj ĝi estas komponita.

Referencoj

↑ Manindra Agrawal, Neeraj Kayal kaj Nitin Saxena, "Primoj estas en P", Analoj de Matematiko 160 (2004), ne. 2, pp. 781–793.
↑ Carl Pomerance kaj Hendrik W. Lenstra

Eksteraj ligiloj

[1] Manindra Agrawal, Neeraj Kayal kaj Nitin Saxena, "Primoj estas en P", Analoj de Matematiko 160 (2004), ne. 2, pp. 781–793.

[2] Carl Pomerance kaj Hendrik W. Lenstra

[1]

[2]