AKS素数性テスト

素数判定アルゴリズム

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

重要性

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

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

このアルゴリズムは理論的には非常に重要であるものの、実際にはほとんど使用されていないため、いわば「銀河アルゴリズム」と化しています。64ビット入力の場合、Baillie-PSWテストは決定論的であり、桁違いに高速に実行されます。より大きな入力の場合、（これも無条件に正しい）ECPPテストとAPRテストの性能はAKSをはるかに上回ります。さらに、ECPPは素数証明を出力できるため、結果の独立かつ迅速な検証が可能ですが、これはAKSアルゴリズムでは不可能です。

概念

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

(X+a)^{n}\equiv X^{n}+a{\pmod {n}}

1

は多項式環内で成り立つ。^[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$

(X+a)^{n}\equiv (X^{n}+a){\pmod {X^{r}-1,n}}

2

これは次と同じです

(X+a)^{n}-(X^{n}+a)=(X^{r}-1)g+nf

3

いくつかの多項式とに対して $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 and 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 ₂は2進対数、rのオイラーのトーシェント関数です。 $\varphi (r)$

ステップ3は、論文ではすべてのa ≤ rについて 1 < gcd( 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] 通常、これらの変更によって計算の複雑さは変わりませんが、かかる時間が桁違いに短縮される可能性があります。たとえば、バーンスタインの最終バージョンでは、理論的な速度向上は200万倍以上になります。

有効性証明の概要

アルゴリズムが正しいためには、n を特定するすべてのステップが正しくなければなりません。ステップ 1、3、4 は、nの割り切れるかどうかを直接判定することに基づいているため、自明に正しいです。ステップ 5 も正しいです。(2) は、 n が素数である場合、 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：n= 31は素数です

   入力：整数n = 31 > 1

   (* ステップ 1 *)
   整数a > 1 かつb > 1 
     の場合、 n = a ^bを出力します。
      b = 2; b <= log ₂ (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を見つけます。 
     maxk = ⌊(log ₂ n) ² ⌋;
     maxr = Max[3, ⌈(Log ₂ n) ⁵ ⌉]; (* maxrは実際には必要ありません *)
     nextR = 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--) {
        ((gcd = GCD[a,n]) > 1 && gcd < n) の場合、 
          [合成]を返します。 
     }
      
     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。
^ グランビル、アンドリュー (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. Zbl 1058.11070.

外部リンク

ワイスタイン、エリック・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] グランビル、アンドリュー (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 トークページを参照してください。