※注意: 本記事では厳密な数学的な証明等は行いません。

有限体はガロア体とも呼ばれます。

有限体は簡単に言うと「数が有限個しか存在しないが四則演算ができる世界」です。

有限体上では $2 \times 8 = 3$ や $2 \times 9 = 1$、$9 + 9 = 0$ 等の計算結果になることがあります。

初めて見ると不思議な感じがしますが、通常の四則演算と異なる計算結果になります。

1. 有限体 GF(2⁴) の例

1.1. 有限体上で使える数

有限体 $GF(2^4)$ 上では数は $0$ から $15$ の整数のみを使うことができます。

有限体で使える数はべき乗 $\alpha^i$ を用いて

\begin{align}
\alpha^0 &= 1 \\
\alpha^1 &= 2 \\
\alpha^2 &= 4 \\
\alpha^3 &= 8
\end{align}

のように表現できます。

ここで $\alpha^4 = 16$ としたいところですが、前述の通り有限体 $GF(2^4)$ 上では $16$ という数は使うことができないため、他の数になります。

足し算および引き算は排他的論理和で実現します。足し算と引き算は同じ計算結果になります。

ここで、原始多項式を $x^4 + x + 1$ とすると、

\alpha^4 + \alpha^1 + \alpha^0 = 0

\begin{align}
\alpha^4 &= 0 - \alpha^1 - \alpha^0 \\
&= \alpha^1 + \alpha^0 \\
&= 2 + 1 \\
&= 3
\end{align}

となり、$\alpha^4 = 3$ と求めることができます。

同様に計算すると

\begin{align}
\alpha^0 &= 1 \\
\alpha^1 &= 2 \\
\alpha^2 &= 4 \\
\alpha^3 &= 8 \\
\alpha^4 &= 3 \\
\alpha^5 &= 6 \\
\alpha^6 &= 12 \\
\alpha^7 &= 11 \\
\alpha^8 &= 5 \\
\alpha^9 &= 10 \\
\alpha^{10} &= 7 \\
\alpha^{11} &= 14 \\
\alpha^{12} &= 15 \\
\alpha^{13} &= 13 \\
\alpha^{14} &= 9 \\
\alpha^{15} &= 1
\end{align}

という結果になります。

$\alpha^0$ から $\alpha^{14}$ まで値は重複せず、$\alpha^{15} = 1$ になります。

このまま計算を続けても数 $0$ は得られないため、別途 $\alpha^{-\infty} = 0$ とします。

地道に式変形してもこれらの結果は得られますが、式の係数をビットとして見てビット演算を行うことでも計算できます。

有限体で使える数はべき乗 $\alpha^i$ および 2 進数を用いて

\begin{align}
\alpha^0 &= 0001_{(2)} = 1 \\
\alpha^1 &= 0010_{(2)} = 2 \\
\alpha^2 &= 0100_{(2)} = 4 \\
\alpha^3 &= 1000_{(2)} = 8
\end{align}

のように表現でき、原始多項式は $x^4 + x + 1$ より

\alpha^4 + \alpha^1 + \alpha^0 = 10011_{(2)} = 0

\begin{align}
\alpha^4 &= 10000_{(2)} \\
&= 10000_{(2)} + 10011_{(2)} \\
&= 0011_{(2)} \\
&= 3
\end{align}

と計算できます。

同様に計算すると

\begin{align}
\alpha^0 &= 0001_{(2)} = 1 \\
\alpha^1 &= 0010_{(2)} = 2 \\
\alpha^2 &= 0100_{(2)} = 4 \\
\alpha^3 &= 1000_{(2)} = 8 \\
\alpha^4 &= 0011_{(2)} = 3 \\
\alpha^5 &= 0110_{(2)} = 6 \\
\alpha^6 &= 1100_{(2)} = 12 \\
\alpha^7 &= 1011_{(2)} = 11 \\
\alpha^8 &= 0101_{(2)} = 5 \\
\alpha^9 &= 1010_{(2)} = 10 \\
\alpha^{10} &= 0111_{(2)} = 7 \\
\alpha^{11} &= 1110_{(2)} = 14 \\
\alpha^{12} &= 1111_{(2)} = 15 \\
\alpha^{13} &= 1101_{(2)} = 13 \\
\alpha^{14} &= 1001_{(2)} = 9 \\
\alpha^{15} &= 0001_{(2)} = 1
\end{align}

となります。

$\alpha^0$ から $\alpha^{14}$ まで値は重複せず、$\alpha^{15} = 0001_{(2)} = 1$ になります。

数 $0$ は別途 $\alpha^{-\infty} = 0000_{(2)} = 0$ とします。

1.2. 有限体上の四則演算

足し算と引き算は排他的論理和、掛け算と割り算はべき乗 $\alpha^i$ の形にして $\alpha^{15} = 1$ を利用すると計算できます。

掛け算と割り算は数をべき乗の形にすれば

\begin{align}
\alpha^i \times \alpha^j &= \alpha^{i+j} \\
\alpha^i \div \alpha^j &= \alpha^{i-j}
\end{align}

