Primeca provo AKS

El Vikipedio, la libera enciklopedio
Saltu al: navigado, serĉo

La primeca provo AKSprimeca 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 primokomponigita 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 [2].

Graveco[redakti | redakti fonton]

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.

Bazo de la provo[redakti | redakti fonton]

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:

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 \le 2 \sqrt{r} \log_{2}(n)

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

Referencoj[redakti | redakti fonton]

  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]

Eksteraj ligiloj[redakti | redakti fonton]