有限体
有限体（ゆうげんたい、英語：finite field）とは、代数学において、有限個の元からなる体、すなわち四則演算が定義され閉じている有限集合のことである。主に計算機関連の分野においては、発見者であるエヴァリスト・ガロアに因んでガロア体あるいはガロア域（ガロアいき、Galois field）などとも呼ぶテンプレート:Sfn。
有限体においては、体の定義における乗法の可換性についての条件の有無は問題にはならない。実際、ウェダーバーンの小定理と呼ばれる以下の定理
- 「有限斜体は可換体である」
が成り立つことが知られている。別の言い方をすれば、有限体において乗法の可換性は、体の有限性から導かれるということである。
構成例
位数最小の有限体は集合としては Fテンプレート:Sub = Z/2Z = {0, 1} で、演算は次で定める。 これは2を法とした余りで加法と乗法を定めていると言ってもよい。
| + | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 0 |
| × | 0 | 1 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
同様の構成は一般の素数 p に対しても成り立つ。整数環 Z の p の倍数全体 pZ は素イデアルで、整数環がPIDなので、特に極大イデアル。したがって剰余環 Fテンプレート:Sub = Z/pZ は p 個の元からなる体である。
素数位数とは限らない有限体も存在する。Fテンプレート:Sub 係数一変数多項式環 Fテンプレート:Sub[x] を考える。その既約多項式 f(x) = xテンプレート:Sup + x + 1 の生成する素イデアル (f(x)) は、 Fテンプレート:Sub[x] がPIDなので、特に極大イデアル。したがって剰余環 Fテンプレート:Sub = Fテンプレート:Sub[x]/(f(x)) は 4 個の元からなる体である。変数 x の自然な全射による像を ω とおくと、Fテンプレート:Sub = {0, 1, ω, ωテンプレート:Sup} と表せ、その演算は関係式 ωテンプレート:Sup + ω + 1 = 0 から定まる。
同様の構成は一般の素数 p に対して成り立ち、任意の拡大次数 d をもつ拡大体が構成できる。そのとき次数 d の既約多項式としてはテンプレート:仮リンクを取ればよい。
構造
K を有限体とし、その位数を q とする。K の素体の位数も有限であるから、K はある素数 p に対する有限体 Fテンプレート:Sub = Z/pZ を素体として含み、素体 Fテンプレート:Sub の有限次代数拡大である。その拡大次数 [K : Fテンプレート:Sub] が n ならば、加法群として K は n 次元の Fテンプレート:Sub-ベクトル空間と同型であるので、K の位数 q は pテンプレート:Sup に一致するテンプレート:Sfn。また乗法群 Kテンプレート:Sup は位数 q − 1 の巡回群と同型であるテンプレート:Sfn。
K を含む Fテンプレート:Sub の代数閉包を (Fテンプレート:Sub)テンプレート:Sup とする。このとき K は、 (Fテンプレート:Sub)テンプレート:Sup の元で、重根を持たない方程式 xテンプレート:Sup − x = 0 を満たすものの全体として特徴付けられる。特に位数が pテンプレート:Sup の有限体は同型を除いて唯一つ存在するテンプレート:Sfn。この一意性により、位数 q の有限体を Fテンプレート:Sub または GF(q) などと表すことがある。また、有限体 Fテンプレート:Sub と自然数 m に対し Fテンプレート:Sub の m 次拡大体は唯一つ存在し、Fテンプレート:Sub と同型であるということも分かる。さらに Fテンプレート:Sub の各元の Fテンプレート:Sub 上の最小多項式は xテンプレート:Supテンプレート:Sup を割り切るので、有限体の拡大はすべて分離的である。つまり有限体は完全体である。さらに q 乗フロベニウス写像とよばれる自己同型写像
を考えると、拡大 Fテンプレート:Sub/Fテンプレート:Sub のガロア群 Gal(Fテンプレート:Sub/Fテンプレート:Sub) = Autテンプレート:Sub(Fテンプレート:Sub) はフロベニウス写像で生成される。つまり、
と表されるテンプレート:Sfn。したがって、有限体の拡大はすべて巡回拡大であるガロア拡大である。
有限体は代数的閉体でありえない。
有限体 Fテンプレート:Sub の元 α, αテンプレート:Sup, …, αテンプレート:Sup が Fテンプレート:Sub 上のベクトル空間 Fテンプレート:Sub の基底をなすとき，この基底を正規基底という。正規基底は常に存在するテンプレート:Sfn。
応用
- リード・ソロモン符号など基本的なものを含む多くの誤り検出・訂正は、GF(2)、GF(2テンプレート:Sup)、GF(2テンプレート:Sup)、GF(2テンプレート:Sup)、GF(2テンプレート:Sup) などを使う。
- AES、Camelliaなど、2000年代以降の共通鍵暗号の多くは、SボックスにGF(2テンプレート:Sup) を使う。
- 楕円曲線暗号は、きわめて大きな位数の有限体、たとえばGF(2テンプレート:Sup) などを使う。
脚注
参考文献
- テンプレート:Cite book
- テンプレート:Cite book
- Igor E. Shparlinski: "Computational and Algorithmic Problems in Finite Fields", Springer (series MASS, Vol.88) (1992). DOI:10.1007/978-94-011-1806-4.
- Jenny Fuseliear et al.: Hypergeometric Functions Over Finite Fields, AMS, Memoirs, No. 1382, (2022).
関連項目
- 標数#素整域・素体
- 可換体
- CLMUL instruction set - 有限体の乗算のための命令
- 誤り検出訂正