Chapter 04

多項式と既約多項式

この章の狙い: 多項式を「数」として扱えるようにする.

03 章の最後で行き止まりに来た。「\(\mathrm{GF}(256)\)が欲しいが、256 は素数でないので\(\mathbb{Z}_{256}\)では作れない」。

打開策はこうだった——整数でやったことを、多項式でもう一度やる。

整数の世界	多項式の世界
整数\(\mathbb{Z}\)	多項式\(\mathrm{GF}(2)[x]\)
素数	既約多項式
素数\(p\)で割った余り → \(\mathrm{GF}(p)\)	既約多項式で割った余り → \(\mathrm{GF}(2^m)\)

この対応表が本章と次章のすべてである。 「素数に当たるものが多項式の世界では何か」を突き止め、割り算の余りで新しい体を作る。

なお本章の内容は、CRC（09 章）にそのまま直結する。 CRC とは要するに「データを多項式と見なして、決められた多項式で割った余りを付ける」だけの技術だからである。

1. GF(2) 係数の多項式

定義

係数が\(\mathrm{GF}(2) = \{0,1\}\)の多項式の全体を\(\mathrm{GF}(2)[x]\)と書く:

最高次の項の次数を\(\deg f\)と書く。

決定的に重要な対応: 多項式 = ビット列. 係数が 0 か 1 しかないので、多項式は係数を並べただけのビット列として表せる。

$$x^5 + x^3 + x + 1 \longleftrightarrow 101011_2 = \texttt{0x2B}$$

（\(x^5\)の係数 1、\(x^4\)は 0、\(x^3\)は 1、\(x^2\)は 0、\(x^1\)は 1、\(x^0\)は 1）

つまりコンピュータが扱うあらゆるデータは、そのまま多項式と見なせる。 1 KB のファイルは 8192 次くらいの多項式である。 この見方ができると、「データの誤り検出」が「多項式の割り算」という代数の問題に化ける。それが CRC。

加算 = XOR

多項式の足し算は同じ次数の係数どうしを足す。係数は\(\mathrm{GF}(2)\)なので\(1+1=0\)、つまり XOR:

ビット列で見ると:

繰り上がりが無いのが普通の 2 進数の足し算との決定的な違いである （\(1+1\)は 0 になるだけで、上の桁に 1 を送らない）。

そして 02 章で見たとおり、標数 2 では引き算 = 足し算. \(a + a = 0\)なので\(-a = a\)。したがって多項式の減算も XOR。 符号理論で「引く」と書いてあっても、実装は全部 XOR である。

乗算

分配法則で展開し、同類項を XOR でまとめる:

（\(x^2\)が 2 個で消え、\(x\)が 2 個で消えた。）

ビット演算では「シフトと XOR の繰り返し」——繰り上がりの無い掛け算 (carry-less multiplication) になる。 最近の CPU には専用命令 PCLMULQDQ があり、CRC や AES-GCM の高速化に使われている。

2. 多項式の除算

手順

普通の筆算とまったく同じ。ただし引き算が XOR になる。

例: \(x^5 + x^3 + x + 1\) を \(x^3 + x + 1\) で割る。

ステップ 1: 被除数の最高次\(x^5\)を、除数の最高次\(x^3\)で割ると\(x^2\)。これが商の最初の項。 除数を\(x^2\)倍して引く（XOR する）:

ステップ 2: 余り\(x^2+x+1\)の次数 2 は、除数の次数 3 より小さい。ここで終了。

商\(q(x) = x^2\)、余り\(r(x) = x^2 + x + 1\)。

検算: \(x^2(x^3+x+1) = x^5+x^3+x^2\)、これに\(x^2+x+1\)を XOR すると \(x^5 + x^3 + (x^2 \oplus x^2) + x + 1 = x^5+x^3+x+1\) ✓

除算アルゴリズムの定理

定理: 任意の\(f(x)\)と\(g(x) \neq 0\)に対し、次を満たす\(q(x), r(x)\)が一意に存在する:

存在の導出: 上の手順そのもの。\(\deg f \geq \deg g\)である限り、最高次を打ち消す項を商に足して 被除数の次数を 1 つ以上下げられる。次数は有限なので有限回で\(\deg r < \deg g\)に到達する ✓

一意性の導出: \(f = q_1g + r_1 = q_2 g + r_2\)と 2 通りあったとする。辺々引くと

