AKS asal sayı testi

AKS asal sayı testi (aynı zamanda Agrawal-Kayal-Saxena asal sayı testi ) deterministik olan algoritma belirler bir doğal sayı olduğu ana ya da içinde polinom çalışma süresi . Manindra Agrawal , Neeraj Kayal ve Nitin Saxena'nın geliştirdiği üç Hintli bilim insanı arasındaydı ve 2002'de PRIMES is in P (Almanca anlamında: Asıl sorun karmaşıklık sınıfı P'ye aittir) başlıklı bir makalede yayınlandı. 2006 yılında araştırmacılara çalışmaları için Gödel ve Fulkerson Ödülü verildi .

Daha sonra başkaları tarafından geliştirilen algoritma, daha önce bilinen tüm polinom asallik kanıtlama algoritmalarından önemli ölçüde farklıdır: uzunluğa bağlı olarak polinom çalışma süresinin ispatı için herhangi bir kanıtlanmamış hipotez (genelleştirilmiş Riemann Hipotezi gibi ) üzerine inşa edilmez. giriş değerlerinin . Asimtotik çalışma süresi orijinal algoritma olduğu yerlerde, test edilecek sayıdır, standları için Landau sembolü ve her türlü küçük pozitif sayı için. ${\ displaystyle {\ mathcal {O}} \ sol ((\ log n) ^ {7.5+ \ varepsilon} \ sağ)}$${\ displaystyle n}$${\ displaystyle {\ mathcal {O}}}$${\ displaystyle \ varepsilon}$

Menşe tarihi

1999'da Manindra Agrawal, doktora danışmanı Somenath Biswas ile polinomların eşitliğini göstermek için olasılıklı bir yöntem üzerinde çalıştı. Bundan, ikisi olasılıksal asal sayı testi için bir yöntem geliştirdi. Arkasındaki ve daha sonra faydalı olduğu ortaya çıkan fikir şu önermedir :

Be ve . O zaman, ancak ve ancak asaldır .$\ mathbb {Z} içinde {\ displaystyle a \, \ mathbb {N} içinde n \, n> 1}$${\ displaystyle \ mathrm {ggT} (a, n) = 1}$${\ displaystyle n}$${\ displaystyle (X + a) ^ {n} \ eşdeğeri X ^ {n} + a \; ({\ metni {mod}} n)}$

Orada bir belirsiz faktör oluşturur polinom halkası . Katsayıları arasında yer polinomların karşılaştırılacak şunlardır: olan bir değil asal sayı ancak ve ancak en küçük bölen eğer tatmin eşitsizlik ; ama o zaman bir tam sayı değildir ve geçerlidir ${\ displaystyle X}$ ${\ displaystyle \ mathbb {Z} [X]}$${\ displaystyle n}$${\ displaystyle a_ {i} (0 <i <n)}$${\ displaystyle X ^ {i}}$${\ displaystyle X}$${\ displaystyle n}$${\ displaystyle k}$${\ displaystyle 1 <k <n}$${\ displaystyle \ textstyle {{\ binom {n-1} {k-1}} / k}}$

${\ displaystyle {\ binom {n} {k}} \ equiv {\ binom {n-1} {k-1}} {\ frac {n} {k}} \ quad ({\ text {mod}} n )}$.

Ortaya çıkan asallık testi için mevcut olanlara ayak uyduramadığı düşünüldü. En kötü durumda, tüm katsayıları hesaplamanız gerekiyordu ki bu oldukça zaman alıcı olabilir. Bu nedenle, fikir başlangıçta daha fazla araştırılmadı.

2001'de öğrenciler Rajat Bhattarcharjee ve Prashant Pandey, lisans tezlerinde Primality Testing'de bu fikri yeniden ele aldılar . Polinomları hesaplama fikrini sadece modulo değil , aynı zamanda modulo (yani ) büyüklük sırasına göre bir tane için genişlettiler . Bu, polinom zamanda hesaplayabileceğiniz avantaja sahiptir . Şimdi bir asal sayı için bu uyumu sağladığı doğrudur , ancak artık asal sayı olmayan sayıları da tatmin ederler. ${\ displaystyle n}$${\ displaystyle X ^ {r} \! \! - \! \! 1}$${\ displaystyle {\ text {mod}} (X ^ {r} \! \! - \! \! 1, n)}$${\ displaystyle r}$${\ displaystyle \ log n}$${\ displaystyle (X + a) ^ {n} \; {\ text {mod}} \; (X ^ {r} \! \! - \! \! 1, n)}$${\ displaystyle n}$

İkili, bu uyumu kesin olarak ve koşulları belirlemek ve böylece bu uyuşmanın yalnızca asal sayılar için geçerli olmasını sağlamak için araştırdı . Bir dizi testten sonra, aşağıdaki varsayımı yaptılar (ayrıca bkz.Agrawal'ın Varsayımı ): ${\ displaystyle a}$${\ displaystyle r}$${\ displaystyle a}$${\ displaystyle r}$

Eğer ( asal sayılar kümesi) ve bölen değilse , ya asaldır ya da . ${\ displaystyle r \ in \ mathbb {P}}$${\ displaystyle \ mathbb {P}}$${\ displaystyle n}$${\ displaystyle (X + 1) ^ {n} \ eşdeğeri X ^ {n} +1 \; {\ bigl (} {\ text {mod}} (X ^ {r} \! \! - \! \! 1), n ​​{\ bigr)}}$${\ displaystyle n}$${\ displaystyle n ^ {2} \ eşdeğeri 1 \; ({\ metni {mod}} r)}$

2002 yılında iki öğrenci Neeraj Kayal ve Nitin Saxena lisans tezleri üzerinde çalıştılar. Öncülerinin düşüncelerini sürdürdüler. Riemann Hipotezinin doğru olduğunu varsayarsak , yukarıdaki teoremi ispatlayabildiler. Hafif bir önseziyle, daha sonra lisans tezlerini deterministik bir polinom-zaman asallık testine doğru çağırdılar .

Ardından Manindra Agrawal ile algoritmayı son haline getirdiler. Daha sonra yayınlanan yazı tipi çok popüler oldu. Doğruluk bir hafta içinde onaylandı ve web sitesi ilk hafta iki milyondan fazla ziyaretçiye sahipti.

Algoritma

Asallığı test etmek sayıdır . Dahası, doğal sayılar olsun. ${\ displaystyle n> 1}$${\ displaystyle a, b, r}$

1: if n = ab für ein b > 1 return ZUSAMMENGESETZT;
2: r = min{ r | ordr(n) > log(n)2 };
3: if 1 < ggT(a,n) < n für ein a ≤ r return ZUSAMMENGESETZT;
4: if n ≤ r return PRIM;
5: for a = 1 to sqrt(phi(r))*log(n) do
6:     if (X+a)n ≢ Xn+a (mod (Xr−1), n) return ZUSAMMENGESETZT;
7: return PRIM;

Açıklamalar

• ${\ displaystyle \ operatorname {min} \ {M \}}$(aşağı doğru kısıtlanmış) kümedeki en küçük öğeyi bulur .${\ displaystyle M}$
• ${\ displaystyle \ operatöradı {ord} _ {r} (n)}$bir düzen içinde ; en küçük sayıdır için de geçerlidir.${\ displaystyle n \; ({\ metni {mod}} r)}$${\ displaystyle k> 0}$${\ displaystyle n ^ {k} \ eşdeğeri 1 \; ({\ metni {mod}} r)}$
• ${\ displaystyle \ günlük (n): = \ log _ {2} (n)}$bir logaritma bir tabana 2.${\ displaystyle n}$
• ${\ displaystyle \ operatöradı {ggT} (a, n)}$olduğu büyük ortak böleni arasında ve .${\ displaystyle a}$${\ displaystyle n}$
• ${\ displaystyle \ operatöradı {sqrt} (X)}$hesaplar karekök içinde .${\ displaystyle X}$
• ${\ displaystyle \ operatöradı {phi} (r): = \ varphi (r)}$1'den : Euler'in Phi işlevi aralığındaki kopprime sayılarının sayısıdır .${\ displaystyle r}$${\ displaystyle r}$
• ${\ displaystyle X}$polinom halkasının tabanıdır ( belirsizdir ) .${\ displaystyle \ mathbb {Z} [X]}$
• İki kat oluşturulmuş yana doğru olan bir ana ideal olarak halka , bir polinomun bölünebilme incelenmelidir hem tarafından . Yani, uyumsuzluk     , ima ile eş anlamlıdır. ${\ displaystyle {\ bigl (} (X ^ {r} \! \! - \! \! 1), n ​​{\ bigr)}}$ ${\ displaystyle \ mathbb {Z} [X]}$${\ displaystyle \ eşit değil \ {\ bigl (} {\ text {mod}} (X ^ {r} \! \! - \! \! 1), n ​​{\ bigr)}}$${\ displaystyle X ^ {r} \! \! - \! \! 1}$${\ displaystyle n}$${\ displaystyle u \ değil \ eşit v \; {\ bigl (} {\ text {mod}} (X ^ {r} \! \! - \! \! 1), n ​​{\ bigr)}}$

  ${\ displaystyle u \ equiv v \; {\ bigl (} {\ text {mod}} (X ^ {r} \! \! - \! \! 1) {\ bigr)} \ quad \ şunu ifade eder \ quad u \ eşit değil \; ({\ text {mod}} n)}$.

• Aslında onaylandıktan sonra

  ${\ displaystyle \ forall r \ forall a \; \ kolon \; (X + a) ^ {n} \ eşdeğeri X ^ {n} + a \ quad {\ bigl (} {\ text {mod}} (X ^ {r} \! \! - \! \! 1), n ​​{\ bigr)}}$

(talimat dizisi 5, 6 ile) sadece 7 numaralı talimatta bu bir asal güçtür. Talimat nedeniyle 1 asal sayıdır.${\ displaystyle n}$${\ displaystyle n}$

Çalışma zamanı davranışı

Algoritma , elemanlarla sonlu halkada fiilen hesaplar . ${\ displaystyle {\ Bigl (} {\ bigl (} \ mathbb {Z} / (n) {\ bigr)} [X] {\ Bigr)} / (X ^ {r} \! \! - \! \ ! 1)}$${\ displaystyle n \ cdot r}$

Bağdaşım Uyum polinom halkada üs içinde miktarını azaltır elde edilen Monome ile . Anlaşmaya uygunluk , ortaya çıkan katsayının basamak sayısını sınırlar .${\ displaystyle \ eşdeğeri {\ bigl (} {\ text {mod}} (X ^ {r} \! \! - \! \! 1) {\ bigr)}}$${\ displaystyle \ mathbb {Z} [X]}$${\ displaystyle (X + a) ^ {n}}$${\ displaystyle \ {X ^ {0}, X ^ {1}, \ ldots, X ^ {r-1} \}}$${\ displaystyle \ eşdeğeri ({\ metin {mod}} n)}$${\ displaystyle \ log n.}$

Böylece belirlenmesi

${\ displaystyle (X + a) ^ {n} \ eşdeğeri X ^ {n} + a \ quad ({\ text {mod}} (X ^ {r} \! \! - \! \! 1), n )}$

tekrarlanan kare alma ile . İle hızlı Fourier çarpma , çaba içindedir . ${\ displaystyle {\ mathcal {O}} (r ^ {2} \ log ^ {3} n)}$${\ displaystyle {\ mathcal {O}} (r \ log ^ {2} n)}$

Agrawal'den sonra Kayal ve Saxena

Keşfi takip eden aylarda , AKS hızını büyük ölçüde artıran yeni varyantlar ( Lenstra 2002, Pomerance 2002, Berrizbeitia 2003, Cheng 2003, Bernstein 2003a / b, Lenstra ve Pomerance 2003) ortaya çıktı. Çok sayıda varyanttan dolayı Crandall ve Papadopoulos'un makalesinde konuşur AKS sınıfı asallık testlerinin uygulanması üzerine (dt .: AKS sınıfının ana testlerinin uygulanması hakkında ) Mart 2003'ten AKS yerine AKS algoritmaları sınıfı tarafından -Algoritma.

Lenstra ve Pomerance algoritması sona eriyor . Bununla birlikte, pratikte, AKS algoritmasının çalışma zamanı, parametre genellikle biraz yukarıda bulunabildiğinden , benzer bir büyüklük sırasına sahiptir . ${\ displaystyle {\ mathcal {O}} \ sol ((\ log n) ^ {6+ \ varepsilon} \ sağ)}$${\ displaystyle r}$${\ displaystyle \ log ^ {2} n}$

Agrawal, Kayal ve Saxena, yukarıdaki varsayımla benzer bir algoritma kurdu:

Önce ile birini arayın (böyle bir aralıkta ). Bu algoritma ile bir çalışma süresi elde edilir . Lenstra ve Pomerance, Remarks on Agrawal Conjecture'da bu varsayım için olası karşı örnekler bulmak için bir buluşsal yöntem verdiler. Ancak, varsayımlarında varsayılanlara benzer rakamlar olup olmadığı henüz bilinmemektedir. ${\ displaystyle r \ in \ mathbb {P}}$${\ displaystyle r \ nmid (n ^ {2} -1)}$${\ displaystyle r}$${\ displaystyle [2,4 \ log n]}$${\ displaystyle {\ mathcal {O}} \ sol ((\ log n) ^ {3+ \ varepsilon} \ sağ)}$

Edebiyat

• Volker Diekert, Manfred Kufleitner, Gerhard Rosenberger: Ayrık cebirsel yöntemler: aritmetik, kriptografi, otomata ve gruplar . De Gruyter, Berlin 2013, ISBN 978-3-11-031260-7 . 
• Martin Dietzfelbinger: Polinom zamanında asallık testi. Rastgele algoritmalardan "PRIMES is P in P" (=  Bilgisayar Bilimleri Ders Notları . No. 3000 ). Springer, Berlin 2004, ISBN 3-540-40344-2 . 

İnternet linkleri

• M. Agrawal, N. Kayal, N. Saxena: PRIMES, P.'de (PDF; 195 kB).
• Eric W. Weisstein : AKS Asallık Testi . In: MathWorld (İngilizce).
• R. Crandall, J. Papadopoulos: AKS-sınıfı asallık testlerinin uygulanması üzerine. ( Arasında Memento içinde 3 Nisan 2003 Internet Archive ). (PDF; 104 kB). 18 Mart 2003.
• O. Braun, S. Schönnenbeck: AKS asal sayı testi dersi 2009.
• Folkmar Bornemann: “Herkes” için bir dönüm noktası. (PDF; 487 kB). Üç Hintli araştırmacının fotoğraflarıyla AKS asallık testi hakkında makale.
• H. Lenstra, C. Pomerance: Agrawal Varsayımı Üzerine Açıklamalar.

Bireysel kanıt

1. ↑ Agrawal, Kayal, Saxena PRIMES P.
2. ↑ Manindra Agrawal, Neeraj Kayal ve Nitin Saxena: PRIMES P.
3. ^ DE Knuth. Bilgisayar Programlama Sanatı, Cilt II, Seminümerik Algoritmalar . Addison Wesley, 1998.