有限体

Algebraic structure

数学において、有限体またはガロア体（エヴァリスト・ガロアにちなんで名付けられた）は、有限個の元を持つ体です。他の体と同様に、有限体とは、乗算、加算、減算、除算の演算が定義され、特定の基本規則を満たす集合です。有限体の最も一般的な例は、 が素数であるときの を法とする整数です。 ${\displaystyle p}$ ${\displaystyle p}$

有限体の位数はその元の数であり、素数または素数のべき乗のいずれかである。すべての素数とすべての正の整数に対して、位数の体が存在する。与えられた位数のすべての有限体は同型である。 ${\displaystyle p}$ ${\displaystyle k}$ ${\displaystyle p^{k}}$

有限体は、数論、代数幾何学、ガロア理論、有限幾何学、暗号化、符号理論など、数学とコンピュータサイエンスの多くの分野の基礎となります。

プロパティ

有限体とは有限集合である体である。有限体には乗算、加算、減算、除算（ゼロ除算を除く）が定義され、体の公理を満たす有限個の元があることを意味する。^[1]

有限体の元の数は、その位数あるいは大きさと呼ばれる。位数の有限体が存在するのは、 が素数冪（は素数、は正の整数）である場合に限る。位数の体では、任意の元のコピーを足し合わせると常にゼロになる。つまり、体の特性は である。^[1] ${\displaystyle q}$ ${\displaystyle q}$ ${\displaystyle p^{k}}$ ${\displaystyle p}$ ${\displaystyle k}$ ${\displaystyle p^{k}}$ ${\displaystyle p}$ ${\displaystyle p}$

に対して、すべての位数体は同型である（以下の§ 存在と一意性を参照）。^[2]さらに、体は同じ位数を持つ2つの異なる有限部分体を含むことはできない。したがって、すべての有限体は同じ位数と同一視でき、それらは明確に、または と表記される。ここで、GF は「ガロア体」を表す。^[3] ${\displaystyle q=p^{k}}$ ${\displaystyle q}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle \mathbf {F} _{q}}$ ${\displaystyle \mathrm {GF} (q)}$

位数の有限体において、多項式は有限体のすべての元を根として持ちます。有限体の非零元は乗法群を形成します。この群は巡回群であるため、すべての非零元は、体の原始元と呼ばれる単一の元の冪乗として表すことができます。（一般に、与えられた体には複数の原始元が存在します。）^[1] ${\displaystyle q}$ ${\displaystyle X^{q}-X}$ ${\displaystyle q}$

有限体の最も単純な例は素数位数の体である。各素数 に対して、位数の素体は 、を法とした整数として構成できる。^[1] ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$

位数素体の元は、範囲 の整数で表すことができます。和、差、積は、対応する整数演算の結果を で割ったときの剰余です。元の逆数は、拡張ユークリッド互除法を用いて計算できます（拡張ユークリッド互除法 § モジュラー整数を参照）。^[1] ${\displaystyle p}$ ${\displaystyle 0,\ldots ,p-1}$ ${\displaystyle p}$

を有限体とする。 の任意の元と任意の整数 に対して、のコピーの和 を とする。となる最小の正値は、の体の特性である。これにより、 を表す整数 を選ぶことで、の元と の元の乗算を定義することができる。この乗算により、 は-ベクトル空間となる。したがって、 の元の数は、ある整数 に対して となる。^[1] ${\displaystyle F}$ ${\displaystyle x}$ ${\displaystyle F}$ ${\displaystyle n}$ ${\displaystyle n\cdot x}$ ${\displaystyle n}$ ${\displaystyle x}$ ${\displaystyle n}$ ${\displaystyle n\cdot 1=0}$ ${\displaystyle p}$ ${\displaystyle (k,x)\mapsto k\cdot x}$ ${\displaystyle k}$ ${\displaystyle \mathrm {GF} (p)}$ ${\displaystyle x}$ ${\displaystyle F}$ ${\displaystyle k}$ ${\displaystyle F}$ ${\displaystyle \mathrm {GF} (p)}$ ${\displaystyle F}$ ${\displaystyle p^{n}}$ ${\displaystyle n}$

恒等式（フレッシュマンズドリーム^[4]と呼ばれることもある）は、特性 の体において真である。これは二項定理から導かれる。なぜなら、の展開における各二項係数は、最初と最後を除いて の倍数だからである。^{[1] : 548} $${\displaystyle (x+y)^{p}=x^{p}+y^{p}}$$ ${\displaystyle p}$ ${\displaystyle (x+y)^{p}}$ ${\displaystyle p}$

フェルマーの小定理によれば、が素数で が体に属する場合、となる。これは上の多項式が等式であることを意味する。より一般的には、 のすべての元は多項式方程式 を満たす。^[5] ${\displaystyle p}$ ${\displaystyle x}$ ${\displaystyle \mathrm {GF} (p)}$ ${\displaystyle x^{p}=x}$ $${\displaystyle X^{p}-X=\prod _{a\in \mathrm {GF} (p)}(X-a)}$$ ${\displaystyle \mathrm {GF} (p)}$ ${\displaystyle \mathrm {GF} (p^{n})}$ ${\displaystyle x^{p^{n}}-x=0}$

有限体の任意の有限体拡大は可分かつ単純である。つまり、が有限体で が の部分体である場合、は の最小多項式が可分となる単一の元を に付加することによって得られる。専門用語で言えば、有限体は完全 である。^[1] ${\displaystyle E}$ ${\displaystyle F}$ ${\displaystyle E}$ ${\displaystyle E}$ ${\displaystyle F}$

体の他のすべての公理を満たすが、その乗法が可換である必要がない、より一般的な代数構造は、除算環（あるいは歪体）と呼ばれる。ウェダーバーンの小定理によれば、任意の有限除算環は可換であり、したがって有限体である。^[1]

存在と唯一性

