有限体上の多項式の因数分解

数学およびコンピュータ代数において、多項式の因数分解とは、それを既約因数の積に分解することである。この分解は理論的には可能であり、任意の体に係数を持つ多項式に対して一意である。しかし、アルゴリズムを用いて因数分解を計算するためには、係数の体に対する強い制約が必要となる。実際には、アルゴリズムは有限体、有理数体、またはそれらのいずれかの有限生成体拡大に係数を持つ多項式に対してのみ設計されている。

有理数上の多変数多項式を含むすべての因数分解アルゴリズムは、この問題をこのケースに帰着させます。多項式因数分解を参照してください。また、これは符号理論（巡回冗長符号やBCH符号）、暗号理論（楕円曲線を用いた公開鍵暗号）、計算数論など、有限体の様々な応用にも用いられます。

多変数多項式の因数分解を一変数多項式に還元することは、有限体の係数の場合には特別な意味を持たないため、この記事では 1 つの変数を持つ多項式のみを検討します。

背景

有限体

有限体理論は、その起源をガウスとガロアの研究に遡ることができ、数学の様々な分野で役割を果たしてきました。この概念は、コンピュータサイエンスなどの数学や科学の他の分野にも応用できるため、有限体への関心が再び高まっており、これは符号理論や暗号学における重要な応用によるところが大きいです。有限体の応用は、暗号学、コンピュータ代数、そして符号理論におけるこれらの発展の一部をもたらします。

有限体またはガロア体とは、有限の位数（元の数）を持つ体である。有限体の位数は、常に素数または素数のべき乗である。各素数のべき乗 q = p ^rに対して、同型を除いてq個の元を持つ有限体がちょうど 1 つ存在する。この体はGF ( q ) またはF _qと表記される。pが素数の場合、GF ( p ) は位数pの素体である。つまり、 pを法とする剰余類の体であり、そのp個の元は 0, 1, ..., p −1と表記される。したがって、GF ( p )におけるa = b は、a ≡ b (mod p )と同じ意味である。

既約多項式

F を有限体とする。一般体と同様に、 F [ x ]の非定数多項式fは、2つの正次多項式の積でない場合、 F上既約であると言われる。 F上既約でない正次多項式は、F上既約であると言われる。

既約多項式を使うと、素数でない位数の有限体を構築できます。実際、素数冪qに対して、同型を除いて一意であるq個の元を持つ有限体をF _qとします。 F _q上で既約である、n次より大きい次数の多項式fは、 q ⁿ個の元を持つ体に同型なn次体の拡大を定義します。この拡大の元はn次未満の多項式です。 F _qの元による加算、減算、乗算は、多項式の元と同じです。2 つの元の積は、多項式としての積をfで割った余りです。元の逆は、拡張 GCD アルゴリズムで計算できます (代数拡大の算術を参照)。

したがって、素数でない位数の有限体上で計算を行うには、既約多項式を生成する必要がある。このための一般的な方法は、多項式をランダムに選び、それが既約かどうかをテストすることである。体上の乗算の効率性を高めるため、通常はx ⁿ + ax + bの形をした多項式を探す。^[要出典]^[1]

有限体上の既約多項式は、フィードバックシフトレジスタとF ₂_ⁿ上の離散対数を使用する疑似乱数ジェネレータにも役立ちます。

F _q上のn次の既約なモニック多項式の数は、モローのネックレス数え上げ関数M _q ( n )によって与えられる非周期ネックレスの数である。密接に関連するネックレス関数N _q ( n )は、 n次のモニック多項式のうち、基本多項式（既約な項の冪）を数える。あるいは、nを割り切るすべての次数dの既約な多項式を数える。^[2]

例

多項式P = x ⁴ + 1はQ上では既約ですが、任意の有限体上では既約ではありません。

F ₂の任意の体拡大において、P = ( x + 1) ⁴。
他の有限体では、−1、2、−2のうち少なくとも1つは平方体である。なぜなら、2つの平方でない数の積は平方体であり、したがって

