Chapter 05

拡大体 GF(2^m) — 1 バイトが 1 つの「数」になる世界

この章で第 I 部が完成する. 03 章で\(\mathbb{Z}\)を素数\(p\)で割って\(\mathrm{GF}(p)\)を作った。 04 章で多項式の世界と、そこでの「素数」（既約多項式）を用意した。この章ではまったく同じ論法を多項式に適用して\(\mathrm{GF}(2^m)\)を作る。
材料「素数」で割るできる体
03 章整数\(\mathbb{Z}\) 素数\(p\) \(\mathrm{GF}(p)\)
本章多項式\(\mathrm{GF}(2)[x]\) 既約多項式\(f(x)\)（次数\(m\)） \(\mathrm{GF}(2^m)\)
完成すると、1 バイト（8 ビット）がそれ自体 1 個の「数」になり、バイトどうしの足し算・掛け算・割り算が自由にできる世界が手に入る。 AES もリード・ソロモンも QR コードも、この世界の上で動いている。

	材料	「素数」で割る	できる体
03 章	整数\(\mathbb{Z}\)	素数\(p\)	\(\mathrm{GF}(p)\)
本章	多項式\(\mathrm{GF}(2)[x]\)	既約多項式\(f(x)\)（次数\(m\)）	\(\mathrm{GF}(2^m)\)

1. 構成 — 既約多項式で割った余りの世界

定義

次数\(m\)の既約多項式\(f(x) \in \mathrm{GF}(2)[x]\)を 1 つ選ぶ。 \(\mathrm{GF}(2^m)\)の要素は、\(f(x)\)で割った余りとして現れる多項式、すなわち

\[ a_{m-1}x^{m-1} + \cdots + a_1 x + a_0, \qquad a_i \in \{0,1\} \]

の形の多項式全体である。係数は\(m\)個、各々 2 通りなので、要素数はちょうど\(2^m\)個 ✓

演算は「多項式として計算してから\(f(x)\)で割った余りを取る」と定める。

なぜ体になるのか（逆元の存在）

体であるために必要なのは、0 以外のすべての要素が逆元を持つこと。これを示す。

\(a(x) \neq 0\)、\(\deg a < m\)とする。\(f\)は既約で\(\deg a < \deg f\)なので、 \(f\)の因数のうち\(a\)を割り切るものは定数しかない。よって

\[ \gcd(a(x), f(x)) = 1 \]

04 章の拡張ユークリッドより、次を満たす\(u(x), v(x)\)が存在する:

\[ a(x)u(x) + f(x)v(x) = 1 \]

両辺を\(f(x)\)で割った余りを取ると、\(f(x)v(x)\)は消えて

\[ a(x)u(x) \equiv 1 \pmod{f(x)} \]

つまり\(u(x)\)が\(a(x)\)の逆元 ✓ ∎

01〜03 章と完全に同じ論法である. 「\(\gcd = 1\) → ベズーの等式 → 逆元」という流れを、整数から多項式に移しただけ。 既約性が効いているのは\(\gcd(a,f)=1\)を保証する一点で、整数のとき「\(p\)が素数だから\(\gcd(a,p)=1\)」と言ったのと対応している。
逆に\(f\)が可約だと壊れる。たとえば\(f = x^2 = x\cdot x\)なら、\(a = x\)は\(f\)と共通因数を持ち、 \(x \cdot (\text{何か}) \equiv 1\)を満たす多項式は存在しない（零因子ができてしまう）。

2. GF(2^3) を手で作る — 全要素を書き出す

\(m = 3\)、既約多項式\(f(x) = x^3 + x + 1\)（04 章で既約と確認済み）を使う。要素は 8 個（\(2^3\)）。

生成元 α によるべき表現

\(f(\alpha) = 0\)を満たす元\(\alpha\)を考える。つまり

\[ \alpha^3 + \alpha + 1 = 0 \Longrightarrow \boxed{\alpha^3 = \alpha + 1} \]

（標数 2 なので移項は符号を変えずにそのまま。）この関係式を使って\(\alpha\)のべき乗を次々に低次に書き換える:

べき	計算	多項式表現	ビット	10 進
\(\alpha^0\)	—	\(1\)	001	1
\(\alpha^1\)	—	\(\alpha\)	010	2
\(\alpha^2\)	—	\(\alpha^2\)	100	4
\(\alpha^3\)	\(\alpha+1\)	\(\alpha+1\)	011	3
\(\alpha^4\)	\(\alpha\cdot\alpha^3 = \alpha(\alpha+1)\)	\(\alpha^2+\alpha\)	110	6
\(\alpha^5\)	\(\alpha(\alpha^2+\alpha) = \alpha^3+\alpha^2 = \alpha^2+\alpha+1\)	\(\alpha^2+\alpha+1\)	111	7
\(\alpha^6\)	\(\alpha(\alpha^2+\alpha+1) = \alpha^3+\alpha^2+\alpha = \alpha^2+1\)	\(\alpha^2+1\)	101	5
\(\alpha^7\)	\(\alpha(\alpha^2+1) = \alpha^3+\alpha = 1\)	\(1\)	001	1

\(\alpha^7 = 1\)で一周した。\(\alpha^1\)から\(\alpha^7\)までで0 以外の 7 個の要素をすべて尽くしている ✓ （\(f\)が原始多項式である、ということ。）

この表が実装のすべてである. 左の「べき表現」と右の「多項式（ビット）表現」を行き来する 2 枚の表（対数表と逆対数表）を用意しておけば:
足し算はビット表現で XOR
掛け算はべき表現で指数を足す（\(\alpha^i \cdot \alpha^j = \alpha^{(i+j) \bmod 7}\)）
つまり掛け算が足し算に化ける。対数を使って掛け算を足し算にする、あの計算尺と同じ発想である。リード・ソロモン符号の実装では、この 2 枚の表（256 バイト×2）を持つのが定番。

演算の実例

加算: \(\alpha^3 + \alpha^5 = (\alpha+1) + (\alpha^2+\alpha+1) = \alpha^2\) ビットで: \(011 \oplus 111 = 100\) ✓ 表より\(\alpha^2\) ✓

乗算（べき表現）: \(\alpha^3 \cdot \alpha^5 = \alpha^8 = \alpha^{8 \bmod 7} = \alpha^1 = \alpha\)

乗算（多項式で直接）: \((\alpha+1)(\alpha^2+\alpha+1) = \alpha^3+\alpha^2+\alpha+\alpha^2+\alpha+1 = \alpha^3+1\) \(\alpha^3 = \alpha+1\)を代入して\(= \alpha+1+1 = \alpha\) ✓ 一致 ✓

逆元: \(\alpha^3\)の逆元は\(\alpha^{7-3} = \alpha^4\)。検算: \(\alpha^3 \cdot \alpha^4 = \alpha^7 = 1\) ✓

除算: \(\alpha^5 / \alpha^3 = \alpha^{5-3} = \alpha^2\)

3. GF(2^8) — 実務で使われる 1 バイトの体

AES の場合

AES は\(f(x) = x^8 + x^4 + x^3 + x + 1\)（0x11B）を使う。要素は 0x00〜0xFF の 256 個。

乗算の実装（xtime 法）: \(\alpha\)倍（つまり\(x\)倍）は「1 ビット左シフト」だが、 8 ビットからあふれたら\(f\)を XOR して次数を下げる:

uint8_t xtime(uint8_t a) {
    return (a << 1) ^ ((a & 0x80) ? 0x1B : 0x00);
}

（0x1B は 0x11B の下位 8 ビット。最上位ビットが立っていたら\(x^8\)が発生するので、 \(x^8 = x^4+x^3+x+1\) = 0x1B に置き換える。）

実例: \(\texttt{0x57} \times \texttt{0x02}\) \(\texttt{0x57} = 01010111_2\)、最上位ビットは 0 なので単に左シフト: \(\texttt{0xAE}\)

実例 2: \(\texttt{0xAE} \times \texttt{0x02}\) \(\texttt{0xAE} = 10101110_2\)、最上位ビットが 1 なのでシフト後に 0x1B を XOR: \((\texttt{0xAE} \ll 1) = \texttt{0x15C} \to\) 8 ビットに切って\(\texttt{0x5C}\)、 \(\texttt{0x5C} \oplus \texttt{0x1B} = \texttt{0x47}\)