を素数冪とし、を素体 上の多項式の 分解体とします。これは、が最低位の有限体であり、その が別個の根を持つことを意味します（の形式的微分はであり、 であることを意味し、一般に分解体が元の の分離可能な拡大であることを意味します）。上記の恒等式は、 の2つの根の和と積が の根であり、 の根の逆数でもあることを示しています。言い換えると、 の根は の位数の体を形成し、これは分解体の極小性によってに等しくなります。 ${\displaystyle q=p^{n}}$ ${\displaystyle F}$ $${\displaystyle P=X^{q}-X}$$ ${\displaystyle \mathrm {GF} (p)}$ ${\displaystyle F}$ ${\displaystyle P}$ ${\displaystyle q}$ ${\displaystyle P}$ ${\displaystyle P'=-1}$ ${\displaystyle \mathrm {gcd} (P,P')=1}$ ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle q}$ ${\displaystyle F}$

分解体の同型性を除く一意性は、したがって、すべての位数体が同型であることを意味する。また、ある体が位数体を部分体として持つ場合、その元はの根であり、位数体 の他の部分体を含むことはできない。 ${\displaystyle q}$ ${\displaystyle F}$ ${\displaystyle q=p^{k}}$ ${\displaystyle q}$ ${\displaystyle X^{q}-X}$ ${\displaystyle F}$ ${\displaystyle q}$

まとめると、1893年にE.H.ムーアによって最初に証明された次の分類定理があります。^[2]

有限体の位数は素冪である。任意の素冪に対して位数 の体が存在し、それらはすべて同型である。これらの体では、すべての元が を満たし、多項式は次のように因数 分解される。 ${\displaystyle q}$ ${\displaystyle q}$ $${\displaystyle x^{q}=x,}$$ ${\displaystyle X^{q}-X}$ $${\displaystyle X^{q}-X=\prod _{a\in F}(X-a).}$$

が と同型な部分体を含む場合、かつが の約数である場合に限ります。この場合、この部分体は一意です。実際、多項式が を割り切る場合、かつ が の約数である場合に限ります。 ${\displaystyle \mathrm {GF} (p^{n})}$ ${\displaystyle \mathrm {GF} (p^{m})}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle X^{p^{m}}-X}$ ${\displaystyle X^{p^{n}}-X}$ ${\displaystyle m}$ ${\displaystyle n}$

明示的な構築

非素数体

素数と を持つ素数冪が与えられた場合、体 は次のように明示的に構成できます。まず、次数の既約多項式を選びます（そのような既約多項式は常に存在します）。次に、によって生成される主イデアルによる多項式環の商環は、位数の体になります。 ${\displaystyle q=p^{n}}$ ${\displaystyle p}$ ${\displaystyle n>1}$ ${\displaystyle \mathrm {GF} (q)}$ ${\displaystyle P}$ ${\displaystyle \mathrm {GF} (p)[X]}$ ${\displaystyle n}$ $${\displaystyle \mathrm {GF} (q)=\mathrm {GF} (p)[X]/(P)}$$ ${\displaystyle \mathrm {GF} (p)[X]}$ ${\displaystyle P}$ ${\displaystyle q}$

より明確に言えば、 の元は上の多項式であり、その次数は より確実に小さい。 の加算と減算は 上の多項式の加算と減算である。2つの元の積はの積を で割った余りである。非ゼロ元の逆数は拡張ユークリッド互除法で計算できる。拡張ユークリッド互除法の§ 単純な代数体拡張 を参照。 ${\displaystyle \mathrm {GF} (q)}$ ${\displaystyle \mathrm {GF} (p)}$ ${\displaystyle n}$ ${\displaystyle \mathrm {GF} (p)}$ ${\displaystyle P}$ ${\displaystyle \mathrm {GF} (q)[X]}$

しかし、この表現では、 の元を対応する多項式と区別するのが難しい場合があります。そのため、一般的には、多項式 に対応する の元に名前を付けます。つまり、 の元は の多項式になります（ただし、 ）。また、の次数が 以上の多項式（例えば乗算の後）に遭遇した場合、の関係を用いて次数を小さくする必要があることがわかります（ユークリッド除算と同じです）。 ${\displaystyle \mathrm {GF} (q)}$ ${\displaystyle \alpha }$ ${\displaystyle \mathrm {GF} (q)}$ ${\displaystyle X}$ ${\displaystyle \mathrm {GF} (q)}$ ${\displaystyle \alpha }$ ${\displaystyle P(\alpha )=0}$ ${\displaystyle \alpha }$ ${\displaystyle n}$ ${\displaystyle P(\alpha )=0}$

の構築を除いて、 には同型な結果をもたらす複数の可能な選択肢がある。ユークリッド除算を簡略化するために、必要なユークリッド除算を非常に効率的にする形式の多項式 を に対して選択するのが一般的である。しかし、いくつかの体、典型的には特性 において、形式の既約多項式が存在しない可能性がある。特性 において多項式が既約である場合、多項式を既約にする可能な限り最小のを選択することが推奨される。これらの三項式がすべて既約である場合、「五項式」 を選択する。なぜなら、より大きい次数で項数が偶数である多項式は、特性 において既約になることはなく、 を根として持つからである。^[6] ${\displaystyle \mathrm {GF} (4)}$ ${\displaystyle P}$ ${\displaystyle P}$ $${\displaystyle X^{n}+aX+b,}$$ ${\displaystyle 2}$ ${\displaystyle X^{n}+aX+b}$ ${\displaystyle 2}$ ${\displaystyle X^{n}+X+1}$ ${\displaystyle X^{n}+X^{k}+1}$ ${\displaystyle k}$ ${\displaystyle X^{n}+X^{a}+X^{b}+X^{c}+1}$ ${\displaystyle 1}$ ${\displaystyle 2}$ ${\displaystyle 1}$

そのような多項式の選択肢として、コンウェイ多項式が挙げられます。コンウェイ多項式は、体の表現とその部分体の表現の間に一定の互換性を保証します。