もしそうなら $-1=a^{2},$ $P=(x^{2}+a)(x^{2}-a).$
もしそうなら $2=b^{2},$ $P=(x^{2}+bx+1)(x^{2}-bx+1).$
もしそうなら $-2=c^{2},$ $P=(x^{2}+cx-1)(x^{2}-cx-1).$

複雑

多項式因数分解アルゴリズムでは、積、除算、最大公約数、ある多項式を別の多項式で法とするべき乗など、基本的な多項式演算が使用されます。最大n^次までの 2 つの多項式の乗算は、 F _qでは「従来」の演算を使用してO ( n2 )回の演算で実行でき、 F _qでは「高速」な演算を使用してO ( nlog ( n )log(log( n ))) 回の演算で実行できます。ユークリッド除算(剰余のある除算) も同じ時間制限内で実行できます。最大n 次^までの 2 つの多項式間の多項式最大公約数のコストは、 F _qでは従来法を使用してO ( n2 ) 回の演算で実行でき、F _qでは高速な演算を使用してO ( nlog2 ( n ) log(log( n ))) 回の演算で実行でき^ます。最大n 次までの多項式h、gの場合、累乗法による累乗法を使用して、 gを法とするh ^qの累乗は、 O (log( q )) の多項式積で実行できます。つまり、古典的な方法を使用すると、 F _qではO ( n ² log( q )) の演算、または高速な方法を使用すると、 F _qではO ( n log( q )log( n ) log(log( n ))) の演算になります。

以下のアルゴリズムでは、多項式の演算に古典的なアルゴリズムを使用して、複雑度はF _qの演算回数で表現されます。

因数分解アルゴリズム

有限体上の多項式を因数分解する多くのアルゴリズムには、次の 3 つの段階が含まれます。

平方自由因数分解
異なる次数の因数分解
等次因数分解

重要な例外は、ステージ 2 と 3 を組み合わせた Berlekamp のアルゴリズムです。

ベルレカンプのアルゴリズム

ベルレカンプのアルゴリズムは、実用上うまく機能する最初の因数分解アルゴリズムとして歴史的に重要です。しかし、このアルゴリズムは基底体の元に対するループを含むため、小さな有限体上でしか実行できません。固定された基底体の場合、その時間計算量は多項式ですが、一般の基底体の場合、計算量は基底体のサイズに対して指数関数的になります。

平方自由因数分解

このアルゴリズムは、pが素数である、位数q = p ^mの有限体F _qから係数を得る多項式の平方分解を求める。このアルゴリズムはまず導関数を求め、次に多項式の最大公約数とその導関数を計算する。最大公約数が1でない場合、導関数が0でない限り（有限体上で定義された非定数多項式の場合に発生する）、最大公約数を元の多項式で再度割る。

このアルゴリズムは、多項式の導関数がゼロの場合、その多項式はx ^pの多項式であるという事実を利用しています。つまり、係数がF _pに属する場合、多項式のp乗はxをx ^{1/ p}で置換することによって得られます。係数がF _pに属さない場合、導関数がゼロの多項式のp乗根は、係数にフロベニウス自己同型の逆を適用することで完了する、xに対する同様の置換によって得られます。

このアルゴリズムは、特性ゼロの体上でも動作しますが、唯一の違いは、 p乗根を計算する命令ブロックには決して入らないという点です。しかし、この場合、 Yunのアルゴリズムはより低い次数の多項式の最大公約数を計算するため、はるかに効率的です。結果として、多項式を整数上で因数分解する際には、以下のアルゴリズムは使用されません。まず整数上で平方根のない因数分解を計算し、得られた多項式を因数分解するために、pを法として平方根のないままとなるようなpを選択します。

