Primeca provo AKS

La primeca provo AKS aŭ primeca provo de Agrawal-Kayal-Saxena estas determinisma algoritmo de primeca provo. Ĝ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ŭ komponigita 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].

GravecoRedakti

La signifeco de AKS estas en tio ke ĝi estas la unua publikigita algoritmo de primeca provo 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 primecaj provoj estas povas labori nur por nombroj kun certaj propraĵoj. La primeca provo de Lucas-Lehmer laboras nur por nombroj de Mersenne kaj provo 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. Elipsa kurba primeca provo kaj primeca provo de Adleman-Pomerance-Rumely povas pruvi ke ĉiu donita nombro estas primo aŭ komponigita, 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ŭ komponigita. Hazardigitaj testoj, ekzemple primeca provo de Miller-Rabin kaj primeca provo de Solovay-Strassen povas provi 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 primeca provo 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 provoRedakti

La primeca provo AKS estas bazita sur la ekvivalenteco (kongrueca rilato en modula aritmetiko)

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

por a interprima al 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 primeca provo en sin, kontrolo de ĝi prenas eksponenta funkcia tempo. 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 komponigitaj 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 provo de primeco 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 komponigita.

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 komponigita.

ReferencojRedakti

↑ 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 ligilojRedakti

[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]