次のセクションでは、上で概説した一般的な構築方法が小さな有限体に対してどのように機能するかを示します。

4つの要素を持つフィールド

最小の非素体とは、4つの元を持つ体であり、一般的にまたは と表記されます。これは、、、 、 の4つの元で構成され、任意のに対して、その他の演算結果は分配法則から容易に導き出されます。完全な演算表については、以下を参照してください。 ${\displaystyle \mathrm {GF} (4)}$ ${\displaystyle \mathbb {F} _{4}.}$ ${\displaystyle 0,1,\alpha ,1+\alpha }$ ${\displaystyle \alpha ^{2}=1+\alpha }$ ${\displaystyle 1\cdot \alpha =\alpha \cdot 1=\alpha }$ ${\displaystyle x+x=0}$ ${\displaystyle x\cdot 0=0\cdot x=0}$ ${\displaystyle x\in \mathrm {GF} (4)}$

これは、前のセクションの結果から次のように推測できます。

上では、次数の既約多項式は1つしかありません。したがって、 は前のセクションの構築にこの多項式を含める必要があり、は におけるこの多項式の根を表すものとします。これは、および がの元であり、は に含まれない であることを意味します。このことから、 における演算の表が得られます。 および は以下のとおりです。 ${\displaystyle \mathrm {GF} (2)}$ ${\displaystyle 2}$ $${\displaystyle X^{2}+X+1}$$ ${\displaystyle \mathrm {GF} (4)}$ $${\displaystyle \mathrm {GF} (4)=\mathrm {GF} (2)[X]/(X^{2}+X+1).}$$ ${\displaystyle \alpha }$ ${\displaystyle \mathrm {GF} (4)}$ $${\displaystyle \alpha ^{2}=1+\alpha ,}$$ ${\displaystyle \alpha }$ ${\displaystyle 1+\alpha }$ ${\displaystyle \mathrm {GF} (4)}$ ${\displaystyle \mathrm {GF} (2)}$ ${\displaystyle \mathrm {GF} (4)}$

追加 ${\displaystyle x+y}$ y × 0 1 α 1 + α 0 0 1 α 1 + α 1 1 0 1 + α α α α 1 + α 0 1 1 + α 1 + α α 1 0

乗算 ${\displaystyle x\cdot y}$ y × 0 1 α 1 + α 0 0 0 0 0 1 0 1 α 1 + α α 0 α 1 + α 1 1 + α 0 1 + α 1 α

相互 × ⁠1/×⁠ 0 — 1 1 α 1 + α 1 + α α

減算の表は示されていません。なぜなら、減算は加法と同一であり、これは標数2のすべての体の場合と同様だからです。除算するには、逆数を掛けます: ⁠ ⁠ ${\displaystyle x/y=x\cdot (1/y)}$。あらゆる体の場合と同様に、ゼロ除算は定義されていません。表から、 の加法構造はクラインの4元群と同型であり、非ゼロの乗法構造は群 と同型であることがわかります。 ${\displaystyle \mathrm {GF} (4)}$ ${\displaystyle Z_{3}}$

この写像は、フロベニウス自己同型と呼ばれる非自明な体自己同型であり、 を前述の既約多項式 の2 番目の根に代入します。 $${\displaystyle \varphi :x\mapsto x^{2}}$$ ${\displaystyle \alpha }$ ${\displaystyle 1+\alpha }$ ${\displaystyle X^{2}+X+1}$

GF(p²）奇数素数p

の場合に上記の一般的な有限体の構成を適用するには、2次の既約多項式を見つける必要があります。 については、これは前のセクションで行われました。 が奇数の素数である場合、 の範囲内でという形の既約多項式が常に存在します。 ${\displaystyle \mathrm {GF} (p^{2})}$ ${\displaystyle p=2}$ ${\displaystyle p}$ ${\displaystyle X^{2}-r}$ ${\displaystyle r}$ ${\displaystyle \mathrm {GF} (p)}$

より正確には、多項式 が上で既約でない場合、かつ が を法とする二次非剰余である場合に限ります（これはほぼ二次非剰余の定義です）。 を法とする二次非剰余が存在します。例えば、は に対して二次非剰余であり、は に対して二次非剰余です。、つまり の場合、 を二次非剰余として選択することができ、これにより非常に単純な既約多項式 が得られます。 ${\displaystyle X^{2}-r}$ ${\displaystyle \mathrm {GF} (p)}$ ${\displaystyle r}$ ${\displaystyle p}$ ${\displaystyle {\frac {p-1}{2}}}$ ${\displaystyle p}$ ${\displaystyle 2}$ ${\displaystyle p=3,5,11,13,\ldots }$ ${\displaystyle 3}$ ${\displaystyle p=5,7,17,\ldots }$ ${\displaystyle p\equiv 3\mod 4}$ ${\displaystyle p=3,7,11,19,\ldots }$ ${\displaystyle -1\equiv p-1}$ ${\displaystyle X^{2}+1}$

二次非剰余 を選んだ上で、を の記号平方根、つまり の性質を持つ記号とします。これは、複素数が の記号平方根であるのと同じです。すると、 の元は、において、 と を含むすべての線形式になります。 の演算は次のように定義されます（ の元をラテン文字で表した演算は、 における演算です）。 ${\displaystyle r}$ ${\displaystyle \alpha }$ ${\displaystyle r}$ ${\displaystyle \alpha ^{2}=r}$ ${\displaystyle i}$ ${\displaystyle -1}$ ${\displaystyle \mathrm {GF} (p^{2})}$ $${\displaystyle a+b\alpha ,}$$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle \mathrm {GF} (p)}$ ${\displaystyle \mathrm {GF} (p^{2})}$ ${\displaystyle \mathrm {GF} (p)}$ ${\displaystyle \mathrm {GF} (p)}$ $${\displaystyle {\begin{aligned}-(a+b\alpha )&=-a+(-b)\alpha \\(a+b\alpha )+(c+d\alpha )&=(a+c)+(b+d)\alpha \\(a+b\alpha )(c+d\alpha )&=(ac+rbd)+(ad+bc)\alpha \\(a+b\alpha )^{-1}&=a(a^{2}-rb^{2})^{-1}+(-b)(a^{2}-rb^{2})^{-1}\alpha \end{aligned}}}$$

