はじめに
「情報理論と符号理論」の後半、符号理論に差し掛かって有限体が出てきた。全然分かってなかったので調べて自分なりに理解したことを記す。拡大体の基礎体となる素数位数の有限体については既知であるものとする（「ガロア体と拡大体」の解説が解り易い）。
\[
% general purpose
\newcommand{\ctext}[1]{\raise0.2ex\hbox{\textcircled{\scriptsize{#1}}}}
% mathematics
% general purpose
\DeclarePairedDelimiterX{\parens}[1]{\lparen}{\rparen}{#1}
\DeclarePairedDelimiterX{\braces}[1]{\lbrace}{\rbrace}{#1}
\DeclarePairedDelimiterX{\bracks}[1]{\lbrack}{\rbrack}{#1}
\DeclarePairedDelimiterX{\verts}[1]{|}{|}{#1}
\DeclarePairedDelimiterX{\Verts}[1]{\|}{\|}{#1}
\newcommand{\as}{{\quad\textrm{as}\quad}}
\newcommand{\st}{{\textrm{ s.t. }}}
\DeclarePairedDelimiterX{\setComprehension}[2]{\lbrace}{\rbrace}{#1\,\delimsize\vert\,#2}
\newcommand{\naturalNumbers}{\mathbb{N}}
\newcommand{\integers}{\mathbb{Z}}
\newcommand{\rationalNumbers}{\mathbb{Q}}
\newcommand{\realNumbers}{\mathbb{R}}
\newcommand{\complexNumbers}{\mathbb{C}}
\newcommand{\field}{\mathbb{F}}
\newcommand{\func}[2]{{#1}\parens*{#2}}
\newcommand*{\argmax}{\operatorname*{arg~max}}
\newcommand*{\argmin}{\operatorname*{arg~min}}
% set theory
\newcommand{\range}[2]{\braces*{#1,\dotsc,#2}}
\providecommand{\complement}{}\renewcommand{\complement}{\mathrm{c}}
\newcommand{\ind}[2]{\mathbbm{1}_{#1}\parens*{#2}}
\newcommand{\indII}[1]{\mathbbm{1}\braces*{#1}}
% number theory
\newcommand{\abs}[1]{\verts*{#1}}
\newcommand{\combi}[2]{{_{#1}\mathrm{C}_{#2}}}
\newcommand{\perm}[2]{{_{#1}\mathrm{P}_{#2}}}
\newcommand{\GaloisField}[1]{\mathrm{GF}\parens*{#1}}
% analysis
\newcommand{\NapierE}{\mathrm{e}}
\newcommand{\sgn}[1]{\operatorname{sgn}\parens*{#1}}
\newcommand*{\rect}{\operatorname{rect}}
\newcommand{\cl}[1]{\operatorname{cl}#1}
\newcommand{\Img}[1]{\operatorname{Img}\parens*{#1}}
\newcommand{\dom}[1]{\operatorname{dom}\parens*{#1}}
\newcommand{\norm}[1]{\Verts*{#1}}
\newcommand{\floor}[1]{\left\lfloor#1\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil#1\right\rceil}
\newcommand{\expo}[1]{\exp\parens*{#1}}
\newcommand{\sinc}{\operatorname{sinc}}
\newcommand{\nsinc}{\operatorname{nsinc}}
\newcommand{\GammaFunc}[1]{\Gamma\parens*{#1}}
\newcommand*{\erf}{\operatorname{erf}}
% inverse trigonometric functions
\newcommand{\asin}[1]{\operatorname{Sin}^{-1}{#1}}
\newcommand{\acos}[1]{\operatorname{Cos}^{-1}{#1}}
\newcommand{\atan}[1]{\operatorname{{Tan}^{-1}}{#1}}
\newcommand{\atanEx}[2]{\atan{\parens*{#1,#2}}}
% convolution
\newcommand{\cycConv}[2]{{#1}\underset{\text{cyc}}{*}{#2}}
% derivative
\newcommand{\deriv}[3]{\frac{\operatorname{d}^{#3}#1}{\operatorname{d}{#2}^{#3}}}
\newcommand{\derivLong}[3]{\frac{\operatorname{d}^{#3}}{\operatorname{d}{#2}^{#3}}#1}
\newcommand{\partDeriv}[3]{\frac{\operatorname{\partial}^{#3}#1}{\operatorname{\partial}{#2}^{#3}}}
\newcommand{\partDerivLong}[3]{\frac{\operatorname{\partial}^{#3}}{\operatorname{\partial}{#2}^{#3}}#1}
\newcommand{\partDerivIIHetero}[3]{\frac{\operatorname{\partial}^2#1}{\partial#2\operatorname{\partial}#3}}
\newcommand{\partDerivIIHeteroLong}[3]{{\frac{\operatorname{\partial}^2}{\partial#2\operatorname{\partial}#3}#1}}
% integral
\newcommand{\integrate}[5]{\int_{#1}^{#2}{#3}{\mathrm{d}^{#4}}#5}
\newcommand{\LebInteg}[4]{\int_{#1} {#2} {#3}\parens*{\mathrm{d}#4}}
% complex analysis
\newcommand{\conj}[1]{\overline{#1}}
\providecommand{\Re}{}\renewcommand{\Re}[1]{{\operatorname{Re}{\parens*{#1}}}}
\providecommand{\Im}{}\renewcommand{\Im}[1]{{\operatorname{Im}{\parens*{#1}}}}
\newcommand*{\Arg}{\operatorname{Arg}}
\newcommand*{\Log}{\operatorname{Log}}
% Laplace transform
\newcommand{\LPLC}[1]{\operatorname{\mathcal{L}}\parens*{#1}}
\newcommand{\ILPLC}[1]{\operatorname{\mathcal{L}}^{-1}\parens*{#1}}
% Discrete Fourier Transform
\newcommand{\DFT}[1]{\mathrm{DFT}\parens*{#1}}
% Z transform
\newcommand{\ZTrans}[1]{\operatorname{\mathcal{Z}}\parens*{#1}}
\newcommand{\IZTrans}[1]{\operatorname{\mathcal{Z}}^{-1}\parens*{#1}}
% linear algebra
\newcommand{\bm}[1]{{\boldsymbol{#1}}}
\newcommand{\matEntry}[3]{#1\bracks*{#2}\bracks*{#3}}
\newcommand{\matPart}[5]{\matEntry{#1}{#2:#3}{#4:#5}}
\newcommand{\diag}[1]{\operatorname{diag}\parens*{#1}}
\newcommand{\tr}[1]{\operatorname{tr}{\parens*{#1}}}
\newcommand{\inprod}[2]{\left\langle#1,#2\right\rangle}
\newcommand{\HadamardProd}{\odot}
\newcommand{\HadamardDiv}{\oslash}
\newcommand{\Span}[1]{\operatorname{span}\bracks*{#1}}
\newcommand{\Ker}[1]{\operatorname{Ker}\parens*{#1}}
\newcommand{\rank}[1]{\operatorname{rank}\parens*{#1}}
% vector
% unit vector
\newcommand{\vix}{\bm{i}_x}
\newcommand{\viy}{\bm{i}_y}
\newcommand{\viz}{\bm{i}_z}
% probability theory
\newcommand{\PDF}[2]{\operatorname{PDF}\bracks*{#1,\;#2}}
\newcommand{\Ber}[1]{\operatorname{Ber}\parens*{#1}}
\newcommand{\Beta}[2]{\operatorname{Beta}\parens*{#1,#2}}
\newcommand{\ExpDist}[1]{\operatorname{ExpDist}\parens*{#1}}
\newcommand{\ErlangDist}[2]{\operatorname{ErlangDist}\parens*{#1,#2}}
\newcommand{\PoissonDist}[1]{\operatorname{PoissonDist}\parens*{#1}}
\newcommand{\GammaDist}[2]{\operatorname{Gamma}\parens*{#1,#2}}
\newcommand{\cind}[2]{\ind{#1\left| #2\right.}} % conditional indicator function
\providecommand{\Pr}{}\renewcommand{\Pr}[1]{\operatorname{Pr}\parens*{#1}}
\DeclarePairedDelimiterX{\cPrParens}[2]{(}{)}{#1\,\delimsize\vert\,#2}
\newcommand{\cPr}[2]{\operatorname{Pr}\cPrParens{#1}{#2}}
\newcommand{\E}[2]{\operatorname{E}_{#1}\bracks*{#2}}
\newcommand{\cE}[3]{\E{#1}{\left.#2\right|#3}}
\newcommand{\Var}[2]{\operatorname{Var}_{#1}\bracks*{#2}}
\newcommand{\Cov}[2]{\operatorname{Cov}\bracks*{#1,#2}}
\newcommand{\CovMat}[1]{\operatorname{Cov}\bracks*{#1}}
% graph theory
\newcommand{\neighborhood}{\mathcal{N}}
% programming
\newcommand{\plpl}{\mathrel{++}}
\newcommand{\pleq}{\mathrel{+}=}
\newcommand{\asteq}{\mathrel{*}=}
\]
構成法
\[
\newcommand{\GF}{\mathrm{GF}}
\]
$p$ を素数とする。$\GF(p^n)$ すなわち「$\GF(p)$ の $n$ 次拡大体」とは、$\GF(p)$ を係数体とする $n-1$ 次以下の多項式の集合であり、 $n$ 次既約多項式（例えば $p=2,\;n=3$ の場合 $x^3+x+1$ や $x^3+x^2+1$ がある）を法とした余りで加法と乗法が定義される。
位数が $p^n$ であること
第 $0,1,2,\dots,n-1$ 次の項の係数がそれぞれ $0,1,2,\dots,p-1$ であるから、$p^n$ 個の元がある。
体を成すこと
$\GF(p^n)$ が加法に関して可換群であり、乗法に関してモノイドであり可換であること、乗法が加法の上で分配的であることは簡単にわかる。あとは任意の非零元に乗法に関する逆元が存在することを確かめれば良い。$f(x)$ を $\GF(p^n)$ の任意の非零元とし、$g(x)$ を、$\GF(p)$ を係数体とする $n$ 次既約多項式とすると、$f$ と $g$ は互いに素だから「ベズーの等式」が示すように、$\GF(p)$ を係数体とする多項式 $a(x),b(x)$ が存在して
\[a(x)f(x) + b(x)g(x) = 1\]
が成り立つ。左辺第2項は $b(x)g(x) \equiv 0\;(\textrm{mod }g(x))$ なので
\[a(x)f(x) \equiv 1\;(\textrm{mod }g(x))\]
よって次式が成り立つ。（%は余りを表す）
\[(a(x)\%g(x))f(x) \equiv a(x)f(x) \equiv 1 \;(\textrm{mod }g(x))\]
従って $a(x)\%g(x)$ が $f(x)$ の逆元である。例えば 「ガロア体と拡大体」 の「多項式上での演算」の 3 つ目の表には2行目以降の全ての行に 1 のマスが存在する。これに対応する元同士が互いに逆元になっている。
原始多項式
「原始多項式」に述べられているが、 $\GF(p)$ 上の $m\in\naturalNumbers$ 次の既約多項式 $p(x)$ が原始多項式であることは、 $x^n-1\;(n\in\naturalNumbers)$ が $p(x)$ で割り切れる最小の $n$ が $p^m-1$ であることと同値である。
原始多項式と生成元
次の命題は真である。
$\GF(p)$ 上の $m\in\naturalNumbers$ 次の既約多項式 $p(x)$ が原始多項式である $\iff\quad p(x)$ を既約多項式に選んで構成された $\GF(p^m)$ に於いて $x$ が生成元である
導出
Proof
($\Rightarrow$)
集合 $S_0\coloneqq\{x,x^2,x^3,\dots,x^{p^m-2}\}$ の元が 0, 1 いずれとも合同でなく、かつ互いに異なることを示す。
$S_0$ の元が 1 でないことは原始多項式の定義から明らかである。
$S_0$ の元が 0 でないことは背理法で示せる。仮にある $k\in\{1,2,\dots,p^m-2\}$ について $x^k\equiv 0$ なら $x^l\equiv 0\;(l\in\naturalNumbers,\;l\geq k)$ であるから $x^{p^m-1}\equiv 1$ に矛盾する。
$S_0$ の元が互いに異なることも背理法で示せる。仮に $a,b\in\naturalNumbers,\;p^m-2\geq b>a\geq1$ が存在して $x^b\equiv x^a$ であるとすると $x^a(x^{b-a}-1)\equiv 0$ である。原始多項式の定義から $x^{b-a}-1\not\equiv 0$ なので $x^a\equiv 0$ であるが、これは先程示した「$S_0$ の元が 0 でない」に矛盾する。
以上より $\{0,1\}\cup S_0$ の要素は互いに異なり、要素数は $p^m-1$ であるから $x$ は $\GF(p^m)$ の生成元である。
($\Leftarrow$)
前提から集合 $S\coloneqq\{0,1,x,x^2,x^3,\dots,x^{p^m-2}\}$ の要素は互いに異なる（☆1）。
まず $x^{p^m-1}\not\equiv 0$ を背理法で示す。仮に $x^{p^m-1}\equiv 0$ とすると $x^{p^m-2}x\equiv 0$ であり、☆1 から $x^{p^m-2}\not\equiv 0$ なので $x\equiv 0$ となり☆1 に矛盾する。
次に $x^{p^m-1}\not\in S\setminus\{0,1\}$ を背理法で示す。仮にある $a\in\{1,2,\dots,p^m-2\}$ が存在して $x^{p^m-1}\equiv x^a$ であるとすると、 $x^a(x^{p^m-1-a}-1)\equiv 0$ であるが☆1 から $x^{p^m-1-a}-1\not\equiv 0$ なので $x^a\equiv 0$ となり☆1 に矛盾する。
$x$ が $\GF(p^m)$ の生成元であるから $x^{p^m-1}$ は必ず $S$ の要素のいずれかと合同である。このことと、以上に示したことから $x^{p^m-1}\equiv 1$ である。
$\square$
投稿者: motchy
An embedded software and FPGA engineer for measuring instrument.
motchy のすべての投稿を表示