アルゴリズム: SFF (Square-Free Factorization)
    入力: F _q [ x ]の単項多項式 f ( q = p ^m)出力: fのSquare-Free Factorization R ← 1
    
    
   
    # wをfの因数のうち重複のないすべての因数の積とする。# p
    
    で割り切れない重複度c ← gcd ( f , f ′)
     w ← f / c 
   # ステップ 1: w
    
    のすべての因数を特定します。i ← 1 
     while  w ≠ 1 do 
        y ← gcd ( w , c )
         fac ← w / y 
        R ← R · fac ⁱ
         w ← y ; c ← c / y ; i ← i + 1 
     end while 
    # cはfの残りの因数の積（重複あり）になります。
   
    # ステップ2: 再帰を使用して残りのすべての要因を特定する# これらはpで割り切れる重複度を持つf
    の因数であることに注意する。c ≠ 1の場合、c ← c ^1/^p R ← R · SFF ( c ) ^p終了
     
        
        
     
   
    出力（R）

考え方は、fの重複度が同じすべての既約因数の積を求めることです。これは2つのステップで行われます。最初のステップでは、fの形式微分を用いて、重複度がpで割り切れないすべての因数を見つけます。2番目のステップでは、残りの因数を特定します。残りの因数はすべて重複度がpで割り切れる、つまりpのべき乗であるため、 p番目の平方根を取り、再帰を適用すれば済みます。

平方因子分解の例

させて

f=x^{11}+2x^{9}+2x^{8}+x^{6}+x^{5}+2x^{3}+2x^{2}+1\in \mathbf {F} _{3}[x],

3 つの要素を持つ体上で因数分解されます。

アルゴリズムはまず計算する