GF(8)とGF(27)

多項式はおよび上で既約である。つまり、 および を法として既約である（これを示すには、 にも にも根を持たないことを示すだけで十分である）。したがって、およびの元は、またはの元（それぞれ）である式で表すことができ、 は次のような記号である。 $${\displaystyle X^{3}-X-1}$$ ${\displaystyle \mathrm {GF} (2)}$ ${\displaystyle \mathrm {GF} (3)}$ ${\displaystyle 2}$ ${\displaystyle 3}$ ${\displaystyle \mathrm {GF} (2)}$ ${\displaystyle \mathrm {GF} (3)}$ ${\displaystyle \mathrm {GF} (8)}$ ${\displaystyle \mathrm {GF} (27)}$ $${\displaystyle a+b\alpha +c\alpha ^{2},}$$ ${\displaystyle a,b,c}$ ${\displaystyle \mathrm {GF} (2)}$ ${\displaystyle \mathrm {GF} (3)}$ ${\displaystyle \alpha }$ $${\displaystyle \alpha ^{3}=\alpha +1.}$$

したがって、 および 上の加算、加法逆演算、および上の乗算は次のように定義されます。次の式では、ラテン文字で表されるまたはの要素間の演算は、それぞれまたはにおける演算です。 ${\displaystyle \mathrm {GF} (8)}$ ${\displaystyle \mathrm {GF} (27)}$ ${\displaystyle \mathrm {GF} (2)}$ ${\displaystyle \mathrm {GF} (3)}$ ${\displaystyle \mathrm {GF} (2)}$ ${\displaystyle \mathrm {GF} (3)}$ $${\displaystyle {\begin{aligned}-(a+b\alpha +c\alpha ^{2})&=-a+(-b)\alpha +(-c)\alpha ^{2}\qquad {\text{(for }}\mathrm {GF} (8),{\text{this operation is the identity)}}\\(a+b\alpha +c\alpha ^{2})+(d+e\alpha +f\alpha ^{2})&=(a+d)+(b+e)\alpha +(c+f)\alpha ^{2}\\(a+b\alpha +c\alpha ^{2})(d+e\alpha +f\alpha ^{2})&=(ad+bf+ce)+(ae+bd+bf+ce+cf)\alpha +(af+be+cd+cf)\alpha ^{2}\end{aligned}}}$$

GF(16)

多項式は上で既約、つまり を法として既約です。したがって、 の元は式で表すことができます。ここでは または(の元) のいずれかであり、は となる記号です (つまり、 は与えられた既約多項式の根として定義されます)。 の特性はであるため、各元は におけるその加法逆元です。 における加算と乗算は次のように定義できます。次の式で、ラテン文字で表された の元間の演算はにおける演算です。 $${\displaystyle X^{4}+X+1}$$ ${\displaystyle \mathrm {GF} (2)}$ ${\displaystyle 2}$ ${\displaystyle \mathrm {GF} (16)}$ $${\displaystyle a+b\alpha +c\alpha ^{2}+d\alpha ^{3},}$$ ${\displaystyle a,b,c,d}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle \mathrm {GF} (2)}$ ${\displaystyle \alpha }$ $${\displaystyle \alpha ^{4}=\alpha +1}$$ ${\displaystyle \alpha }$ ${\displaystyle \mathrm {GF} (2)}$ ${\displaystyle 2}$ ${\displaystyle \mathrm {GF} (16)}$ ${\displaystyle \mathrm {GF} (16)}$ ${\displaystyle \mathrm {GF} (2)}$ ${\displaystyle \mathrm {GF} (2)}$ $${\displaystyle {\begin{aligned}(a+b\alpha +c\alpha ^{2}+d\alpha ^{3})+(e+f\alpha +g\alpha ^{2}+h\alpha ^{3})&=(a+e)+(b+f)\alpha +(c+g)\alpha ^{2}+(d+h)\alpha ^{3}\\(a+b\alpha +c\alpha ^{2}+d\alpha ^{3})(e+f\alpha +g\alpha ^{2}+h\alpha ^{3})&=(ae+bh+cg+df)+(af+be+bh+cg+df+ch+dg)\alpha \;+\\&\quad \;(ag+bf+ce+ch+dg+dh)\alpha ^{2}+(ah+bg+cf+de+dh)\alpha ^{3}\end{aligned}}}$$

体には8つの原始元（ の非零元すべてが整数乗となる元）があります。これらの元は の4つの根とその逆元です。特に、は原始元であり、原始元はより小さく、と互いに素です（つまり、1、2、4、7、8、11、13、14）。 ${\displaystyle \mathrm {GF} (16)}$ ${\displaystyle \mathrm {GF} (16)}$ ${\displaystyle X^{4}+X+1}$ ${\displaystyle \alpha }$ ${\displaystyle \alpha ^{m}}$ ${\displaystyle m}$ ${\displaystyle 15}$

乗法構造

の非零元の集合は、乗法 の下で の位数 のアーベル群である。ラグランジュの定理によれば、 の任意の非零元 に対して となるようなの約数が存在する。この方程式は任意の体で最大 個の解を持つため、 は に対して取り得る最小の値である。有限アーベル群の構造定理は、この乗法群が巡回 であること、つまりすべての非零元が単一の元の冪乗であることを意味する。まとめると、 ${\displaystyle \mathrm {GF} (q)}$ ${\displaystyle q-1}$ ${\displaystyle k}$ ${\displaystyle q-1}$ ${\displaystyle x^{k}=1}$ ${\displaystyle x}$ ${\displaystyle \mathrm {GF} (q)}$ ${\displaystyle x^{k}=1}$ ${\displaystyle k}$ ${\displaystyle q-1}$ ${\displaystyle k}$