という直感的な計算ができます。

例えば

\begin{align}
7 + 7 &= 0111_{(2)} + 0111_{(2)} = 0000_{(2)} = 0 \\
5 + 3 &= 0101_{(2)} + 0011_{(2)} = 0110_{(2)} = 6 \\
5 - 3 &= 0101_{(2)} - 0011_{(2)} = 0110_{(2)} = 6 \\
6 \times 4 &= \alpha^{5\phantom{0}} \times \alpha^{2\phantom{0}} = \alpha^{7\phantom{0}} = 11 \\
8 \times 9 &= \alpha^{3\phantom{0}} \times \alpha^{14} = \alpha^{17} = \alpha^{15} \times \alpha^2 = \alpha^2 = 4 \\
9 \div 3 &= \alpha^{14} \div \alpha^{4\phantom{0}} = \alpha^{10} = 7 \\
12 \div 5 &= \alpha^{6\phantom{0}} \div \alpha^{8\phantom{0}} = \alpha^{15} \times \alpha^6 \div \alpha^8 = \alpha^{13} = 13
\end{align}

のようになります。

ちなみに $0$ が関わる場合も同様で

\begin{align}
0 + 14 &= 0000_{(2)} + 1110_{(2)} = 1110_{(2)} = 14 \\
8 - 0 &= 0100_{(2)} - 0000_{(2)} = 0100_{(2)} = 8 \\
2 \times 0 &= \alpha^{\rlap{1}\phantom{-\infty}} \times \alpha^{-\infty} = \alpha^{-\infty} = 0 \\
0 \div 10 &= \alpha^{-\infty} \div \alpha^{\rlap{9}\phantom{-\infty}} = \alpha^{-\infty} = 0
\end{align}

のように計算できます。

掛け算と割り算において $\alpha^{15} = 1$ が成り立つため、$i \neq -\infty$ かつ $j \neq -\infty$ のとき

\begin{align}
\alpha^i \times \alpha^j &= \alpha^{(i+j) \bmod 15} \\
\alpha^i \div \alpha^j &= \alpha^{(15+i-j) \bmod 15}
\end{align}

と考えることもできます。

例えば

\begin{alignat}{5}
6 \times 4 &= \alpha^5 & {} \times {} &\alpha^2 & &= \alpha^{(5+2) \bmod 15} & &= \alpha^7 & &= 11 \\
8 \times 9 &= \alpha^3 & {} \times {} &\alpha^{14} & &= \alpha^{(3+14) \bmod 15} & &= \alpha^2 & &= 4 \\
9 \div 3 &= \alpha^{14} & {} \div {} &\alpha^4 & &= \alpha^{(15+14-4) \bmod 15} & &= \alpha^{10} & &= 7 \\
12 \div 5 &= \alpha^6 & {} \div {} &\alpha^8 & &= \alpha^{(15+6-8) \bmod 15} & &= \alpha^{13} & &= 13
\end{alignat}

のようになります。

2. 有限体 GF(2⁸) の例

2.1. 有限体上で使える数

有限体 $GF(2^8)$ 上では数は $0$ から $255$ の整数のみを使うことができます。

有限体で使える数はべき乗 $\alpha^i$ を用いて

\begin{align}
\alpha^0 &= 1 \\
\alpha^1 &= 2 \\
\alpha^2 &= 4 \\
\alpha^3 &= 8 \\
\alpha^4 &= 16 \\
&\hspace{0.5em} \vdots \\
\alpha^7 &= 128 \\
\end{align}

のように表現できます。

ここで $\alpha^8 = 256$ としたいところですが、前述の通り有限体 $GF(2^8)$ 上では $256$ という数は使うことができないため、他の数になります。

足し算および引き算は排他的論理和で実現します。足し算と引き算は同じ計算結果になります。

ここで、原始多項式を $x^8 + x^4 + x^3 + x^2 + 1$ とすると、

\alpha^8 + \alpha^4 + \alpha^3 + \alpha^2 + \alpha^0 = 0

\begin{align}
\alpha^4 &= 0 - \alpha^4 - \alpha^3 - \alpha^2 - \alpha^0 \\
&= \alpha^4 + \alpha^3 + \alpha^2 + \alpha^0 \\
&= 16 + 8 + 4 + 1 \\
&= 29
\end{align}

となり、$\alpha^4 =29$ と求めることができます。

同様に計算すると $\alpha^0$ から $\alpha^{254}$ まで値は重複せず、$\alpha^{255} = 1$ になります。

このまま計算を続けても数 $0$ は得られないため、別途 $\alpha^{-\infty} = 0$ とします。

地道に式変形してもこれらの結果は得られますが、式の係数をビットとして見てビット演算を行うことでも計算できます。

有限体で使える数はべき乗 $\alpha^i$ および 2 進数を用いて

