AKS 素数判定

AKS素数判定（アグラワル・カヤル・サクセナ素数判定、円分AKS判定とも呼ばれる）は、インド工科大学カンプール校のコンピュータ科学者であるマニンドラ・アグラワル、ニーラジ・カヤル、ニティン・サクセナによって作成され、2002年8月6日に「PRIMES is in P」と題された論文で発表された決定論的素数証明アルゴリズムである。 ^{[1]このアルゴリズムは、}一般化リーマン予想などの数学的推測に頼ることなく、与えられた数が素数か合成数かを多項式時間で判定できる最初のアルゴリズムであった。また、この証明は解析学の分野に依存しないことでも注目に値する。^[2] 2006年、著者らは研究によりゲーデル賞とフルカーソン賞を受賞した。

重要性

AKS は、一般性、多項式時間、決定性、無条件に正しいという3 つの条件を同時に満たす最初の素数証明アルゴリズムです。これまでのアルゴリズムは何世紀にもわたって開発されてきましたが、これらの特性のうち最大 3 つしか実現できず、4 つすべてを実現することはできませんでした。

AKS アルゴリズムは、与えられた任意の一般的な数の素数性を検証するために使用できます。特定の特性を持つ数に対してのみ機能する、多くの高速素数性テストが知られています。たとえば、ルーカス・レーマーテストはメルセンヌ数に対してのみ機能し、ペパンテストはフェルマー数に対してのみ適用できます。
アルゴリズムの最大実行時間は、対象数値の桁数に対する多項式によって制限できます。ECPPとAPR は、特定の数値が素数であることを決定的に証明または反証しますが、すべての入力に対して多項式時間の制限があることは知られていません。
このアルゴリズムは、対象数が素数か合成数かを決定論的に区別することが保証されています。Miller –RabinやBaillie–PSWなどのランダム化テストは、任意の数の素数性を多項式時間でテストできますが、確率的な結果しか生成しないことが知られています。
AKS の正しさは、いかなる補助的な未証明の仮説にも条件付けられません。対照的に、ミラー版のミラー・ラビン検定は完全に決定論的であり、すべての入力に対して多項式時間で実行されますが、その正しさは、まだ証明されていない一般化リーマン予想の真偽に依存します。

このアルゴリズムは理論的には非常に重要であるが、実際には使用されていないため、銀河アルゴリズムとなっている。64 ビットの入力の場合、Baillie-PSW テストは決定論的であり、桁違いに高速に実行される。より大きな入力の場合、(これも無条件に正しい) ECPP テストと APR テストのパフォーマンスはAKS よりもはるかに優れている。さらに、ECPP は素数証明書を出力できるため、結果の独立した迅速な検証が可能だが、これは AKS アルゴリズムでは不可能である。

コンセプト

AKS素数判定は、次の定理に基づいています。と互いに素な整数が与えられたとき、多項式合同関係が成り立つ場合のみ、は素数となります。 $n\geq 2$ $a$ $n$ $n$

多項式環内では成り立つ。^{[1] は、}この多項式環を生成する不定値を表すことに注意すること。 $(\mathbb {Z} /n\mathbb {Z} )[X]$ $X$

この定理はフェルマーの小定理の多項式への一般化です。一方向では、二項定理と二項係数の次の性質を組み合わせて簡単に証明できます。

{n \choose k}\equiv 0{\pmod {n}}

が素数であればすべてに対して。

0<k<n

n

関係式（１）はそれ自体が素数判定を構成するが、それを検証するには指数関数的な時間がかかる。つまり、力ずくのアプローチでは多項式の展開と結果として得られる係数の削減が必要となる。 $(X+a)^{n}$ ${\pmod {n}}$ $n+1$

合同は多項式環における等式である。の商環を評価すると、関係する多項式の次数の上限が生成される。AKS はにおける等式を評価するため、計算の複雑さはのサイズに依存する。わかりやすくするために、^{[1] では}これを合同として表現する。 $(\mathbb {Z} /n\mathbb {Z} )[X]$ $(\mathbb {Z} /n\mathbb {Z} )[X]$ $(\mathbb {Z} /n\mathbb {Z} )[X]/(X^{r}-1)$ $r$