の非ゼロ元の乗法群は巡回的です。つまり、 の非ゼロ元がとなるような元 が存在します。 ${\displaystyle \mathrm {GF} (q)}$ ${\displaystyle a}$ ${\displaystyle q-1}$ ${\displaystyle \mathrm {GF} (q)}$ ${\displaystyle a,a^{2},\ldots ,a^{q-2},a^{q-1}=1}$

このような元はの原始元と呼ばれます。 でない限り、原始元は一意ではありません。原始元の数は 個です。ここではオイラーのトーティエント関数です。 ${\displaystyle a}$ ${\displaystyle \mathrm {GF} (q)}$ ${\displaystyle q=2,3}$ ${\displaystyle \phi (q-1)}$ ${\displaystyle \phi }$

上記の結果は、の任意の に対してが成り立つことを意味します。 が素数である特別なケースは、フェルマーの小定理です。 ${\displaystyle x^{q}=x}$ ${\displaystyle x}$ ${\displaystyle \mathrm {GF} (q)}$ ${\displaystyle q}$

離散対数

が の原始元である場合、 の任意の非零元に対して、を満たす唯一の整数が存在し、 となる。この整数はを底とするの離散対数と呼ばれる。 ${\displaystyle a}$ ${\displaystyle \mathrm {GF} (q)}$ ${\displaystyle x}$ ${\displaystyle F}$ ${\displaystyle n}$ ${\displaystyle 0\leq n\leq q-2}$ ${\displaystyle x=a^{n}}$ ${\displaystyle n}$ ${\displaystyle x}$ ${\displaystyle a}$

は、例えばを二乗するべき乗法などを用いて非常に高速に計算できますが、その逆演算である離散対数を計算する効率的なアルゴリズムは知られていません。これは様々な暗号プロトコルで使用されています。詳細は離散対数を参照してください。 ${\displaystyle a^{n}}$

の非零元を離散対数で表すと、乗算と除算は を法とする加算と減算に簡約されるため簡単です。しかし、加算は の離散対数を計算することになります。この恒等式 により、の離散対数の表（ツェッヒ対数）を作成することでこの問題を解くことができます。これは に対して適用されます（零の離散対数を と定義すると便利です）。 ${\displaystyle \mathrm {GF} (q)}$ ${\displaystyle q-1}$ ${\displaystyle a^{m}+a^{n}}$ $${\displaystyle a^{m}+a^{n}=a^{n}\left(a^{m-n}+1\right)}$$ ${\displaystyle a^{n}+1}$ ${\displaystyle n=0,\ldots ,q-2}$ ${\displaystyle -\infty }$

ゼクの対数は、中規模体上の線型代数などの大規模な計算に役立ちます。中規模体とは、自然なアルゴリズムを非効率的にするほど十分に大きいが、体の位数と同じサイズのテーブルを事前に計算する必要があるため大きすぎない体です。

団結の根源

有限体のすべての非ゼロ元は1 の根であり、のすべての非ゼロ元も同様です。 ${\displaystyle x^{q-1}=1}$ ${\displaystyle \mathrm {GF} (q)}$

が正の整数である場合、番目の原始単位根は、任意の正の整数 に対して方程式の解ではない方程式の解です。が体 における 番目の原始単位根である場合、 にはすべての単位根、つまりが含まれます。 ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle x^{n}=1}$ ${\displaystyle x^{m}=1}$ ${\displaystyle m<n}$ ${\displaystyle a}$ ${\displaystyle n}$ ${\displaystyle F}$ ${\displaystyle F}$ ${\displaystyle n}$ ${\displaystyle 1,a,a^{2},\ldots ,a^{n-1}}$

体が の約数である場合に限り、 の 乗根を含む。が の約数である場合、における 乗根の数はである（オイラーのトーティエント関数）。における 乗根の数はである。 ${\displaystyle \mathrm {GF} (q)}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle q-1}$ ${\displaystyle n}$ ${\displaystyle q-1}$ ${\displaystyle n}$ ${\displaystyle \mathrm {GF} (q)}$ ${\displaystyle \phi (n)}$ ${\displaystyle n}$ ${\displaystyle \mathrm {GF} (q)}$ ${\displaystyle \mathrm {gcd} (n,q-1)}$

特性体 において、任意の 分の 1 根は 分の 1 根でもある。したがって、特性体 において原始 分の 1 根は決して存在しない。 ${\displaystyle p}$ ${\displaystyle np}$ ${\displaystyle n}$ ${\displaystyle np}$ ${\displaystyle p}$

一方、 がと互いに素である場合、番目の円分多項式の根はの特性を持つすべての体において異なる。これは、この多項式が の約数であり、その判別式がを法として非ゼロとなるためである。したがって、番目の円分多項式は を に因数分解して、すべて同じ次数を持つ異なる既約多項式、例えば に分解でき、これは番目の原始単位根を含む最小の特性体である。 ${\displaystyle n}$ ${\displaystyle p}$ ${\displaystyle n}$ ${\displaystyle p}$ ${\displaystyle X^{n}-1}$ ${\displaystyle n^{n}}$ ${\displaystyle p}$ ${\displaystyle n}$ ${\displaystyle \mathrm {GF} (q)}$ ${\displaystyle d}$ ${\displaystyle \mathrm {GF} (p^{d})}$ ${\displaystyle p}$ ${\displaystyle n}$

ブラウアー指標を計算する際には、写像を用いて表現行列の固有値を複素数に写像する。この写像の下では、基底部分体は単位円（零点は除く）の周囲に等間隔に配置された点から構成される。 ${\displaystyle \alpha ^{k}\mapsto \exp(2\pi ik/(q-1))}$ ${\displaystyle \mathrm {GF} (p)}$

