2013 年度前期 離散数学

草刈圭一朗 hkusakari@is.nagoya-u.ac.jpi

講義資料 (11): 多項式環・ガロア体

11.1

多項式環

本節は，教科書 4.1.1 節 (pp.151–156) に対応する．
定義 11.1 hR, +′ , ·′, 0, 1i を環とする．文字 x を用いた形式的な有限和

f (x) = a0 + a1 x + · · · + an xn(a0 , a1 , . . . , an ∈ R)

を R 上の多項式 (polynomial)，または R を係数とする多項式と呼ぶ．ここで，文字 x を変数 (variable) または不定元 (indeterminate) と呼ぶ．特に，an = 1 であるとき多項式 fの事をモニック多項式 (monic polynomial) と呼ぶ．また，有限個の i を除いて ai = 0 と約束することにより，f (x) = Σi ai xi とも記す．ここで，ai を項 ai xi の係数 (coefficient) あるいは i 次の係数と呼ぶ．2 つの多項式 Σi ai xi と Σi bi xi が等しいとは全ての i で ai = bi となることである．便宜上，係数が 0 の項は省略し，1xi は単に xi で略記する．
定義 11.2 環 hR, +′, ·′ , 0, 1i 上の多項式全体からなる集合を R[x] で記す．多項式の和 (+)と積 (·) を以下で定義する．
def

Σi ai xi + Σi bi xi == Σi (ai +′ bi )xi ，def

Σi ai xi · Σi bi xi == Σk (Σi+j=k ai ·′ bj )xk

環 hR, +′ , ·′ , 0, 1i 上の多項式環 (polynomial ring) とは代数系 hR[x], +, ·, 0, 1i の事である．
以下では慣例に従い + と +′ に同じ記号を利用し，· と ·′ は省略する．
定理 11.3 環 R 上の多項式環 R[x] は環である．

証明は割愛する．大変かもしれないが難しくはない．気骨ある若者はチャレンジすべし．
例 11.4 整数環上の多項式環 Z[x] を考える．

(1 − x) + (1 + x + x2 ) = 2 + 0x + x2 = 2 + x2
(1 − x)(1 + x + x2 ) = 1 + 0x + 0x2 − 1x3 = 1 − x3

定義 11.5 多項式 g が多項式 f の約元であるとき，g を f の因数 (factor) と呼び，g | f で記す．また，多項式 g が f, h 双方の因数であるとき g を f と h の共通因数 (common factor)と呼ぶ．

定義 11.6 多項式 f (x) = a0 + a1 x + · · · + an xn (ただし an 6= 0) を考える．このとき，nを多項式 f の次数 (degree) と呼び，deg(f ) で表す．
NOTE: 上記の定義において deg(0) は未定義になっている．文献によっては，deg(0) = −1または deg(0) = −∞ と定義する場合もある．
定義 11.7 多項式 f が既約多項式 (irreducible polynomial) であるとは，deg(f ) ≥ 1 で，さらに，f = gh かつ deg(g), deg(h) ≥ 1 となる多項式 g, h が存在しないことである．
NOTE: 既約多項式としてモニック多項式のみを考える文化もある．
67

11.2

可換体上の多項式環

本節も，教科書 4.1.1 節 (pp.151–156) に対応する．
多項式環を考える上で特に重要なのが可換体上の多項式環である．文献によっては，可換体上の多項式環のみを多項式環と呼ぶこともある．注意されたし．
可換体上の多項式環では，整数環 Z で成立した様々な良い性質が成立する．
定理 11.8 可換体 K 上の多項式環 K[x] は一意分解整域 (unique factorization domain)，すなわち以下の性質を満たす整域である．

• 任意の f ∈ K[x]/K は既約分解を持つ．すなわち，ある既約多項式 f1 , . . . , fn が存在して f = f1 · · · fn となる．さらに，この既約分解は既約多項式の順序と可逆元の積を除いて一意的である．
証明は割愛する．代数学の大抵の専門書に証明が載っているはずなので，興味ある方は参照されたし．

NOTE: 上記の定理は，可換体上の多項式環では整数環で成り立った素因数分解の一意性に相当する概念が成立することを意味する．
定理 11.9 可換体 K 上の多項式環 K[x] において剰余定理が成立する．すなわち，任意のf, g ∈ K[x] に対し，g 6= 0 ならば，以下を満たす多項式 q, r が存在する．

f = qg + r(r = 0 または deg(r) < deg(g))

さらに，上記を満たす多項式 q, r は一意に定まる．
証明 (概略のみ示す) q, r の存在は deg(f ) に関する帰納法で示せる．帰納段階の証明は
f = a0 + a1 x + · · · + an xn (an 6= 0)，g = b0 + b1 x + · · · + bm xm (bm 6= 0) とおくと，
n−mf ∗ = f − an b−1g を考えることにより帰納法の仮定が適用できる．また，一意性の証
m x
明は背理法で証明できる (次数の概念をうまく使うと容易に矛盾が導ける)．
定理 11.10 可換体 K 上の多項式環 K[x] はユークリッド整域である．
def

証明 (概略のみ示す) 定理 11.8 より K[x] は整域になる．さらに，付値 v を v(f ) == deg(f )で定義すればユークリッド整域になる．

