AKS asallık testi

AKS asallık testi (olarak da bilinen Agrawal-Kayal-Saxena asallık testi ve AKS cyclotomic testi ) bir olduğunu deterministik ve kültürlü asallık geçirmez algoritması yayınlanan (tüm numaralar için işleri)6 Ağu 2002Manindra Agrawal , Neeraj Kayal ve Nitin Saxena (AKS) adlı üç Hintli bilim adamı tarafından . Bu test, polinom zamandaki bir sayının asallığını ilk belirleyebilen testtir . Bu test, "PRIMES is in P" başlıklı bilimsel bir makalede yayınlandı . Bu makale onlara prestijli 2006 Gödel Ödülü'nü kazandırdı .

Algoritma

Prensip

Algoritma, bir sayının asal mı yoksa bileşik mi olduğunu belirler (çarpanlara ayırma anlamında).

Algoritma, Fermat'ın küçük teoreminin aşağıdaki genellemesine dayanmaktadır  : herhangi bir n ≥ 2 tamsayısı ve n ile bir asal sayı için ,

n bir asal sayıdır ancak ve ancak(X+-de)değil≡Xdeğil+-demoddeğil,{\ displaystyle (X + a) ^ {n} \ eşdeğeri X ^ {n} + a \ mod n,}

bu , iki terimli katsayıların bir özelliğinden kaynaklanır  :

n bir asal sayıdır ancak ve ancak∀k∈{1,...,değil-1},(değilk)≡0moddeğil.{\ displaystyle \ forall k \ in \ {1, \ ldots, n-1 \}, {n \ k seç} \ equiv 0 \ mod n.}

AKS'nin amacı bu özelliği verimli bir şekilde kullanmaktır.

Operasyon

Algoritma genel olarak şu şekildedir:

procédure AKS(n{\displaystyle n}): Si n=ab{\displaystyle n=a^{b}} avec a,b∈N{\displaystyle a,b\in \mathbb {N} } et b>1{\displaystyle b>1} alors renvoyer non-premier Construire le plus petit entier r{\displaystyle r} tel que l'ordre de n{\displaystyle n} modulo r{\displaystyle r} soit supérieur à 4log2⁡n{\displaystyle 4\log ^{2}n} Si pgcd(a,n{\displaystyle a,n}) != 1 pour un certain a≤r{\displaystyle a\leq r} alors renvoyer non-premier Si n≤r{\displaystyle n\leq r} alors renvoyer premier Pour a{\displaystyle a} compris entre 1 et ⌊2φ(r)log⁡n⌋{\displaystyle \left\lfloor 2{\sqrt {\varphi (r)}}\log n\right\rfloor } faire: Si (X+a)n≢Xn+amod(Xr−1)Z/nZ[X]{\displaystyle (X+a)^{n}\not \equiv X^{n}+a\mod (X^{r}-1)\mathbb {Z} /n\mathbb {Z} [X]} alors renvoyer non-premier Renvoyer premier

Kanıt

Karmaşıklık

Orijinal zaman karmaşıklığı içindedir . Algoritmanın karmaşıklığını etkileyen çeşitli varyasyonları ve iyileştirmeleri vardır. Önceki bölümde açıklanan versiyon karmaşıklığa , yani girişin boyutunda polinom karmaşıklığına sahiptir. AKS'nin karmaşıklığı, çeşitli varsayımların durumundan da etkilenir . Ö{\ displaystyle O}(günlük12⁡değil){\ displaystyle (\ log ^ {12} n)}Ö(günlük10,5⁡değil){\ displaystyle O (\ log ^ {10,5} n)}

Çeşitli varsayımların sonuçları

• Eğer ilk köklerinde Artin 'tahmin doğru, daha sonra AKS algoritması düzeyinde bir karmaşıklığa sahiptir ;Ö(günlük6⁡değil){\ displaystyle O (\ log ^ {6} n)}
• Eğer varsayım Agrawal  (in) doğrudur, o zaman AKS karmaşıklığı hakkındadır .Ö(günlük3⁡değil){\ displaystyle O (\ log ^ {3} n)}

Diğer asallık testleriyle karşılaştırma