有限体F_25を複素根への写像で表す。基底部分体F_5は赤で示されている。

例: GF(64)

体には、より小さな体が共有していない興味深い特性がいくつかあります。つまり、どちらも他方に含まれない 2 つの部分体があること、すべての生成元 (上の次数の最小多項式を持つ元) が原始元であるとは限らないこと、そして、原始元がガロア群の下ですべて共役であるとは限らないことです。 ${\displaystyle \mathrm {GF} (64)}$ ${\displaystyle 6}$ ${\displaystyle \mathrm {GF} (2)}$

この体の位数は2 ⁶、6の約数は1、2、3、6であるため、 GF(64)の部分体はGF(2)、GF(2 ² ) = GF(4)、GF(2 ³ ) = GF(8)、そしてGF(64)自身である。2と3は互いに素であるため、GF(64 )におけるGF(4)とGF(8)の交点は素体GF(2)となる。

したがって、 GF(4)とGF(8)の和集合は10個の元を持つ。GF (64)の残りの54個の元は、他の部分体に含まれないという意味でGF(64)を生成する。したがって、これらはGF(2)上の6次既約多項式の根となる。これは、 GF(2)上に、ちょうど9個の = ⁠が存在することを意味する。54/6⁠ 6次の既約単項多項式。これはX ⁶⁴ − XをGF(2)で因数分解することで検証できる。

GF(64)の元は、を割り切る何らかの n に対して原始n 乗根である。 3 乗根と 7 乗根はそれぞれGF(4)とGF(8)に属するため、54 個の生成元は、 {9, 21, 63}に含まれる何らかのnに対して原始n乗根である。オイラーのトーティエント関数によれば、原始9乗根、原始1 乗根、原始63乗根がそれぞれ6 個存在する。これらの数を合計すると、再び元が求められる。 ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle 63}$ ${\displaystyle 12}$ ${\displaystyle 21}$ ${\displaystyle 36}$ ${\displaystyle 54}$

円分多項式を因数分解すると、次のことがわかります。 ${\displaystyle \mathrm {GF} (2)}$

• 6 つの原始th 根は の根であり、すべてガロア群の作用の下で共役です。 ${\displaystyle 9}$ $${\displaystyle X^{6}+X^{3}+1,}$$
• 12個の原始平方根は、ガロア群の作用下で2つの軌道を形成する平方根である。2つの因数は互いに逆数であるため、平方根とその（乗法的）逆根は同じ軌道には属さない。 ${\displaystyle 21}$ $${\displaystyle (X^{6}+X^{4}+X^{2}+X+1)(X^{6}+X^{5}+X^{4}+X^{2}+1).}$$
• の原始元はの根です。これらはガロア群の作用により、それぞれ 6 つの元からなる 6 つの軌道に分割されます。 ${\displaystyle 36}$ ${\displaystyle \mathrm {GF} (64)}$ $${\displaystyle {\begin{aligned}&(X^{6}+X^{4}+X^{3}+X+1)(X^{6}+X+1)(X^{6}+X^{5}+1)\cdot {}\\&\qquad (X^{6}+X^{5}+X^{3}+X^{2}+1)(X^{6}+X^{5}+X^{2}+X+1)(X^{6}+X^{5}+X^{4}+X+1).\end{aligned}}}$$

これは、 GF(2)[ X ] / ( X ⁶ + X + 1)と定義するのが最良の構築方法であることを示しています。実際、この生成元は原始元であり、この多項式は最も簡単なユークリッド除算を生成する既約多項式です。 ${\displaystyle \mathrm {GF} (64)}$

フロベニウスの自己同型性とガロア理論

このセクションでは、は素数、 はの累乗です。 ${\displaystyle p}$ ${\displaystyle q=p^{n}}$ ${\displaystyle p}$

において、恒等写像( x + y ) ^p = x ^p + y ^{p は}、写像が の-線型自己準同型であり、部分体 のすべての元を固定する体自己同型であることを意味する。これはフェルディナント・ゲオルク・フロベニウスにちなんでフロベニウス自己同型と呼ばれる。 ${\displaystyle \mathrm {GF} (q)}$ $${\displaystyle \varphi :x\mapsto x^{p}}$$ ${\displaystyle \mathrm {GF} (p)}$ ${\displaystyle \mathrm {GF} (q)}$ ${\displaystyle \mathrm {GF} (p)}$

φ ^kをφ自身とのk回の合成と表記すると、次式が成り立ちます 。前の節で示したように、φ ^{n は}恒等写像です。0 < k < nの場合、自己同型φ ^kは恒等写像ではありません。そうでなければ、多項式は p ^k個 以上の根を持つことになります。 $${\displaystyle \varphi ^{k}:x\mapsto x^{p^{k}}.}$$ $${\displaystyle X^{p^{k}}-X}$$

GF( q )には他のGF( p ) -自己同型は存在しない。言い換えれば、GF( p ⁿ )にはちょうどn 個のGF( p ) -自己同型が存在し、それらは $${\displaystyle \mathrm {Id} =\varphi ^{0},\varphi ,\varphi ^{2},\ldots ,\varphi ^{n-1}.}$$

ガロア理論の観点から言えば、これはGF( p ⁿ )がGF( p )のガロア拡大であり、巡回ガロア群を持つことを意味します。

フロベニウス写像が射影的であるという事実は、すべての有限体が完全であることを意味します。

多項式因数分解

Fが有限体である場合、 Fに係数を持つ非定数モニック多項式は、それがFに係数を持つ 2 つの非定数モニック多項式の積でなければ、F上で既約です。

体上のすべての多項式環は一意の因数分解領域であるため、有限体上のすべてのモニック多項式は一意の方法（因数の順序まで）で既約モニック多項式の積に因数分解できます。