一般の乗算は、片方をビット分解して xtime の繰り返しと XOR で組み立てる（\(a \times \texttt{0x0B} = a\times(\texttt{0x08}+\texttt{0x02}+\texttt{0x01})\) のように）。

AES の MixColumns がこれ. 状態バイトに 0x02, 0x03 を掛ける操作が現れるが、それはすべて\(\mathrm{GF}(2^8)\)上の乗算である。 暗号の強度は「体の上での複雑な混ぜ合わせ」から来ており、その体がこの章で作ったものである。

リード・ソロモン（QR コード）の場合

QR コードは\(f(x) = x^8+x^4+x^3+x^2+1\)（0x11D）を使い、\(\alpha = 2\)が原始元。 \(\alpha^{255} = 1\)なので、0 以外の 255 個の要素を巡る。

4. 有限体の一般論（まとめの定理）

ここまでの構成が例外なく成り立つことを、一般の定理として述べておく。

定理 1（存在と一意性）: 任意の素数\(p\)と正整数\(m\)に対し、要素数\(p^m\)の有限体が存在し、同型を除いて一意である。逆に、有限体の要素数は必ず素数のべき\(p^m\)の形に限る。

「同型を除いて一意」とは、どの既約多項式を選んでも、できる体は本質的に同じものという意味。 \(\mathrm{GF}(2^3)\)を作るのに\(x^3+x+1\)を使っても\(x^3+x^2+1\)を使っても、要素の名前が変わるだけで、演算の構造は完全に一致する。（実務で「AES は 0x11B、QR は 0x11D」と違う多項式を使えるのはこのため。ただし同じシステム内では統一しないと値が合わない。）

定理 2（乗法群は巡回群）: \(\mathrm{GF}(q)\)の 0 以外の要素は、乗法について位数\(q-1\)の巡回群をなす。すなわち原始元\(\alpha\)が存在し、全非零要素が\(\alpha\)のべきで書ける。

系（フェルマーの一般化）: 任意の\(a \neq 0\)について

\[ a^{q-1} = 1, \qquad \text{よって} \quad a^{-1} = a^{q-2} \]

\(\mathrm{GF}(2^8)\)なら\(a^{-1} = a^{254}\)。AES の S-box はこの逆元計算を使っている （\(\mathrm{GF}(2^8)\)上の逆元を取り、その後アフィン変換をかける）。

定理 3（部分体）: \(\mathrm{GF}(p^m)\)が\(\mathrm{GF}(p^n)\)を部分体として含む \(\iff\) \(n \mid m\)。

定理 4（フロベニウス）: 標数\(p\)の体では

\[ (a + b)^p = a^p + b^p \]

導出: 二項定理で展開すると\(\binom{p}{k}a^kb^{p-k}\)の和になる。 \(0 < k < p\)のとき\(\binom{p}{k} = \frac{p!}{k!(p-k)!}\)の分子は\(p\)を含み、分母は\(p\)より小さい数の積なので\(p\)で割り切れない。よって\(\binom{p}{k} \equiv 0 \pmod p\)となり、両端の項だけが残る ∎

標数 2 なら\((a+b)^2 = a^2+b^2\)。「2 乗すると各項が独立に 2 乗される」というこの性質は、 BCH 符号の共役根（10 章）や楕円曲線の高速演算で使われる。

5. 第 I 部のまとめ — 手に入った道具

道具	内容	この先の使い道
合同算術	\(\bmod\) の四則演算	RSA、CRC
拡張ユークリッド	逆元の計算	RSA 鍵生成、体の逆元
繰り返し二乗法	巨大なべき乗	RSA、DH、楕円曲線
群・環・体	構造の分類	全体の見通し
\(\mathrm{GF}(p)\)	素数個の完全な世界	数論暗号
多項式除算	余りの一意性	CRC（09 章）
既約・原始多項式	体を作る材料	GF(2^m)、LFSR
\(\mathrm{GF}(2^m)\)	1 バイト = 1 個の数	AES（14 章）、RS 符号（11 章）

これで代数の準備は完了である。次章から誤り検出・訂正に入る。