これは以下と同じです:

いくつかの多項式およびに対して。 $f$ $g$

すべての素数はこの関係式を満たすことに注意する（（3）でを選択すると（1）が得られ、これは素数に対して成り立つ）。この合同性は、がの桁の多項式である場合に多項式時間でチェックできる。AKSアルゴリズムは、の桁の多項式のサイズである大きな値のセットに対してこの合同性を評価する。AKSアルゴリズムの有効性の証明は、と上記の性質を持つ値のセットを見つけることができ、合同性が成り立つ場合は素数の累乗であることを示す。^[1] $g=0$ $n$ $r$ $n$ $a$ $n$ $r$ $a$ $n$

歴史と実行時間

上記の論文の最初のバージョンでは、著者らはアルゴリズムの漸近的時間計算量が(ビッグオー記法のÕ を使用)、つまりnの桁数の 12 乗に桁数の多重対数である因数を掛けたものであると証明しました。しかし、この上限はかなり緩いものでした。ソフィー・ジェルマン素数の分布に関する広く信じられている推測が真実であれば、最悪のケースはすぐにまで削減されます。 ${\tilde {O}}(\log(n)^{12})$ ${\tilde {O}}(\log(n)^{6})$

発見から数か月後には、新しい変種 (Lenstra 2002、Pomerance 2002、Berrizbeitia 2002、Cheng 2003、Bernstein 2003a/b、Lenstra と Pomerance 2003) が登場し、計算速度が大幅に向上しました。多くの変種が存在するため、Crandall と Papadopoulos は、2003 年 3 月に発表した科学論文「AKS クラスの素数性テストの実装について」で「AKS クラス」のアルゴリズムについて言及しています。

これらのバリエーションやその他のフィードバックに応えて、論文「PRIMES は P に属する」が更新され、AKS アルゴリズムとその正しさの証明が新たに定式化されました (このバージョンは最終的にAnnals of Mathematicsに掲載されました)。基本的な考え方は同じままですが、r は新しい方法で選択され、正しさの証明はより首尾一貫して構成されました。新しい証明は、有限体上の円分多項式の挙動にほぼ排他的に依存していました。時間計算量の新しい上限はでしたが、後にふるい理論からの追加の結果を使用してに削減されました。 ${\tilde {O}}(\log(n)^{10.5})$ ${\tilde {O}}(\log(n)^{7.5})$

2005年、ポメランスとレンストラはオペレーションで実行されるAKSの変種を実証し、 ^[3]論文の別の更新バージョンにつながりました。^{[4]アグラワル、カヤル、サクセナは、}アグラワルの予想が正しい場合に実行される変種を提案しましたが、ポメランスとレンストラによるヒューリスティックな議論は、それがおそらく誤りであることを示唆しました。 ${\tilde {O}}(\log(n)^{6})$ ${\tilde {O}}(\log(n)^{3})$

アルゴリズム

アルゴリズムは以下のとおりです。^[1]

入力: 整数

n > 1

。

n が完全累乗かどうかを確認します。整数 $a$ $> 1$ かつ $b$ $> 1に対して$ $n = a b$ の場合、合成数を出力します。
$ord$ $r$ $($ $n$ $) > (log$ $2$ $n$ $)$ $2$ となる最小のr を見つけます。rとnが互いに素でない場合は、合成数を出力します。
すべての 2 ≤ a ≤ min ( r , n −1 ) について、a がn を割り切れないことを確認します。いくつかの 2 ≤ a ≤ min ( r , n −1 ) についてa | nの場合、合成値を出力します。
n ≤ rの場合、primeを出力します。
$a =$ 1 の場合 $\left\lfloor {\sqrt {\varphi (r)}}\log _{2}(n)\right\rfloor$
( X + a ) ⁿ ≠ X ⁿ + a (mod X ^r − 1, n )の場合、合成値を出力します。
プライムを出力します。

ここで、ord _r ( n ) はr を法とするnの乗法順序、log ₂は二進対数、はrのオイラーのトーシェント関数です。 $\varphi (r)$