例 11.11 以前，ユークリッド整域とは直感的に言うとユークリッドの互除法が適用できる代数である，と説明した．実際，可換体上の多項式環である R[x] において，以下のようにユークリッドの互除法を用いて最大公約元を求めることができる．
先ず，関係 ⇒E を (f, g) ⇒E (g, r) で定義する．ここで，r は定理 11.9 における多項式とする．このとき，f = x4 + x3 + 3x2 + 2x + 2，g = x3 − 2x2 − 2x − 3 とすると，(f, g) =⇒E=⇒E=((x + 3)g + (11x2 + 11x + 11), g)(g, 11x2 + 11x + 11)
1( 11(x − 3)(11x2 + 11x + 11) + 0, 11x2 + 11x + 11)(11x2 + 11x + 11, 0)
11x2 + 11x + 1168なお，約元の定義において同伴な元は同一視していたことに注意．それゆえに，f, g の最大公約元としては，11x2 + 11x + 11 でなく，これと同伴でかつモニックになる x2 + x + 1を取る場合が多い．
11.3

ガロア体

本節ではガロア体に関する基本的な性質を紹介する．証明は本講義の枠組みをかなり超えてしまうので割愛．
定義 11.12 ある素数 p と自然数 n に対し位数が pn となる体の事をガロア体 (Galois field)と呼び，GF (pn ) で記す．
命題 11.13 任意の有限体はガロア体である．また，任意の素数 p と自然数 n に対しガロア体 GF (pn ) が同型を除いて一意に存在する．

命題 11.14 p を素数とし，f を Zp [x] 上の n 次既約多項式とする．このとき，Zp [x]/(f ) はGF (pn ) を構成する．
NOTE: 本資料では，記法 Zp [x]/(f ) を紹介していない．ちなみに Zp [x]/(f ) は，多項式環 Zp [x] のイデアル (f ) を法とした剰余環であり，f の既約性により体であることが保証されている．とりあえず，Zp [x]/(f ) は例 11.16 のように Zp [x] における多項式を f で割ることによって得られる剰余多項式の全体と考えていれば十分．
命題 11.15 ガロア体 GF (pn ) = hF, +, ·, 0, 1i の乗法群 F × = hF \ {0}, ·, 1i は巡回群である，すなわち，ある α ∈ F \ {0} が存在して，F \ {0} = {α0 , α1 , . . . , αp −2 }nとなる．このとき，α をガロア体 F の原始元 (primitive element) と呼ぶ．また，任意のGF (pn ) の原始元 α に対し，Zp (α) は GF (pn ) を構成する．
NOTE: 本資料では，記法 Zp (α) を紹介していない．ちなみに Zp (α) は，体 Zp に α を付加した拡大体と呼ばれる体である．本資料で Zp (α) の記法を用いるのは α が GF (pn ) の原n始元であるという特殊な場合のみであるため，Zp (α) = {0, α0 , α1, . . . , αp −2 } と考えていれば十分．
例 11.16 f (x) = x4 + x + 1 とし，α を f の根とする (f (x) = 0 を満たす複素数)．ここで，f は Z2 [x] における既約多項式となっており，α はガロア体 GF (24 ) の原始元となっている(証明は割愛)．
命題 11.14 より，Z2 [x]/(f ) は GF (24 ) を構成する．また，命題 11.15 より，Z2 (α) も GF (24 )を構成する．さらに，命題 11.13 より，これらのガロア体は同型である．

69

以下にこれらのガロア体の対応表を記す．なお，(a0 a1 a2 a3 ) を多項式 a0 +a1 x+a2 x2 +a3 x3のベクトル表現と呼ぶことにする．

Z2 (α) Z2 [x]/(f ) ベクトル表現 Z2 (α)
0α0α1α2α3α4α5α601xx2x3
1+xx + x2
x2 + x3(0 0 0 0)(1 0 0 0)(0 1 0 0)(0 0 1 0)(0 0 0 1)(1 1 0 0)(0 1 1 0)(0 0 1 1)7αα8α9α10α11α12α13α14Z2 [x]/(f )ベクトル表現

31+x+x
1 + x2x + x3
1 + x + x2
x + x2 + x3
1 + x + x2 + x3
1 + x2 + x3
1 + x3(1 1 0 1)(1 0 1 0)(0 1 0 1)(1 1 1 0)(0 1 1 1)(1 1 1 1)(1 0 1 1)(1 0 0 1)



NOTE: 上の例で見るように，ガロア体 GF (2n ) は n ビット符合の全体と対応する．それゆえに，ガロア体の理論は符合理論の基礎をなし，通信のエラー検出・訂正等の基礎理論構築に大活躍する．また，暗号 (共通鍵暗号や楕円暗号等) への応用も盛んに研究されている．
定義 11.17 多項式 f ∈ Zp [x] に対し，f | (xk −1) となる最小の自然数 k を f の周期 (period)と呼ぶ．Zp [x] 上の n 次既約多項式 f が周期 pn − 1 を持つとき，f を原始多項式 (primitivepolynomial) と呼ぶ．
命題 11.18 n 次の既約多項式 f ∈ Zp [x] に対し以下の性質は全て等価である．

• f は原始多項式である．
• xp −1 ≡ 1 (mod f ) かつ任意の k < pn − 1 で xk 6≡ 1 (mod f )．
n• x が Zp [x]/(f ) = GF (pn ) の原始元である．
• Zp [x]/(f ) において，xp −1 = 1 かつ任意の k < pn − 1 で xk 6= 1．
nNOTE: 原始多項式は既約多項式であるが，この逆は一般には成立しない．例えば，x4 +x3 + x2 + x + 1 は Z2 [x] において既約多項式であるが原始多項式ではない．実際，k = 5(6= 24 − 1) に対し (x4 + x3 + x2 + x + 1)5 = 1．

演習課題
問 11.1 試験問題を作成せよ．また，作成した問題に対して以下の３項目も作成すること．

• 模範解答• 予想正答率• 予想解答時間 (お手上げの人は考慮しなくて良い)
なお，試験問題というものは，解̇い̇て̇貰̇う̇ための問題であると言うことを忘れないこと．

70