c=\gcd(f,f')=x^{9}+2x^{6}+x^{3}+2.

導関数はゼロでないので、 $w = f / c = x 2 + 2$ となり、 while ループに入ります。 1 回のループ後、 $y = x + 2$ 、 $z = x + 1$ 、 $R = x + 1$ となり、更新値は $i = 2$ 、 $w = x + 2$ 、 $c = x 8 + x 7 + x 6 + x 2 + x + 1$ となります。 2 回目のループでは $y = x + 2$ 、 $z =$ 1 、 $R = x + 1$ となり、更新値は $i = 3$ 、 $w = x + 2$ 、 $c = x 7 + 2 x 6 + x + 2$ となります。 3 回目のループでも $R$ は変化しません。 4 回目のループでは $y = 1$ 、 $z = x + 2$ 、 $R = (x + 1)(x + 2) 4$ となり、更新値は $i = 5$ 、 $w = 1$ 、 $c = x 6 +$ 1 となります。w = 1なので、whileループを抜けます。c ≠ 1 なので $、これは完全立方体でなければなりません$ $。c$ の立方根は、 $x 3 を$ $x$ に置き換えて得られる $x 2 + 1$ であり、平方根除去手続きを再帰的に呼び出すことで、これが平方根除去であることが決定されます。したがって、これを立方体化し、その時点までの $R$ の値と組み合わせると、平方根除去分解が得られます。

f=(x+1)(x^{2}+1)^{3}(x+2)^{4}.

異なる次数の因数分解

このアルゴリズムは、平方根のない多項式を、すべての既約因数が同じ次数である多項式の積に分解します。因数分解する多項式を $n次多項式$ $f \in F q [x]とします。$

アルゴリズム別次数因数分解(DDF)
    入力: 単項平方自由多項式   $f \in F q [x]$ 
    出力: f が次数 d の既約因数を持ち、 g が f の次数 d のすべての単項既約因数の積であるようなすべてのペア $($  $g$  , d
               $)$ の $集合$ 。Begin  $while$  do if 
               $g \neq 1, then$  ;
     end if i  $:$  $=$  i + 1
                 ;  $end$  $while$  $;$  $if$ , then
         ; if , then
         return { (  $f$  $,$  $1)}$  ,
             else return  $S$  End
         $i:=1;\qquad S:=\emptyset ,\qquad f^{*}:=f;$ 
          $\deg f^{*}\geq 2i$   
             $g=\gcd(f^{*},x^{q^{i}}-x)$ 
              
                 $S:=S\cup \{(g,i)\}$  $f^{*}:=f^{*}/g$ 
            
            
          $f^{*}\neq 1$   $S:=S\cup \{(f^{*},\deg f^{*})\}$   $S=\emptyset$

アルゴリズムの正確さは以下に基づいています。

補題i ≥ 1に対して多項式
$x^{q^{i}}-x\in \mathbf {F} _{q}[x]$
はF _q [ x ]内のiを割り切る次数のすべての単項既約多項式の積である。

一見すると、これは入力多項式の次数に対して指数関数的な次数の多項式の最大公約数を計算するため、効率的ではないように見えます。しかし、

g=\gcd \left(f^{*},x^{q^{i}}-x\right)

置き換えられる可能性がある

g=\gcd \left(f^{*},\left(x^{q^{i}}-x\mod f^{*}\right)\right).

したがって、次の式を計算する必要があります。

x^{q^{i}}-x\mod f^{*},

方法は2つあります。

方法I.の値から開始
$x^{q^{i-1}}\mod f^{*}$

前のステップで計算された値と、その新しいf*を法とするq乗を、2乗法によるべき乗法を用いて計算する。これには

$O\left(\log(q)\deg(f)^{2}\right)$

各ステップでF _qの算術演算を実行し、

$O\left(\log(q)\deg(f)^{3}\right)$
アルゴリズム全体の算術演算。

方法II. q乗がF _q上の線型写像であるという事実を利用して、その行列を計算する。
$O\left(\deg(f)^{2}(\log(q)+\deg(f))\right)$

ループの各反復において、行列とベクトルの積を計算する（O (deg( f ) ^{2 )回の演算）。これにより}_、 Fqにおける演算の総数は

$O\left(\deg(f)^{2}(\log(q)+\deg(f))\right).$
したがって、この2番目の方法はより効率的であり、通常はこちらが好まれます。さらに、この方法で計算される行列は、ほとんどのアルゴリズムで等次数分解（下記参照）に使用されているため、これを異次数分解に使用することで、さらなる計算時間を節約できます。

等次因数分解

カントール・ザッセンハウスアルゴリズム

このセクションでは、有限体F _q上のn次モニック平方自由一変数多項式fの因数分解について考察します。この多項式 f には、 $r$ $\geq 2個の、それぞれ$ d次で異なる既約因数が2 つあります。 $f_{1},\ldots ,f_{r}$

まず、CantorとZassenhaus (1981)によるアルゴリズムについて説明し、次に計算量がやや少ない変種について説明します。どちらも実行時間がランダム選択に依存する確率的アルゴリズム（ラスベガスアルゴリズム）であり、平均実行時間は良好です。次のセクションでは、Shoup (1990)によるアルゴリズムについて説明します。これも等次因数分解アルゴリズムですが、決定論的です。これらのアルゴリズムはすべて、係数体の次数qが奇数である必要があります。その他の因数分解アルゴリズムについては、例えばKnuthの著書『The Art of Computer Programming』第2巻を参照してください。

アルゴリズムカントール・ザッセンハウスアルゴリズム。
    入力:奇数位数_qの有限体F q。F _q [ x ]のn = rd次
           モニック平方自由多項式f、r ≥ 2 個の既約因子
                を持ち、それぞれ次数はdです。
    出力: fの単数既約因子の集合。

    因子:= { f };
    サイズ(因子) < rの場合、 F _q [ x ]においてdeg( h ) < n となるh をランダムに
        
        選択します。Factorsにおいてdeg( u ) > dとなる各uについて、 gcd( g , u ) ≠ 1 かつ gcd( g , u ) ≠ uの場合、
                Factors:= Factors を実行します。endif
             endwhile $g:=h^{\frac {q^{d}-1}{2}}-1{\pmod {f}}$ 
           
             $\,\setminus \,\{u\}\cup \{(\gcd(g,u),u/\gcd(g,u))\}$ 
    

    リターン要因

このアルゴリズムの正しさは、環F _q [ x ]/ fが体F _q [ x ]/ f _iの直積であることに依存している。ここでf _{i は}fの既約因子上を走る。これらの体はすべてq ^d個の元を持つので、これらの体のいずれかにおけるgの成分は確率でゼロとなる。

{\frac {q^{d}-1}{2q^{d}}}\sim {\tfrac {1}{2}}.

これは、多項式gcd( g、u )がgの成分がゼロであるgの因数の積であることを意味します。

アルゴリズムのwhileループの平均反復回数は未満であることが示されており、 Fqにおける算術演算の平均回数はとなる_。 [ 3 ^] $2.5\log _{2}r$ $O(dn^{2}\log(r)\log(q))$

d log( q ) > nの典型的なケースでは、この複雑さは次のように軽減される。

O(n^{2}(\log(r)\log(q)+n))

線形写像の核で hを選択することによって

v\to v^{q}-v{\pmod {f}}

命令を置き換える

g:=h^{\frac {q^{d}-1}{2}}-1{\pmod {f}}

による

g:=h^{\frac {q-1}{2}}-1{\pmod {f}}.

妥当性の証明は上記と同じで、体F _q [ x ]/ f _iの直積をq元を持つそれらの部分体の直積に置き換えます。計算量は、アルゴリズム自体、線形マップの行列の計算（これは平方自由分解で既に計算されている可能性があります）とカーネルの計算にO ( n ³ ) に分解されます。このアルゴリズムは、因子の次数が同じでなくても機能することに注意してください（この場合、while ループを停止するために必要な因子の数rは、カーネルの次元として求められます）。ただし、このアルゴリズムを使用する前に平方自由分解を行うと、計算量は若干改善されます（平方自由分解ではnが減少する可能性があるため、重要なステップの計算量が削減されます）。 $O(n^{2}\log(r)\log(q))$ $O(n^{2}(\log(q)+n))$

ビクター・ショウプのアルゴリズム

前節のアルゴリズムと同様に、Victor Shoupのアルゴリズムは等次因数分解アルゴリズムである。^[4]それらとは異なり、Victor Shoupのアルゴリズムは決定論的アルゴリズムである。しかし、実際には前節のアルゴリズムほど効率的ではない。Shoupのアルゴリズムでは、入力は素体F _p上の多項式に制限される。

ショウプのアルゴリズムの最悪計算時間計算量はp 倍になります。指数関数的ではありますが、この計算時間は $p$ 倍になる従来の決定論的アルゴリズム（ベルレカンプのアルゴリズム）よりもはるかに優れています。しかし、計算時間が指数関数的になる多項式は非常に少なく、アルゴリズムの平均計算時間計算量は p 倍になります。ここで、 $d$ は多項式の次数、 $p$ は基底体の要素数です。 ${\sqrt {p}}.$ $d\log(p),$

g = g ₁ ... g _kを目的の因数分解とする。ここでg _{i は}次数dの異なる単数既約多項式である。n = deg( g ) = kd とする。環R = F _q [ x ]/ gを考え、 xのRへの像をxで表す。環Rは体R _i = F _q [ x ]/ g _iの直積であり、 p _iでRからR _iへの自然準同型を表す。R _iのF _q上のガロア群は位数dの巡回群であり、体自己同型u → u ^pによって生成される。したがって、g _iのR _iへの根は

p_{i}(x),p_{i}(x^{q}),p_{i}\left(x^{q^{2}}\right),\ldots ,p_{i}\left(x^{q^{d-1}}\right).

前のアルゴリズムと同様に、このアルゴリズムは、ベルレカンプのアルゴリズムと同じRの部分代数 Bを使用する。これは「ベルレカンプ部分代数」とも呼ばれ、次のように定義される。

{\begin{aligned}B&=\left\{\alpha \in R\ :\ p_{1}(\alpha ),\cdots ,p_{k}(\alpha )\in \mathbf {F} _{q}\right\}\\&=\{u\in R\ :\ u^{q}=u\}\end{aligned}}

Bの部分集合Sが分離集合であるとは、任意の1 ≤ i < j ≤ kに対して、S∈S が存在し、となるときを言う。前述のアルゴリズムでは、分離集合はSの要素をランダムに選択することによって構成される。ショウプのアルゴリズムでは、分離集合は次のように構成される。R [ Y ] のsが、 $p_{i}(s)\neq p_{j}(s)$

{\begin{aligned}s&=(Y-x)\left(Y-x^{q}\right)\cdots \left(Y-x^{q^{d-1}}\right)\\&=s_{0}+\cdots +s_{d-1}Y^{d-1}+Y^{d}\end{aligned}}

すると、i =1, ..., kに対して（2つのモニック多項式は同じ根を持つ）、分離集合となる。g _iは互いに異なるため、異なる添字の組（ i , j ）ごとに、係数s _hの少なくとも1つは $\{s_{0},\dots ,s_{d-1}\}$ $p_{i}(s)=g_{i}$ $p_{i}(s_{h})\neq p_{j}(s_{h}).$

分離集合を持つショウプのアルゴリズムは、単に「線形写像の核内のh をランダムに選択する」という命令を「 hがS内にあり、i が{1, ..., k −1} 内にある状態でh + i を選択する」に置き換えることで、前のセクションの最後のアルゴリズムと同じように進行します。 $v\to v^{q}-v{\pmod {f}}$

時間計算量

前の節で述べたように、有限体上の因数分解には、多項式時間計算量のランダム化アルゴリズム（例えばカントール・ザッセンハウスアルゴリズム）があります。また、平均計算量が多項式時間となる決定論的アルゴリズム（例えばショウプのアルゴリズム）もあります。

多項式最悪の複雑度を持つ決定論的アルゴリズムの存在は、まだ未解決の問題です。

ラビンの還元不可能性のテスト

個別次数分解アルゴリズムと同様に、ラビンのアルゴリズム^[5]は上記の補題に基づいています。個別次数分解アルゴリズムは、入力多項式の次数の半分以下のすべてのdをテストします。ラビンのアルゴリズムは、より少ないdを考慮する場合、因子が不要であるという利点を活用しています。それ以外は、個別次数分解アルゴリズムと同様です。これは、以下の事実に基づいています。

p ₁ , ..., p _kをnのすべての素因数とし、（1 ≤ i ≤ k）とすると、 n次F _q [ x ] の多項式fがF _q [ x ]で既約となるのは、（1 ≤ i ≤ k）かつf がを割り切れるときのみです。実際、f がn を割り切れない次数の因数を持つ場合、f はを割り切れません。一方、 f がn を割り切れる次数の因数を持つ場合、この因数は少なくとも次の 1 つを割り切れます。 $n/p_{i}=n_{i}$ $\gcd \left(f,x^{q^{n_{i}}}-x\right)=1$ $x^{q^{n}}-x$ $x^{q^{n}}-x$ $x^{q^{n_{i}}}-x.$

アルゴリズムラビン既約性テスト
    入力: n次のF _q [ x ]の単項多項式f、 
         p ₁、...、p _{k は}すべてnの異なる素因数。
    出力:「 fは既約ではない」または「fは既約である」のいずれか。

    j  = 1 からkまで実行します。i
     = 1 から k まで実行します。g :
         =  gcd( f , h ) ;
         g ≠ 1の場合、 「fは既約」を返してSTOP します。for
    の終了。g
     = 0
    の場合、「fは既約」 
        を返し、それ以外の場合は「fは既約」
を返します。  
         $n_{j}=n/p_{j}$    
         $h:=x^{q^{n_{i}}}-x{\bmod {f}}$   $g:=x^{q^{n}}-x{\bmod {f}}$

このアルゴリズムの基本的な考え方は、最小値から繰り返し平方和を求めるかフロベニウス自己同型を用いて計算し、対応する最大公約数を求めるというものである。初等多項式演算を用いると、フロベニウス自己同型行列の計算にはF _qにおける演算が必要となり、 $x^{q^{n_{i}}}{\bmod {f}}$ $n_{1},\ldots ,n_{k}$ $O(n^{2}(n+\log q))$

x^{q^{n_{i}}}-x{\pmod {f}}

はさらにO ( n ³ ) 回の演算が必要であり、アルゴリズム自体もO ( kn ² ) 回の演算を必要とするため、F _qでは演算の合計はになります。高速演算（乗算と除算、およびGCD 計算の計算量）を使用すると、繰り返しの二乗によるの計算はとなり、アルゴリズム自体はとなり、F _qでは演算の合計はになります。 $O(n^{2}(n+\log q))$ $O(n\log n)$ $O(n(\log n)^{2})$ $x^{q^{n_{i}}}-x{\bmod {f}}$ $O(n^{2}\log n\log q)$ $O(kn(\log n)^{2})$ $O(n^{2}\log n\log q)$

参照

参考文献

ケンプファート、H（1969）多項式の因数分解についてオハイオ州立大学数学科、オハイオ州コロンバス43210
Shoup, Victor (1996)有限体上の滑らかさと因数分解多項式トロント大学コンピュータサイエンス学部
Von Zur Gathen, J. ; Panario, D. (2001). 有限体上の多項式の因数分解：概説. Journal of Symbolic Computation , 第31巻, 第1～2号, 2001年1月, 3--17.
Gao Shuhong, Panario Daniel, Test and Construction of Inreducible Polynomials over Finite Fieldsクレムソン大学数理科学科、サウスカロライナ州、29634–1907、アメリカ合衆国。およびトロント大学コンピュータサイエンス科、カナダ M5S-1A4
ショウプ、ビクター（1989）有限体上の既約多項式を求めるための新しいアルゴリズムウィスコンシン大学マディソン校コンピュータサイエンス学部
ゲデス, キース・O. ; チャポル, スティーブン・R. ; ラバーン, ジョージ (1992). コンピュータ代数のためのアルゴリズム. ボストン, マサチューセッツ州: クルーワー・アカデミック・パブリッシャーズ. pp. xxii+585. ISBN 0-7923-9259-0。

注記

^ “$\mathbb{Z}_2$ 上の還元可能性？”. Mathematics Stack Exchange . 2023年9月10日閲覧。
^ Christophe Reutenauer、Mots circulaires et Polynomes irreductibles、Ann.科学。数学ケベック、第 12 巻、第 2 号、275-285 ページ
^ フラジョレ、フィリップ; ステアヤート、ジャン＝マルク (1982)、「オートマタ、言語、プログラミング」、Lecture Notes in Comput. Sci.、第140巻、オーフス：シュプリンガー、pp. 239– 251、doi :10.1007/BFb0012773、ISBN 978-3-540-11576-2
^ Victor Shoup, 有限体上の因数分解多項式の決定論的計算量について, Information Processing Letters 33:261-267, 1990
^ ラビン、マイケル (1980). 「有限体における確率的アルゴリズム」。SIAM ジャーナルオンコンピューティング。9 ( 2 ) : 273–280。CiteSeerX 10.1.1.17.5653 。土井：10.1137/0209024。

外部リンク

いくつかの既約多項式 http://www.math.umn.edu/~garrett/m/algebra/notes/07.pdf
体とガロア理論:http://www.jmilne.org/math/CourseNotes/FT.pdf
ガロア体:http://designtheory.org/library/encyc/topics/gf.pdf 2010年12月15日アーカイブ、Wayback Machine
有限体上の多項式の因数分解: http://www.science.unitn.it/~degraaf/compalg/polfact.pdf 2011年7月21日アーカイブ、Wayback Machineにて

[1] “$\mathbb{Z}_2$ 上の還元可能性？”. Mathematics Stack Exchange . 2023年9月10日閲覧。

[2] Christophe Reutenauer、Mots circulaires et Polynomes irreductibles、Ann.科学。数学ケベック、第 12 巻、第 2 号、275-285 ページ

[3] フラジョレ、フィリップ; ステアヤート、ジャン＝マルク (1982)、「オートマタ、言語、プログラミング」、Lecture Notes in Comput. Sci.、第140巻、オーフス：シュプリンガー、pp. 239– 251、doi :10.1007/BFb0012773、ISBN 978-3-540-11576-2

[4] Victor Shoup, 有限体上の因数分解多項式の決定論的計算量について, Information Processing Letters 33:261-267, 1990

[5] ラビン、マイケル (1980). 「有限体における確率的アルゴリズム」。SIAM ジャーナルオンコンピューティング。9 ( 2 ) : 273–280。CiteSeerX 10.1.1.17.5653 。土井：10.1137/0209024。