ステップ3は、論文では、すべてのa ≤ rについて1 < ( a , n ) < nをチェックするものとして示されています。これはrまでの試行除算と同等であり、 gcdを使用せずに非常に効率的に実行できることが分かります。同様に、ステップ4の比較は、試行除算がrまでのすべての値をチェックしたら素数を返すように置き換えることができます。 $\left\lfloor {\sqrt {n}}\right\rfloor .$

非常に小さな入力を超えると、ステップ5にかかる時間が支配的になります。複雑さの本質的な削減（指数から多項式へ）は、有限環ですべての計算を実行することで達成されます。

R=(\mathbb {Z} /n\mathbb {Z} )[X]/(X^{r}-1)

要素から成る。この環には単項式のみが含まれ、係数はであり、その要素はすべてビット内でコード化可能である。 $n^{r}$ $r$ $\{X^{0},X^{1},\ldots ,X^{r-1}\}$ $\mathbb {Z} /n\mathbb {Z}$ $n$ $\log_{2}(n)$

アルゴリズムに対するその後の改良のほとんどは、ステップ5のコア操作を高速化するrのサイズの縮小と、ステップ5で実行されるループの数であるsのサイズの縮小に集中しています。 ^[5] 通常、これらの変更によって計算の複雑さは変わりませんが、かかる時間が桁違いに短縮される可能性があります。たとえば、Bernsteinの最終バージョンでは、理論上200万倍以上の高速化が実現されています。

有効性証明の概要

アルゴリズムが正しいためには、n を識別するすべてのステップが正しくなければなりません。ステップ 1、3、および 4 は、nの割り切れるかどうかの直接的なテストに基づいているため、当然正しいです。ステップ 5 も正しいです。n が素数である場合、(2) はnとrと互いに素な任意の選択に対して真であるため、不等式は n が合成数でなければならないことを意味します。

証明の難しい部分は、ステップ 6 が正しいことを示すことです。その正しさの証明は、ステップ 5 でテストされる( X + a ) 二項式から構築されたの乗法群の上限と下限に基づいています。ステップ 4 は、これらの二項式がの異なる要素であることを保証します。rの特定の選択では、 n が素数または素数の累乗でない限り、境界は矛盾を生じます。ステップ 1 のテストと合わせて、これはステップ 6 でnが常に素数であることを意味します^。[1] $\mathbb {Z} _{n}[x]$ $\left\lfloor {\sqrt {\varphi (r)}}\log _{2}(n)\right\rfloor$ $\mathbb {Z} _{n}[x]$