右辺の次数は\(\deg g\)未満。左辺は\(q_1 \neq q_2\)なら次数\(\geq \deg g\)になってしまい矛盾。 よって\(q_1 = q_2\)、したがって\(r_1 = r_2\) ∎

この「余りの一意性」が CRC の理論的根拠である. 送信側と受信側が同じ除数（生成多項式）を使えば、同じデータからは必ず同じ余りが出る。 余りが違えば、データが途中で変わった証拠になる。09 章でこれを詳しく扱う。

3. 既約多項式 — 多項式の世界の「素数」

定義

次数 1 以上の多項式\(f(x)\)が、自分より低次の多項式の積に分解できないとき、\(f\)を既約多項式という （分解できるものは可約）。

整数の素数と完全に同じ考え方: \(7\)は\(1\times 7\)としか書けないので素数、\(6 = 2\times 3\)なので合成数。

判定法（低次の場合）

次数 2, 3 の判定: \(\mathrm{GF}(2)\)上で次数 2 または 3 の多項式が可約なら、 必ず 1 次の因数（\(x\)または\(x+1\)）を持つ。 そして「\(x - a\)が因数 \(\iff\) \(f(a) = 0\)」（因数定理）なので:

• \(f(0) = 0\) \(\iff\) 定数項が 0（\(x\)で括れる）
• \(f(1) = 0\) \(\iff\) 係数の個数が偶数（1 を代入すると全係数の XOR になるため）

次数 4 以上: 1 次の因数が無くても 2 次×2 次に分解できる場合があるので、上の判定だけでは足りない。 低次の既約多項式で順に割ってみる必要がある。

実例: 次数 3 の多項式を全部調べる

\(x^3\)の係数は 1 として、残り 3 ビット（\(x^2, x, 1\)の有無）で 8 通り:

次数 3 の既約多項式は\(x^3+x+1\)と\(x^3+x^2+1\)の 2 つ。

検算（\(x^3+1\)が可約であること）: \((x+1)(x^2+x+1) = x^3+x^2+x+x^2+x+1 = x^3 + 1\) ✓（\(x^2\)が 2 個、\(x\)が 2 個で消えた）

実務で使われる既約多項式

4. 原始多項式 — 既約よりさらに強い条件

既約であっても、べき乗が全要素を尽くすとは限らない。 \(x\)のべき乗\(x, x^2, x^3, \dots\)を既約多項式\(f\)で割った余りが、 0 以外の全\(2^m - 1\)個の要素を巡るとき、\(f\)を原始多項式という。

（03 章の「原始元」の多項式版である。）

例: \(f = x^4+x+1\)（既約かつ原始）では\(x\)の位数が\(2^4-1 = 15\)で、全 15 個の非零要素を巡る。 一方\(x^4+x^3+x^2+x+1\)は既約だが原始ではない（\(x\)の位数が 5 にとどまる）。

なぜ原始性が要るのか. LFSR（13 章）で最長周期の擬似乱数を作るとき、 リード・ソロモン符号（11 章）で符号語の長さを最大にするとき、 「全要素を巡る」という性質が本質的に効く。単に既約なだけでは周期が短くなってしまう。

5. 最大公約多項式とユークリッドの互除法

整数のときとまったく同じ手順が使える。「大小」の代わりに「次数」を見る。

例: \(\gcd(x^4+x^3+x+1, x^3+x+1)\)

ステップ 1: \(x^4+x^3+x+1\) を \(x^3+x+1\) で割る。 \(x^4 \div x^3 = x\)なので、除数の\(x\)倍\(= x^4+x^2+x\)を XOR:

まだ次数 3 なので続ける。商にさらに 1 を足し、除数\(x^3+x+1\)を XOR:

商\(= x+1\)、余り\(= x^2+x\)。

ステップ 2: \(\gcd(x^3+x+1, x^2+x)\)。 \(x^3 \div x^2 = x\)、\(x(x^2+x) = x^3+x^2\)を XOR:

さらに\((x^2+x+1)\oplus(x^2+x) = 1\)。商\(=x+1\)、余り\(=1\)。

ステップ 3: \(\gcd(x^2+x, 1) = 1\)。

よって\(\gcd = 1\)（互いに素）。

拡張版も同じ: 01 章と同様に係数を追跡すれば \(a(x)u(x) + b(x)v(x) = \gcd(a,b)\) の\(u, v\)が求まる。 これが 05 章で GF(2^m) の逆元を計算する方法であり、 BCH・RS 符号の復号（10・11 章）で誤り位置多項式を求める鍵にもなる。

6. まとめ