Back اختبار أ.ك.أس لأولية عدد ما Arabic AKS-Primzahltest German AKS primality test English Test de primalidad AKS Spanish آزمون اول بودن ایکیاس Persian Test de primalité AKS French מבחן AKS לראשוניות HE ए॰ के॰ ऐस॰ नंबर अभाज्यता टेस्ट Hindi Algoritmo AKS Italian AKS素数判定法 Japanese
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(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].
- ↑ 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