例1:ん= 31は素数である

   入力: 整数n = 31 > 1。

   (* ステップ 1 *)
    (整数a > 1 かつb > 1 に対してn = a ^b )の場合、 
     合成値を出力します。
      (b = 2; b <= log _{2 (n); b++)}の場合{ 
       a = n ^1/b ;
        (a が整数) 
         の場合、 [合成]を返す
     }
     a = n ^1/2 ...n ^1/4 = {5.568, 3.141, 2.360}

   (* ステップ 2 *) O _r ( n ) > (log ₂ n ) ²となる
   最小のr を見つけます。 
     最大値k = ⌊(log ₂ n) ² ⌋;
     maxr = Max[3, ⌈(Log ₂ n) ⁵ ⌉]; (* maxr は実際には必要ありません *)
     次R = True;
     (r = 2; nextR && r < maxr; r++)の場合{
       nextR = False;
       For (k = 1; (!nextR) && k ≤ maxk; k++) {
         次のR = (Mod[n ^k , r] == 1 || Mod[n ^k , r]==0)
       }
     }
     r--; (*ループは1ずつ増加します*)
      
     r = 29

   (* ステップ 3 *)
    (1 < gcd ( a , n ) < nで、あるa ≤ rの場合)、 
     合成を出力します。For
      ( a = r; a > 1; a--) {
        If ((gcd = GCD[a,n]) > 1 && gcd < n)、 
          [Composite]を返します。 
     }
      
     gcd = {GCD(29,31)=1, GCD(28,31)=1, ..., GCD(2,31)=1} ≯ 1

   (* ステップ 4 *)
    ( n ≤ r )の場合、 
      primeを出力します。
      ( n ≤ r )の場合、 
        [Prime]を返します(* n > 5690034 の場合、このステップは省略できます *) 
      
     31 > 29
   
   (* ステップ 5 *) 
   a = 1の場合 、 (( X + a ) ⁿ ≠ X ⁿ + a (mod X ^r − 1, n )) 
       の場合、合成値を出力します。  $\left\lfloor {\sqrt {\varphi (r)}}\log _{2}(n)\right\rfloor$  
      
      
     φ[x_] := オイラーファイ[x];
     PolyModulo[f_] := PolynomialMod[ PolynomialRemainder [f, x ^r -1, x], n];
     max = Floor[Log[2, n] √ φ[r] ];
      For (a = 1; a ≤ max; a++) {
        If (PolyModulo[(x+a) ⁿ - PolynomialRemainder[x ⁿ +a, x ^r -1], x] ≠ 0) {
          Return [Composite]
       {
     }
      
     (x+a) ³¹ =
       a ³¹ +31a ³⁰ x +465a ²⁹ x ² +4495a ²⁸ x ³ +31465a ²⁷ x ⁴ +169911a ²⁶ x ⁵ +736281a ²⁵ x ⁶ +2629575a ²⁴ x ⁷ +7888725a ²³ x ⁸ +20160075a ²² x ⁹ +44352165a ²¹ x ¹⁰ +84672315a ²⁰ x ¹¹ +141120525a ¹⁹ x ¹² +206253075a ¹⁸ x ¹³ +265182525a ¹⁷ x ¹⁴ +300540195a ¹⁶ x ¹⁵ +300540195a ¹⁵ x ¹⁶ +265182525a ¹⁴ x ¹⁷ +206253075a ¹³ x ¹⁸ +141120525a ¹² x ¹⁹ +84672315a ¹¹ x ²⁰ +44352165a ¹⁰ x ²¹ +20160075a ⁹ x ²² +7888725a ⁸ x ²³ +2629575a ⁷ x ²⁴ +736281a ⁶ x ²⁵ +169911a ⁵ x ²⁶ +31465a ⁴ x ²⁷ +4495a ³ x ²⁸ +465a ² x ²⁹ +31ax ³⁰ +x ³¹
      
     多項式剰余[(x+a) ³¹ , x ²⁹ -1] =
       465a ² +a ³¹ +(31a+31a ³⁰ )x +(1+465a ²⁹ )x ² +4495a ²⁸ x ³ +31465a ²⁷ x ⁴ +169911a ²⁶ x ⁵ +736281a ²⁵ x ⁶ +2629575a ²⁴ x ⁷ +7888725a ²³ x ⁸ +20160075a ²² x ⁹ +44352165a ²¹ x ¹⁰ +84672315a ²⁰ x ¹¹ +141120525a ¹⁹ x ¹² +206253075a ¹⁸ x ¹³ +265182525a ¹⁷ x ¹⁴ +300540195a ¹⁶ x ¹⁵ +300540195a ¹⁵ x ¹⁶ +265182525a ¹⁴ x ¹⁷ +206253075a ¹³ x ¹⁸ +141120525a ¹² x ¹⁹ +84672315a ¹¹ x ²⁰ +44352165a ¹⁰ x ²¹ +20160075a ⁹ x ²² +7888725a ⁸ x ²³ +2629575a ⁷ x ²⁴ +736281a ⁶ x ²⁵ +169911a ⁵ x ²⁶ +31465a ⁴ x ²⁷ +4495a ³ x ²⁸
      
     ( A ) 多項式剰余[(x+a) ³¹ , x ²⁹ -1], 31] = a ³¹ +x ²
      
     （B）多項式剰余[x ³¹ +a, x ²⁹ -1] = a+x ²
      
     ( A ) - ( B ) = a ³¹ +x ² - (a+x ² ) = a ³¹ -a です。
      
      $\max =\left\lfloor \log _{2}(31){\sqrt {\varphi (29)}}\right\rfloor =26$ 
      
     {1 ³¹ -1 = 0 (mod 31)、2 ³¹ -2 = 0 (mod 31)、3 ³¹ -3 = 0 (mod 31)、...、26 ³¹ -26 = 0 (mod 31)}
   
   (* ステップ 6 *) 
   primeを出力します 。
     31 素数でなければならない

ここで、PolynomialModは多項式の項ごとのモジュロ減算です。例：PolynomialMod[x+2x ² +3x ³ , 3] = x+2x ² +0x ³

^[6]

参考文献

^ abcdef アグラワル、マニンドラ;カヤル、ニーラージ。サクセナ、ニティン (2004)。「PRIMES は P にあります」(PDF)。数学年報。160 (2): 781–793。土井：10.4007/annals.2004.160.781。JSTOR 3597229。
^ Granville, Andrew (2005). 「与えられた整数が素数であるかどうかを判断するのは簡単である」。Bull . Amer. Math. Soc . 42 : 3–38. doi : 10.1090/S0273-0979-04-01037-7。
^ HW Lenstra Jr. と Carl Pomerance、「ガウス周期による素数テスト」、予備版、2005 年 7 月 20 日。
^ HW Lenstra Jr. および Carl Pomerance、「Primality testing with Gaussian periods Archived 2012-02-25 at the Wayback Machine」、2011 年 4 月 12 日版。
^ ダニエル J. バーンスタイン、「Proving Primality After Agrawal-Kayal-Saxena」、2003 年 1 月 25 日版。
^ 「例 2: n はステップ 4 以降は素数ではない」が欠落している理由については、AKS トークページを参照してください。

さらに読む

ディーツフェルビンガー、マーティン（2004）。多項式時間での素数判定。ランダム化アルゴリズムからPRIMESまで、P. コンピュータサイエンスの講義ノート。第3000巻。ベルリン：Springer - Verlag。ISBN 3-540-40344-2.ZBL1058.11070 。

外部リンク

Weisstein、Eric W.「AKS 素数テスト」。MathWorld。
R. Crandall、Apple ACG、J. Papadopoulos (2003 年 3 月 18 日): AKS クラスの素数判定の実装について (PDF)
ボルネマンによる記事。3 人のインド人科学者の写真と情報が掲載されています (PDF)
アンドリュー・グランビル：与えられた整数が素数であるかどうかを判断するのは簡単です
スコット・アーロンソン著『The Prime Facts: From Euclid to AKS』(PDF)
PRIMESはPにあります。Anton StiglicによるFAQ
2006年ゲーデル賞受賞
2006年フルカーソン賞受賞
AKS「PRIMES in P」アルゴリズムリソース

[AKS-1] アグラワル、マニンドラ;カヤル、ニーラージ。サクセナ、ニティン (2004)。「PRIMES は P にあります」(PDF)。数学年報。160 (2): 781–793。土井：10.4007/annals.2004.160.781。JSTOR 3597229。

[2] Granville, Andrew (2005). 「与えられた整数が素数であるかどうかを判断するのは簡単である」。Bull . Amer. Math. Soc . 42 : 3–38. doi : 10.1090/S0273-0979-04-01037-7。

[lenstra_pomerance_2005-3] HW Lenstra Jr. と Carl Pomerance、「ガウス周期による素数テスト」、予備版、2005 年 7 月 20 日。

[lenstra_pomerance_2011-4] HW Lenstra Jr. および Carl Pomerance、「Primality testing with Gaussian periods Archived 2012-02-25 at the Wayback Machine」、2011 年 4 月 12 日版。

[bernstein03-5] ダニエル J. バーンスタイン、「Proving Primality After Agrawal-Kayal-Saxena」、2003 年 1 月 25 日版。

[6] 「例 2: n はステップ 4 以降は素数ではない」が欠落している理由については、AKS トークページを参照してください。

重要性

コンセプト

歴史と実行時間

アルゴリズム

有効性証明の概要

例1:ん= 31は素数である

参考文献

さらに読む

外部リンク

関連するトピック

インド工科大学カンプール校

マニンドラ・アグラワル

ニーラジ・カヤル

ニティン・サクセナ