AKS algoritması, test edilecek sayının basamak sayısında polinom zamanında çalışan ilk genel asallık testi değildir . Bununla birlikte, önceki tüm genel asallık ispat algoritmalarından bir anahtar farkı vardır: Doğruluk için kanıtlanmamış bir hipoteze ( Riemann hipotezi gibi ) ve tüm girdileri için kanıtlanabilir bir polinom zamanına sahip değildir. Ek olarak, deterministik bir algoritmadır  : olasılık testlerinin aksine, bir sayının asal olup olmadığını (tıpkı Eratosthenes'in eleği gibi) kesin olarak belirlemeyi mümkün kılar , bu da yalnızca bir sayının olası bir asal olup olmadığını belirlemeyi mümkün kılar. Olumlu olduğu zaman verilen cevapta aslında belirli bir hata olasılığına sahip olan sayıdır .

Varyantlar

Keşiften birkaç ay sonra birçok varyant ortaya çıktı: Lenstra 2002, Pomerance 2002, Berrizbeitia 2003, Cheng 2003, Bernstein 2003a / b, Lenstra ve Pomerance 2003 . AKS algoritmasının yürütme hızını farklı boyutlarda geliştirdiler. Algoritmanın bu çoklu varyantlarına, 2003 yılında Crandall ve Papadopoulos tarafından sunulan "AKS sınıfı" kavramı altında atıfta bulunulmaktadır.

Ayrıca görün

İlgili Makaleler

• Eratosthenes Kalburu  : MÖ 3. yüzyılın asallık testi. J.-C.
• Fermat asallık  testi: Basit olasılık testi.
• Solovay-Strassen asallık testi  : Koşulsuz olasılık testi.
• Miller-Rabin asallık  testi: Genelleştirilmiş Riemann hipotezini varsayan GL Miller'ın deterministik testine dayanan koşulsuz olasılık testi .
• Lucas-Lehmer asallık testi  : Genel değildir, belirli sayıların asallığını test etmeye izin verir.
• Conjecture Agrawal  (en)

Dış bağlantılar

• TrigoFacile.com  : Algoritmanın eksiksiz ve ayrıntılı sunumu ve gösterimi. [PDF]
• (tr) Eric W. Weisstein , "  AKS Primality Test  " , MathWorld'de
• (tr) PRIMES Is in P: A Breakthrough for “Everyman”  : Folkmar Bornemann'ın Notices of the American Mathematical Society'de üç Hintli bilim insanı tarafından yayınlanan keşif üzerine yazdığı makale . [PDF]

Notlar ve referanslar

(fr) Bu makale kısmen veya tamamen alınır İngilizce Vikipedi başlıklı makalesinde "  AKS asallık testi  " ( yazarların listesini görmek ) .

Notlar

1. Harf , Euler'in gösterge işlevini belirtir .φ{\ displaystyle \ varphi}
2. Bir sayıdaki hane sayısı sırasına göre değişir .değil{\ displaystyle n}günlük⁡değil{\ displaystyle \ log n}

Referanslar

1. PRIMES, P'de [PDF]  : özellikle yazarlarından biri tarafından kendi sayfasında alıntılanan orijinal makale .
2. “Kesin” hakemli makale 2004'te yayınlandı: Manindra Agrawal , Neeraj Kayal ve Nitin Saxena , “  PRIMES is in P  ”, Annals of Mathematics . İkinci Seri , cilt.  160, n o  22004, s.  781-793 ( DOI  10.4007 / annals.2004.160.781 , Matematik İncelemeleri  MR2123939 , zbMATH  02157791 , çevrimiçi okuyun )
3. 2006 Gödel Ödülü sayfası
4. Pascal Boyer, Sayıların ve uygulamalarının küçük arkadaşı , Paris, Calvage ve Mounet,2019, 648  s. ( ISBN  978-2-916352-75-6 ) , II. Asal sayılar, böl.  3.4. ("AKS"), s.  212-213.
5. (en) AKS sınıfı asallık testlerinin uygulanması hakkında [PDF]  : R. Crandall ve J. Papadopoulos, 18 Mart 2003

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">