多項式の既約性を検証し、有限体上の多項式を因数分解するための効率的なアルゴリズムが存在します。これらは、整数または有理数上の多項式を因数分解するための重要なステップです。少なくともこの理由から、すべてのコンピュータ代数システムは、有限体上、あるいは少なくとも有限素体上の多項式を因数分解する関数を備えています。

与えられた次数の既約多項式

この多項式はq 位の体上の線型因子に因数分解されます。より正確には、この多項式はq位の体上のすべての 1 次モニック多項式の積です。 $${\displaystyle X^{q}-X}$$

これは、q = p ⁿの場合、X ^q − Xは、次数がnを割り切るGF( p )上のすべてのモニック既約多項式の積であることを意味します。実際、PがX ^q − XのGF( p )上の既約因子である場合、その分解体はGF( p ⁿ )に含まれるため、その次数はn を割り切ります。逆に、P がnを割り切る次数dのGF( p )上の既約モニック多項式である場合、それはGF( p ⁿ )に含まれる次数dの体拡大を定義し、 Pのすべての根はGF( p ⁿ )に属し、X ^q − Xの根です。したがって、P はX ^q − Xを割り切ります。X ^q − Xには多重因数がないため、それを割り切るすべての既約モニック多項式の積になります。

この特性はGF( p )上の各次数の多項式における既約因数の積を計算するために使用されます。 「異なる次数因数分解」を参照してください。

有限体上の与えられた次数のモニック既約多項式の数

GF( q )上の n次のモニック既約多項式の個数N ( q , n )は^[7]で与えられる。ここでμはメビウス関数^である。この式は、上記のXq − Xの性質とメビウスの反転公式から直接導かれる。 $${\displaystyle N(q,n)={\frac {1}{n}}\sum _{d\mid n}\mu (d)q^{n/d},}$$

上記の式により、 GF( q )上のn次の既約な（必ずしもモニックではない）多項式の数は( q −1) N ( q , n )となる。

正確な式は、不等式が鋭い場合、かつn が素数のべき乗である場合に限る、ということを示唆する。任意のqおよび任意のnに対して、右辺は正となるため、GF( q )上に少なくとも1つのn次既約多項式が存在する。 $${\displaystyle N(q,n)\geq {\frac {1}{n}}{\biggl (}q^{n}-\sum _{\ell \mid n,\ \ell {\text{ prime}}}q^{n/\ell }{\biggr )};}$$

アプリケーション

暗号学において、有限体または有限体上の楕円曲線における離散対数問題の難しさは、 Diffie-Hellmanプロトコルなど、広く用いられているいくつかのプロトコルの基礎となっています。例えば、2014年には、Wikipediaへの安全なインターネット接続に、大規模な有限体上の楕円曲線Diffie-Hellmanプロトコル（ ECDHE ）が利用されました。 ^[8]符号理論において、多くの符号は有限体上のベクトル空間の部分空間として構築されます。

有限体は、リード・ソロモン誤り訂正符号やBCH符号など、多くの誤り訂正符号で用いられています。コンピュータデータは2進数で保存されるため、有限体の標数はほぼ常に2です。例えば、1バイトのデータはGF(2 ⁸ )の元として解釈できます。唯一の例外はPDF417バーコードで、 GF(929)です。一部のCPUには、標数2の有限体（一般的にはキャリーレス積のバリエーション）に有用な特別な命令が搭載されています。

有限体は整数論において広く用いられており、整数に関する多くの問題は、1つまたは複数の素数を法として簡約することで解くことができる。例えば、有理数体上の多項式因数分解や線型代数に関する既知の最速アルゴリズムは、1つまたは複数の素数を法として簡約し、その後、中国式剰余定理、ヘンゼルのリフティング、またはLLLアルゴリズムを用いて解を再構成する。

同様に、数論における多くの理論的問題は、一部またはすべての素数を法とする還元を考えることで解決できます。例えば、ハッセ原理を参照してください。代数幾何学における近年の多くの発展は、こうしたモジュラー手法の威力を高める必要性から生まれました。ワイルズによるフェルマーの最終定理の証明は、有限体を含む多くの数学的ツールを駆使した深い結果の例です。

ヴェイユ予想は、有限体上の代数多様体上の点の数に関するもので、その理論は指数和や指標和の推定を含む多くの応用がある。

有限体は組合せ論において広く応用されており、よく知られた例としては、ペイリーグラフの定義とそれに関連するアダマール行列の構成が挙げられる。算術組合せ論においては、有限体^[9]と有限体モデル^{[10] [11]が、}セメレディの等差数列に関する 定理などにおいて広く用いられている。

拡張機能

ウェダーバーンの小定理

除算環は体の一般化である。除算環は可換であるとは仮定されない。非可換な有限除算環は存在しない。ウェダーバーンの小定理は、すべての有限除算環は可換であり、したがって有限体であると述べている。この結果は、結合性公理を交替性に緩和した場合でも成立する。つまり、アルティン・ツォルンの定理により、すべての有限代替除算環は有限体となる。^[12]

代数的閉包

有限体は代数的に閉じていません。のすべての場合においてf  ( α ) = 1であるため、多項式はに根を持ちません。 ${\displaystyle F}$ $${\displaystyle f(T)=1+\prod _{\alpha \in F}(T-\alpha ),}$$ ${\displaystyle F}$ ${\displaystyle \alpha }$ ${\displaystyle F}$

素数pが与えられたとき、の代数閉包とします。これは、すべての代数閉包と同様に同型を除いて一意であるだけでなく、一般の場合とは逆に、そのすべての部分体はそのすべての自己同型によって固定され、同じ特性pのすべての有限体の代数閉包でもあります。 ${\displaystyle {\overline {\mathbb {F} }}_{p}}$ ${\displaystyle \mathbb {F} _{p}.}$

