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 Manindra Agrawal, Neeraj Kayal kaj Nitin Saxena, "Primoj estas en P", Analoj de Matematiko 160 (2004), ne. 2, pp. 781–793. 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(b12+ε), 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 Carl Pomerance kaj Hendrik W. Lenstra.

 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)

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 : 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

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,


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 , en ĉiu okazo testante ekvivalentecon de du polinomoj en la kampo: se

por ĉiuj pozitivaj entjeroj a tiaj ke

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

 Referencoj 

 Eksteraj ligiloj 

 R. Crandall, Apple ACG, kaj J. Papadopoulos (18-a de marto, 2003): Pri realigo de AKS-klasaj primeco-testoj 
 Artikolo de Borneman kun fotoj kaj informo pri kreintoj de AKS 
 Andrew Granville: Estas facile ekscii ĉu donita entjero estas primo
 La primaj faktoj: de Eŭklido al AKS, de Scott Aaronson
 La Primoj estas en P, malgranda respondaro de Anton Stiglic
 Citaĵo de premio de Gödel de 2006
 Citaĵo de premio de Fulkerson de 2006 

Kategorio:Primeco-testoj
Kategorio:Modula aritmetiko