\begin{align}
\alpha^0 &= 00000001_{(2)} = 1 \\
\alpha^1 &= 00000010_{(2)} = 2 \\
\alpha^2 &= 00000100_{(2)} = 4 \\
\alpha^3 &= 00001000_{(2)} = 8 \\
\alpha^4 &= 00010000_{(2)} = 16 \\
&\phantom{= 0000}\hspace{0.5em} \vdots \\
\alpha^7 &= 10000000_{(2)} = 128 \\
\end{align}

のように表現でき、原始多項式は $x^8 + x^4 + x^3 + x^2 + 1$ より

\alpha^8 + \alpha^4 + \alpha^3 + \alpha^2 + \alpha^0 = 100011101_{(2)} = 0

\begin{align}
\alpha^8 &= 100000000_{(2)} \\
&= 100000000_{(2)} + 100011101_{(2)} \\
&= 00011101_{(2)} \\
&= 29
\end{align}

と計算できます。

他の $\alpha^i$ の値に関しても同様に計算でき、$\alpha^0$ から $\alpha^{254}$ まで値は重複せず、$\alpha^{255} = 00000001_{(2)} = 1$ になります。

数 $0$ は別途 $\alpha^{-\infty} = 00000000_{(2)} = 0$ とします。

2.2. 有限体上の四則演算

足し算と引き算は排他的論理和、掛け算と割り算はべき乗 $\alpha^i$ の形にして $\alpha^{255} = 1$ を利用すると計算できます。

掛け算と割り算は数をべき乗の形にすれば

\begin{align}
\alpha^i \times \alpha^j &= \alpha^{i+j} \\
\alpha^i \div \alpha^j &= \alpha^{i-j}
\end{align}

という直感的な計算ができます。

例えば

\begin{align}
15 + 15 &= 00001111_{(2)} + 00001111_{(2)} = 00000000_{(2)} = 0 \\
6 + 5 &= 00000110_{(2)} + 00000101_{(2)} = 00000011_{(2)} = 3 \\
6 - 5 &= 00000110_{(2)} - 00000101_{(2)} = 00000011_{(2)} = 3 \\
6 \times 3 &= \alpha^{26\phantom{0}} \times \alpha^{25\phantom{0}} = \alpha^{51\phantom{0}} = 10 \\
7 \times 11 &= \alpha^{198} \times \alpha^{238} = \alpha^{436} = \alpha^{255} \times \alpha^{181} = \alpha^{181} = 49 \\
9 \div 3 &= \alpha^{223} \div \alpha^{25\phantom{0}} = \alpha^{198} = 7 \\
12 \div 5 &= \alpha^{27\phantom{0}} \div \alpha^{50\phantom{0}} = \alpha^{255} \times \alpha^{27} \div \alpha^{50} = \alpha^{232} = 247
\end{align}

のようになります。

ちなみに $0$ が関わる場合も同様で

\begin{align}
0 + 14 &= 00000000_{(2)} + 00001110_{(2)} = 00001110_{(2)} = 14 \\
8 - 0 &= 00000100_{(2)} - 00000000_{(2)} = 00000100_{(2)} = 8 \\
2 \times 0 &= \alpha^{\rlap{1}\phantom{-\infty}} \times \alpha^{-\infty} = \alpha^{-\infty} = 0 \\
0 \div 10 &= \alpha^{-\infty} \div \alpha^{\rlap{51}\phantom{-\infty}} = \alpha^{-\infty} = 0
\end{align}

のように計算できます。

掛け算と割り算において $\alpha^{255} = 1$ が成り立つため、$i \neq -\infty$ かつ $j \neq -\infty$ のとき

\begin{align}
\alpha^i \times \alpha^j &= \alpha^{(i+j) \bmod 255} \\
\alpha^i \div \alpha^j &= \alpha^{(255+i-j) \bmod 255}
\end{align}

と考えることもできます。

例えば

\begin{alignat}{5}
6 \times 3 &= \alpha^{26} & {} \times {} &\alpha^{25} & &= \alpha^{(26+25) \bmod 255} & &= \alpha^{51} & &= 10 \\
7 \times 11 &= \alpha^{198} & {} \times {} &\alpha^{238} & &= \alpha^{(198+238) \bmod 255} & &= \alpha^{181} & &= 49 \\
9 \div 3 &= \alpha^{223} & {} \div {} &\alpha^{25} & &= \alpha^{(255+223-25) \bmod 255} & &= \alpha^{198} & &= 7 \\
12 \div 5 &= \alpha^{27} & {} \div {} &\alpha^{50} & &= \alpha^{(255+27-50) \bmod 255} & &= \alpha^{232} & &= 247
\end{alignat}

のようになります。

3. 原始多項式の求め方の概要

既約多項式 (つまり因数分解できない多項式) の中から前述のようなべき乗 $\alpha^i$ の対応が作れるものを選びます。

原始多項式は既約多項式になりますが、すべての既約多項式が原始多項式になるわけではありません。

例えば、8 次の ($x^8$ で始まる) 既約多項式は 30 個存在し、その内の 16 個は原始多項式として使用することができます。

参考「有限体 GF(2^n) の既約多項式および原始多項式の一覧: 1 次から 8 次まで - Qiita」