この特性は主に、 の要素がの根とまったく同じであり、の包含を定義することから生じます。これらの包含により、非公式に と書くことが可能になります。この表記法の正式な妥当性は、上記のフィールド包含がフィールドの有向集合を形成することから生じます。その直接的な極限は であり、これは「有向和集合」と見なすことができます。 ${\displaystyle \mathbb {F} _{p^{n}}}$ ${\displaystyle x^{p^{n}}-x,}$ ${\displaystyle \mathbb {\mathbb {F} } _{p^{n}}\subset \mathbb {F} _{p^{nm}}}$ ${\displaystyle m>1.}$ $${\displaystyle {\overline {\mathbb {F} }}_{p}=\bigcup _{n\geq 1}\mathbb {F} _{p^{n}}.}$$ ${\displaystyle {\overline {\mathbb {F} }}_{p},}$

代数閉包における原始要素

の原始元 が与えられたとき、の原始元は ${\displaystyle g_{mn}}$ ${\displaystyle \mathbb {F} _{q^{mn}},}$ ${\displaystyle g_{mn}^{m}}$ ${\displaystyle \mathbb {F} _{q^{n}}.}$

明示的な計算では、すべての有限体に対して一貫した原始元を選択することが有用である。つまり、 の原始元を、 が既に選択された原始元である場合に常に、 となるように選択する。 ${\displaystyle g_{n}}$ ${\displaystyle \mathbb {F} _{q^{n}}}$ ${\displaystyle n=mh,}$ ${\displaystyle g_{m}=g_{n}^{h},}$ ${\displaystyle g_{m}}$ ${\displaystyle \mathbb {F} _{q^{m}}.}$

このような構成はコンウェイ多項式によって得られるかもしれない。

準代数的閉包

有限体は代数的に閉じていないが、準代数的に閉じている。これは、有限体上の任意の斉次多項式には、変数の数が次数よりも多い場合に、その成分が体に含まれる非自明な零点が存在することを意味する。これはアルティンとディクソンの予想であり、シュヴァレーによって証明された（シュヴァレー・ワーニング定理を参照）。

参照

• 基本アーベル群
• 1つの要素を持つフィールド
• 有限体演算
• 有限環
• 有限群
• ガロア環
• ハミング空間
• 準有限体

注記

1. ダミット, デイビッド・スティーブン; フット, リチャード・M. (2004).抽象代数（第3版）. ホーボーケン, ニュージャージー: ワイリー. ISBN 978-0-471-43334-7。
2. Moore, EH (1896)、「単純群の二重無限系」、EH Moore他編『コロンビア万国博覧会関連国際数学会議数学論文集』 、Macmillan & Co.、 208～ 242頁 
3. この後者の表記法は、 1893年にシカゴで開催された国際数学会議におけるEHムーアの演説で導入されました（Mullen & Panario 2013、p. 10）。
4. アルフィ、パオロ (2009).代数学：第0章. アメリカ数学会. p. 439. ISBN 978-0-8218-4781-7。
5. Xiang-dong Hou (2018)、「有限体に関する講義」、数学大学院、プロビデンス、ロードアイランド：アメリカ数学会、p. 2
6. 政府使用のための推奨楕円曲線(PDF)、米国国立標準技術研究所、1999年7月、p. 3、2008年7月19日時点のオリジナルからアーカイブ(PDF)
7. ジェイコブソン 2009, §4.13
8. ほとんどのブラウザでは、URLの横に表示されるロッカーをクリックして表示されるセキュリティ情報を確認することで、この情報を確認できます。2025年現在でも、 Wikipediaのデジタル証明書には、暗号アルゴリズムに「楕円曲線」が使用されていると記載されています。
9. Shparlinski, Igor E. (2013)、「有限体上の加法組合せ論：新しい結果と応用」、有限体とその応用、DE GRUYTER、pp.  233– 272、doi :10.1515/9783110283600.233、ISBN 9783110283600
10. Green, Ben (2005)、「加法組合せ論における有限体モデル」、Surveys in Combinatorics 2005、ケンブリッジ大学出版局、pp.  1– 28、arXiv : math/0409420、doi :10.1017/cbo9780511734885.002、ISBN 9780511734885、S2CID  28297089
11. Wolf, J. (2015年3月). 「算術的組合せ論における有限体モデル ― 10年後」.有限体とその応用. 32 : 233–274 . doi : 10.1016/j.ffa.2014.11.003 . hdl : 1983/d340f853-0584-49c8-a463-ea16ee51ce0f . ISSN  1071-5797.
12. Shult, Ernest E. (2011).点と線. 古典幾何学の特徴. Universitext. ベルリン: Springer-Verlag . p. 123. ISBN 978-3-642-15626-7. Zbl  1213.51001。

参考文献

• WH Bussey (1905)「p ⁿ ≤ 169のガロア体表」アメリカ数学会報12(1): 22–38, doi :10.1090/S0002-9904-1905-01284-2
• WH Bussey (1910)「位数<1000のガロア体の表」アメリカ数学会報16(4): 188–206, doi :10.1090/S0002-9904-1910-01888-7
• ジェイコブソン、ネイサン(2009) [1985]、基礎代数 I (第 2 版)、ドーバー出版、ISBN 978-0-486-47189-1
• Mullen, Gary L.; Mummert, Carl (2007)、『有限体とその応用 I』、学生数学図書館 (AMS)、ISBN 978-0-8218-4418-2
• マレン、ゲイリー・L.; パナリオ、ダニエル (2013)、『有限体ハンドブック』、CRC Press、ISBN 978-1-4398-7378-6
• リドル、ルドルフ。Niederreiter、Harald (1997)、Finite Fields (第 2 版)、ケンブリッジ大学出版局、ISBN 0-521-39231-4
• Skopin, AI (2001) [1994]、「ガロア体」、数学百科事典、EMS Press

外部リンク

• Wolfram Research の有限体。
• 有限体とその応用、Science Direct、（オープンアクセスジャーナル）。

Retrieved from "https://en.wikipedia.org/w/index.php?title=Finite_field&oldid=1320719858"