Chapter 04
多項式と既約多項式
この章の狙い: 多項式を「数」として扱えるようにする.
03 章で\(\mathrm{GF}(256)\)が必要になったが、256 は素数でないので\(\mathbb{Z}_{256}\)では体を作れない。解決策は、整数の世界での構成を多項式の世界で繰り返すことである。
整数の世界 多項式の世界 整数\(\mathbb{Z}\) 係数が 0/1 の多項式全体\(\mathrm{GF}(2)[x]\)（1 節） 素数 既約多項式（3 節） 素数\(p\)で割った余り → \(\mathrm{GF}(p)\) 次数\(m\)の既約多項式で割った余り → \(\mathrm{GF}(2^m)\)（05 章で構成） この対応表が本章と次章の全体像である。 本章の内容は CRC（09 章） にも直結する。CRC はデータを多項式と見なし、決められた多項式で割った余りを付ける技術である。
この章で使う既出の用語（定義は各リンク先）. 合同式\(\equiv\)と\(\bmod\)（01 章 1 節）、ユークリッドの互除法（01 章 3 節）、拡張ユークリッドの互除法（01 章 4 節）、位数・逆元（02 章 1 節）、標数と「標数 2 では引き算 = 足し算」（02 章 3 節）、XOR（02 章 4 節）、原始元（03 章 3 節）、離散対数（03 章 3 節）
1. GF(2) 係数の多項式
定義
本章では係数を\(\mathrm{GF}(2) = \{0,1\}\)に限った多項式を扱う。その全体を\(\mathrm{GF}(2)[x]\)と書く:
多項式は複数の項の和だが、次数は多項式全体に 1 つ決まる数で、係数が 1 の項のうち\(x\)の指数が最も大きいもの（最高次の項）の指数を指す。これを\(\deg f\)と書く。上の式で言えば、\(a_n = 1\)のとき\(\deg f = n\)である。 たとえば\(f = x^5 + x^3 + 1\)の項は\(x^5, x^3, 1\)の 3 つで、最高次の項は\(x^5\)なので\(\deg f = 5\)である。 定数\(1\)の次数は 0 である。係数がすべて 0 の多項式（零多項式、単に\(0\)と書く）には次数を定めない。
\(x\)は数ではなく項の位置を示す記号であり、多項式は係数の並びで区別する。 3 節では\(x\)に値を代入する場面が出てくるが、代入するのは\(\mathrm{GF}(2)\)の要素\(0\)か\(1\)で、計算も\(\mathrm{GF}(2)\)で行う（\(1 + 1 = 0\)）。 このため、代入した値だけでは多項式を区別できないことがある。たとえば\(x^2 + x\)は
と、どちらを代入しても\(0\)になるが、係数が 0 でないので零多項式ではない。
多項式 = ビット列. 係数が 0 か 1 なので、多項式は係数を最高次から並べたビット列として表せる。
$$x^5 + x^3 + x + 1 \longleftrightarrow 101011_2 = \texttt{0x2B}$$
コンピュータが扱うあらゆるデータはそのまま多項式と見なせる。 この見方により、データの誤り検出が多項式の割り算という代数の問題になる。それが CRC（09 章）である。
加算 = XOR
多項式の足し算は同じ次数の係数どうしを足す。係数は\(\mathrm{GF}(2)\)なので\(1+1=0\)、つまり XOR:
ビット列で見ると（\(\oplus\)は XOR）:
繰り上がりが無いのが普通の 2 進加算との違いである（\(1+1\)は 0 になるだけで、上の桁に 1 を送らない）。 以下、XOR であることを強調したいときは多項式どうしの足し算にも\(\oplus\)を使う（意味は\(+\)と同じ）。
02 章 3 節で見たとおり、標数 2 では\(-a = a\)なので引き算 = 足し算 = XOR。 符号理論で「引く」と書いてあっても、実装は全部 XOR である。
乗算
分配法則で展開し、同類項を XOR でまとめる:
（同じ次数の項が 2 個あると、加算の規則で\(x^2 + x^2 = (1+1)x^2 = 0\)、\(x + x = (1+1)x = 0\)と消える。）
ビット列で見ると、片方の各ビット 1 についてもう片方をその桁ぶん左シフトして XOR する——繰り上がりの無い掛け算 (carry-less multiplication) になる。 たとえば\((x+1)(x^2+1)\)は\(011\)と\(101\)の掛け算で、\(x+1\)の\(x^1\)のビットに対して\(101\)を 1 桁左シフトした\(1010\)、\(x^0\)のビットに対してシフトなしの\(0101\)を作り、XOR して\(1111 = x^3+x^2+x+1\) ✓ 最近の CPU には専用命令 PCLMULQDQ があり、CRC や AES-GCM の高速化に使われている。
次数の基本性質: \(f, g \neq 0\)なら\(\deg(fg) = \deg f + \deg g\)。
例: \(f = x^2 + 1\)（\(\deg f = 2\)）、\(g = x^3 + x\)（\(\deg g = 3\)）。展開すると項どうしの積が 4 つ出る:
\(x^3\)は 2 個出るので、上の乗算と同じく\(x^3 + x^3 = (1+1)x^3 = 0\)で消える。一方\(x^5\)は最高次の項どうしの積\(x^2 \cdot x^3\)からしか出ないので、打ち消し合う相手がなく残る。よって\(\deg(fg) = 5 = 2 + 3\)。
一般にも同じで、次数\(\deg f + \deg g\)の項は\(f\)と\(g\)の最高次の項どうしの積からしか現れない（ほかの組み合わせは指数の和がそれより小さい）。その係数は\(1 \times 1 = 1\)なので消えない。
2. 多項式の除算
手順
普通の筆算と同じで、引き算が XOR になる。各段で、残っている多項式の最高次の項が消えるように除数をずらして XOR し、残りの次数が除数の次数より小さくなったら終わる。
普通の筆算との違い: 大小を比べない。 普通の筆算では、たとえば 10 から 11 は引けないので、その桁の商を 0 にして次の桁へ進む。 多項式の筆算では、残りの先頭（最高次）のビットが 1 で除数と桁がそろっていれば、数として除数より小さく見えても XOR する。たとえば\(10 \oplus 11 = 01\)である。 XOR には繰り下がりが無いので「引けない」ことが起きず、見るのは最高次の項を消せるかどうかだけだからである。
止まるところ: 下ろす桁が無くなったら終わり。 除数は被除数の桁の上でしかずらせない。除数の右端が被除数の右端（\(x^0\)の桁）にそろった段の XOR が最後で、その後は右に下ろす桁が無いので終了する。 このとき残っているのは右端の「除数の桁数 − 1」桁で、これが余りである。多項式で言えば、残りの次数が除数の次数より小さくなったところで止まる。 たとえば\(1001 \div 11\)なら、除数\(11\)の右端が\(1001\)の右端の 1 にそろう段までで、余りは最後の 1 桁である。
上の図で被除数と除数（ビット列）を変えて試せる。
図の初期値\(1101000 \div 1011\)は\(x^6+x^5+x^3\)を\(x^3+x+1\)で割る計算で、商と余りから次の等式が得られる:
除算アルゴリズムの定理
定理: 任意の\(f(x)\)と\(g(x) \neq 0\)に対し、次を満たす\(q(x), r(x)\)が一意に存在する:
存在: 上の手順そのもの。途中の余り（最初は\(f\)自身）の次数が\(\deg g\)以上である限り、次数の差を\(k\)として\(x^k\)を商に加え、\(x^k g\)を XOR すれば最高次の項が消えて次数が 1 以上下がる。次数は有限なので、有限回で余りが\(0\)になるか次数が\(\deg g\)未満になる。
一意性: \(f = q_1g + r_1 = q_2 g + r_2\)と 2 通りあったとする。辺々引くと
右辺は\(0\)か、次数が\(\deg g\)未満。左辺は\(q_1 \neq q_2\)なら\(0\)でなく、1 節の次数の性質から次数は\(\deg(q_1 - q_2) + \deg g \geq \deg g\)になり矛盾。よって\(q_1 = q_2\)、したがって\(r_1 = r_2\) ∎
この「余りの一意性」が CRC の理論的根拠である. 送信側と受信側が同じ除数（生成多項式）を使えば、同じデータからは必ず同じ余りが出る。 余りが違えば、データが途中で変わった証拠になる。09 章でこれを詳しく扱う。
合同式の記法
整数と同じ記法を多項式にも使う。\(g \bmod f\)は\(g\)を\(f\)で割った余りを表し、\(g\)と\(h\)を\(f\)で割った余りが等しいこと、すなわち\(g - h\)が\(f\)で割り切れることを
と書く。01 章 2 節と同じ理由で、足し算と掛け算の途中の式は好きなときに\(f\)で割った余りに置き換えてよい。この記法は 4 節と05 章で使う。
3. 既約多項式 — 多項式の世界の「素数」
定義
\(f = gh\)と書けるとき、\(g\)と\(h\)を\(f\)の因数という。 次数 1 以上の多項式\(f\)が、次数 1 以上の 2 つの多項式の積に書けないとき、\(f\)を既約多項式という。書けるものは可約という。積の次数は和なので（1 節）、可約なら 2 つの因数はどちらも\(f\)より次数が低い。 整数の素数と同じ考え方: 7 は\(1\times 7\)としか書けないので素数、\(6 = 2\times 3\)なので合成数。
判定法（低次の場合）
基本は「割り切れる相手を探す」。整数で 91 が素数かを調べるとき 2, 3, 5, 7, … で割ってみるのと同じで、\(f\)を低い次数の多項式で順に割り、割り切れるものが見つかれば可約、見つからなければ既約である。
試す範囲は次の 2 点で絞れる。
- 次数は\(\deg f / 2\)以下で足りる。\(f = gh\)なら\(\deg g + \deg h = \deg f\)なので、\(g, h\)の片方は次数が半分以下である（整数で\(\sqrt{n}\)まで試せば足りるのと同じ）。
- 割る相手は既約多項式だけで足りる。可約な\(g\)で割り切れるなら、\(g\)の因数でも割り切れるからである（整数で 4 を試さなくても 2 で見つかるのと同じ）。
上の図に\(f\)のビット列を入れると、この範囲の既約多項式で実際に割った結果が並ぶ。
1 次の因数は見ただけで分かる。1 次の多項式は\(x\)と\(x+1\)の 2 つだけで、どちらも割り算をしなくても判定できる。
- \(x\)で割り切れる ⇔ 定数項が 0。定数項が無ければ全部の項が\(x\)を含むので、\(x\)でくくれる。例: \(x^3+x^2 = x(x^2+x)\)。
- \(x+1\)で割り切れる ⇔ 係数 1 の項の個数が偶数。例: \(x^3+1\)は項が 2 個なので\(x+1\)で割り切れ、\(x^3+1 = (x+1)(x^2+x+1)\)。
なぜ項の個数で分かるのか。 3 段階で示す。
① 割り算の式を書く。 \(f\)を\(x+1\)で割った商を\(q(x)\)、余りを\(r\)とする。余りは除数\(x+1\)より次数が低いので、\(x\)を含まない定数（\(0\)か\(1\)）である:
② \(x = 1\)を代入して余りだけを取り出す。 \(1\)を選ぶのは、除数\(x+1\)を\(0\)にする値だからである（\(\mathrm{GF}(2)\)では\(1+1=0\)）。すると商の項がまるごと消えて余りだけが残る:
ここで注意したいのは、「\(x+1\)で割り切れる」は多項式そのものの性質であり、\(x\)にどの値を入れるかで成り立ったり成り立たなかったりするものではないことである。 \(x = 1\)の代入は、決まった定数である余り\(r\)を計算するための手段として 1 回使うだけで、「\(x = 1\)のときだけ割り切れる」という意味ではない。 \(x = 0\)を代入して得られる\(f(0)\)は定数項であり、これは\(x+1\)ではなく\(x\)で割り切れるかを表す別の量である（下で述べる）。
③ \(f(1)\)を計算する。 どの項\(x^k\)も\(x = 1\)で\(1^k = 1\)になるので、\(f(1)\)は\(1\)を項の個数だけ足したものである。\(\mathrm{GF}(2)\)では\(1+1 = 0\)なので、項の個数が偶数なら\(0\)、奇数なら\(1\)になる。
| \(f\) | \(f(1)\) | 余り\(r\) | \(x+1\)で |
|---|---|---|---|
| \(x^3+1\)（2 項） | \(1+1 = 0\) | \(0\) | 割り切れる |
| \(x^3+x+1\)（3 項） | \(1+1+1 = 1\) | \(1\) | 割り切れない |
\(x\)で割る場合も同じで、今度は除数\(x\)を\(0\)にする値\(x = 0\)を代入する。\(f(x) = q(x)\,x + r\)から\(f(0) = r\)となり、\(f(0)\)は定数項そのものなので、1 つ目の条件「定数項が 0」が得られる。 このように「除数を 0 にする値を代入すると余りが出てくる」ことを剰余の定理といい、そこから従う「余りが 0 ⇔ 割り切れる ⇔ その値を代入して 0」を因数定理という。
次数 2, 3 なら 1 次の因数を調べるだけでよい。次数 2 や 3 の多項式が可約なら、因数の次数は\(1+1\)か\(1+2\)なので、必ず 1 次の因数を含む。したがって
次数 4, 5 では 2 次の因数も調べる。1 次の因数が無くても 2 次 × 2 次などに分解できる場合がある。 次数 2 の既約多項式は\(x^2+x+1\)だけである（上の条件で\(x^2, x^2+x, x^2+1\)を調べると、どれも可約）。したがって 1 次の判定に加えて、\(x^2+x+1\)で割り切れるかを調べればよい。
- \(x^4+x^2+1\): 定数項 1、項 3 個なので 1 次の因数は無い。しかし\(x^2+x+1\)で割り切れ、\(x^4+x^2+1 = (x^2+x+1)^2\)。可約。
- \(x^4+x^3+x^2+x+1\): 定数項 1、項 5 個なので 1 次の因数は無い。\(x^2+x+1\)で割ると余りが\(x+1\)で割り切れない。既約。
実例: 次数 3 の多項式を全部調べる
\(x^3\)の係数は 1 として、残り 3 ビット（\(x^2, x, 1\)の有無）で 8 通り:
| 多項式 | ビット | 定数項 | 項の個数 | 判定 |
|---|---|---|---|---|
| \(x^3\) | 1000 | 0 | 1 | 可約（\(x\cdot x\cdot x\)） |
| \(x^3+1\) | 1001 | 1 | 2 | 可約（\((x+1)(x^2+x+1)\)） |
| \(x^3+x\) | 1010 | 0 | 2 | 可約（\(x(x+1)^2\)） |
| \(x^3+x+1\) | 1011 | 1 | 3 | 既約 ✓ |
| \(x^3+x^2\) | 1100 | 0 | 2 | 可約（\(x^2(x+1)\)） |
| \(x^3+x^2+1\) | 1101 | 1 | 3 | 既約 ✓ |
| \(x^3+x^2+x\) | 1110 | 0 | 3 | 可約（\(x(x^2+x+1)\)） |
| \(x^3+x^2+x+1\) | 1111 | 1 | 4 | 可約（\((x+1)^3\)） |
定数項が 1 で項の個数が奇数なのは\(x^3+x+1\)と\(x^3+x^2+1\)の 2 つだけで、これが次数 3 の既約多項式である。
実務で使われる既約多項式
| 用途 | 多項式 | 16 進表現 |
|---|---|---|
| AES の \(\mathrm{GF}(2^8)\) | \(x^8+x^4+x^3+x+1\) | 0x11B |
| リード・ソロモン（QR コード） | \(x^8+x^4+x^3+x^2+1\) | 0x11D |
| CRC-32 | \(x^{32}+x^{26}+x^{23}+x^{22}+x^{16}+x^{12}+x^{11}+x^{10}+x^8+x^7+x^5+x^4+x^2+x+1\) | 0x104C11DB7 |
16 進表現は 1 節のビット列を最高次の係数まで含めて書いたものである。たとえば 0x11B\(= 1\,0001\,1011_2\)は 9 ビットで、先頭の 1 が\(x^8\)に当たる。
4. 原始多項式 — 既約よりさらに強い条件
次数\(m\)の多項式\(f\)で割った余りは、\(0\)か次数\(m\)未満の多項式である。係数\(m\)個がそれぞれ 0/1 なので\(2^m\)通りあり、0 を除くと\(2^m - 1\)通りある。 次数\(m\)の既約多項式\(f\)について、\(x\)のべき乗\(x, x^2, x^3, \dots\)を\(f\)で割った余りを順に並べたとき、0 以外の\(2^m - 1\)通りがすべて現れるなら、\(f\)を原始多項式という。 既約であっても、べき乗が全部を尽くすとは限らない。
並べた余りは、\(x^N \equiv 1 \pmod f\)となったところで振り出しに戻り、以後\(x^{N+1} \equiv x\)、\(x^{N+2} \equiv x^2\)、…と同じ余りを繰り返す。 この最小の\(N\)を\(f\)を法とする\(x\)の位数という（02 章の要素の位数と同じ考え方）。 原始多項式とは、\(x\)の位数が\(2^m - 1\)で、1 に戻るまでに全部を巡るものである。03 章の「原始元」の多項式版である。
例: 3 節で既約と確かめた\(f = x^4+x^3+x^2+x+1\)は原始ではない。 \(x^4 = 1 \cdot f + (x^3+x^2+x+1)\)なので
これを使って\(x^5\)を計算する:
右辺の\(x^4\)を再び置き換えると
\(x^5 \equiv 1\)なので\(x\)の位数は 5 であり、0 以外の\(2^4 - 1 = 15\)通りの余りのうち 5 通りしか現れない。
一方\(f = x^4+x+1\)は原始多項式である（既約であることは 3 節と同じ手順で分かる。定数項 1、項 3 個なので 1 次の因数は無く、\(x^2+x+1\)で割ると余りが\(1\)で割り切れない）。 \(x^4 \equiv x+1\)なので、1 つ前の余りに\(x\)を掛け（ビット列では左シフト）、\(x^4\)が出たら\(x+1\)に置き換える（\(0011\)を XOR する）と順に求まる:
| \(i\) | \(x^i \bmod f\) | ビット | \(i\) | \(x^i \bmod f\) | ビット |
|---|---|---|---|---|---|
| 1 | \(x\) | 0010 | 9 | \(x^3+x\) | 1010 |
| 2 | \(x^2\) | 0100 | 10 | \(x^2+x+1\) | 0111 |
| 3 | \(x^3\) | 1000 | 11 | \(x^3+x^2+x\) | 1110 |
| 4 | \(x+1\) | 0011 | 12 | \(x^3+x^2+x+1\) | 1111 |
| 5 | \(x^2+x\) | 0110 | 13 | \(x^3+x^2+1\) | 1101 |
| 6 | \(x^3+x^2\) | 1100 | 14 | \(x^3+1\) | 1001 |
| 7 | \(x^3+x+1\) | 1011 | 15 | \(1\) | 0001 |
| 8 | \(x^2+1\) | 0101 |
\(x^{15}\)で初めて 1 に戻り、その間に 0 以外の 15 通りがすべて 1 回ずつ現れる。05 章では\(x^3+x+1\)について同じ表を作る。
なぜ原始性が要るのか. LFSR（13 章）で最長周期の擬似乱数を作るとき、 リード・ソロモン符号（11 章）で符号語の長さを最大にするとき、 「全要素を巡る」という性質が本質的に効く。既約なだけでは周期が短くなる。
5. 最大公約多項式とユークリッドの互除法
多項式\(a, b\)の両方を割り切る多項式のうち次数が最大のものを最大公約多項式といい、\(\gcd(a, b)\)と書く。\(\gcd(a,b) = 1\)のとき\(a\)と\(b\)は互いに素という。 計算には整数のとき（01 章）と同じ互除法が使える。\(a\)を\(b\)で割った余りを\(r\)とすると\(\gcd(a,b) = \gcd(b,r)\)なので、余りが\(0\)になるまで割り算を繰り返し、最後の 0 でない余りが\(\gcd\)である。「大小」の代わりに「次数」が下がっていくので必ず終わる。
例: \(\gcd(x^4+x^3+x+1,\; x^3+x+1)\)
ビット列では\(11011\)と\(1011\)である。割る側を前のステップの余りに替えながら、2 節の筆算を繰り返す。
ステップ 1: \(11011 \div 1011\)
商\(11 = x+1\)、余り\(110 = x^2+x\)。
ステップ 2: \(1011 \div 110\)（前の除数を前の余りで割る）
商\(11 = x+1\)、余り\(01 = 1\)。
ステップ 3: \(110 \div 1\)
余りが\(0\)になったので終了。最後の 0 でない余りは\(1\)（ステップ 2）である。
よって\(\gcd = 1\)で、2 つは互いに素である。
拡張版も同じ: 01 章 4 節と同様に各ステップの商から係数を追跡すれば、 \(a(x)u(x) + b(x)v(x) = \gcd(a,b)\) を満たす多項式\(u(x), v(x)\)が求まる。 これが 05 章で\(\mathrm{GF}(2^m)\)の逆元を計算する方法であり、 BCH・RS 符号の復号（10 章・11 章）で誤り位置多項式を求める鍵にもなる。