講義ノート

情報数学特論
桔梗宏孝
1
環の定義と基本事項
足し算 (+) やかけ算 (× あるいは ·) というと，自然数の演算，整数の演
算，有理数の演算，実数の演算，複素数の演算，複素数係数の多項式の演算
が連想されると思う．これらはすべて 1 つの演算として理解できた．しかし
ながら，世の中にはこれらの演算とは違うけれども，同じような性質をもっ
た演算がたくさんある．代数学では +, · などの演算 (記号) を少し抽象的に
使用し，よく知られているものとは違う場合も含めて使用する．+, · などは
一般論においては仮想的な演算ととらえ，具体例においては演算方法を具体
的に与えて使っていると考える．議論を展開するためにはもちろん，様々な
仮定を置く．この仮定が様々な定義である．
定義 1.1（環の定義） 組 (R, +, ·, 0, 1) が次の性質を満たすときこの組を環
(ring) と呼ぶ．ここで，+, · は抽象的な 2 項演算，0, 1 は抽象的な要素であ
る．+ を加法，· を乗法と呼ぶ．
(R0) R は空でない集合である．
(R1) (R, +, 0) は可換群である．すなわち，
(A1) 0 ∈ R
(A2) x, y ∈ R ならば x + y ∈ R (R は + で閉じている)
1
(A3) x, y, z ∈ R ならば (x + y) + z = x + (y + z) (+ の結合性)
(A4) x ∈ R ならば x + 0 = 0 + x = x (0 は + の単位元)
(A5) x, y ∈ R ならば x + y = y + x (+ の可換性)
(A6) x ∈ R ならば，ある z ∈ R に対し x + z = z + x = 0 (+ に関す
る逆元の存在)
(R2) (R, ·, 1) は単位元 1 をもつモノイドである．すなわち，
(M1) 1 ∈ R
(M2) x, y ∈ R ならば x · y ∈ R (R は · で閉じている)
(M3) x, y, z ∈ R ならば (x · y) · z = x · (y · z) (· の結合性)
(M4) x ∈ R ならば x · 1 = 1 · x = x (1 は · の単位元)
(R3) 1 ̸= 0
(R4) x, y, z ∈ R ならば x · (y + z) = x · y + x · z, (y + z) · x = y · x + z · x
(分配法則)
この定義はすこし長いが，これから様々な例に慣れてくれば自然なものに
感じられると思う．ここですぐに覚えなくてもよい．
例 1.2 整数の全体集合を Z と書く．すると，みなさんのよく知っている +
と · について，(Z, +, ·, 0, 1) は環である．0 と 1 もよく知っている 0 と 1 で
ある．
例 1.3 有理数全体 Q, 実数全体 R, 複素数全体 C も普通の +, · と 0 と 1 に
ついて環になる．
例 1.4 整数係数の 1 変数多項式の全体 Z[X]，有理数係数の 1 変数多項式
の全体 Q[X]，実数係数の 1 変数多項式の全体 R[X]，複素数係数の 1 変数
多項式の全体 C[X] は，普通の多項式の演算の + と ·，0 と 1 は整数の 0 と
1 とすれば環になる．
2
例 1.5 R 係数の 2 次の正方行列の全体を M (R, 2) とする．+ を行列の和，
· を行列の積，0 を零行列，1 を単位行列とすると (M (R, 2), +, ·, 0, 1) は環
になる．
例 1.6 H = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11} とする．x, y ∈ H に対し，
x + y を 12 時間表示での x 時の y 時間後の時間，x · y を，0 時から x 時間
針を進めるという操作を y 回行なったときの時間とすると，(H, +, ·, 0, 1) は
環になる．x + y = 整数として x + y を計算して 12 で割った余り，x · y =
整数として x · y を計算して 12 で割った余りとしても同じことである．
定義 1.7 (R, +, ·, 0, 1) が環のとき，さらに · が可換，すなわち
(M5) x, y ∈ R ならば x · y = y · x
のとき，この環を可換環 (commutative ring) と呼ぶ．
この可換環に対し，さらに
(M6) x ∈ R, x ̸= 0 ならば，ある z ∈ R に対し x · z = z · x = 1
のとき，この環を体 (field) と呼ぶ．体とは，環において 0 以外の部分が · に
関しても可換群になっているということである．
問 1.8 上の例を，可換環になっているもの，なっていないもの，体になっ
ているもの，体になっていないものに分類せよ．
· の可換性がなくても，0 以外の部分が乗法について群になっている (乗
法について逆元がある) ものもあり，斜体 (skew field, division ring) と呼ば
れる．
定義 1.9（加法と乗法の逆元） (R, +, ·, 0, 1) を環とする．x ∈ R に対し，
x + y = y + x = 0 となる y ∈ R がちょうど 1 つ存在する．このような y を
x の加法の逆元と呼び，−x と書く．また，xz = zx = 1 となる z ∈ R も存
3
在しても 1 つしかない．このような z を x の乗法の逆元と呼び，x−1 ある
いは 1/x と書く．一般の環において，x−1 が存在するとは限らないことに
注意してほしい．x ̸= 0 ならば必ず x−1 が存在する環が体 (斜体) である．
定義 1.10（減法と除法） 環 (R, +, ·, 0, 1) において，x, y ∈ R に対し，x − y
と x/y を x − y = x + (−y) と x/y = x · (1/y) で定義する．
問 1.11
環において次の等式が成り立つことを示せ．
(1) 0 · x = x · 0 = 0
(2) (−x) · y = x · (−y) = −xy
(3) (−x) · (−y) = xy
2
整数環と剰余環
一般の環におけるイデアルと剰余環の定義を先に行うのが普通であるが，
具体例を先に述べる．
命題 2.1（割り算の原理） N ̸= 0,, N ∈ Z とする．このとき，任意の m ∈ Z
に対し，
m = q · N + r,
0 ≤ r < |N |
となる整数 q, r が m, N に依存して唯 1 通り存在する．この q を m/N の
整商と呼び，r を m/N の余り，あるいは剰余と呼ぶ．N > 0 のとき，m/N
の整商は有理数 m/N を越えない最大の整数になる．ガウス記号 [x](= x を
越えない最大の整数) を使うと m/N の整商 = [m/N ] となる．m/N の剰
余を m mod N と書く．
証明は数学的帰納法で簡単にできる．
4
例 1.6 は，0 から 11 までの数で閉じている世界であるが，整数全体と密接
な関係にある．3 時と 15 時，4 時と 16 時は午前と午後を無視すれば同じ時
間であると我々は思っている．12 で割った余りが同じとき「同じ」と思っ
て使っているのである．整数 x に対し x mod 12 を対応させる写像を考える
とすべての整数は 0 から 11 のどれかに対応する．同じ値に対応するとき，
われわれば「同じ時間」と思っているのである．この「同じ」時間という概
念を一般化すると次の定義が生まれる．
定義 2.2（合同数） N ̸= 0 とする．整数 X に対し，X mod N = 0 のと
き，N |X と書く．これは N が X を割り切るということである．
整数 x, y に対し N |(x − y) のとき，x と y は法 N で合同と言い，x ≡ y
(mod N ) と書く．これは x mod N = y mod N ということである．
命題 2.3 N ∈ Z, N ̸= 0 とし，N Z = {N · z | z ∈ Z} とする．N Z を (N )
と書くことも多い．
(1) x, y ∈ N Z ならば x + y ∈ N Z.
(2) x ∈ N Z, r ∈ Z ならば r · x ∈ N Z.
(3) x ≡ y (mod N ) ⇔ (x − y) ∈ N Z.
最初の 2 つの性質はイデアルという概念の定義である．すなわち，N Z が
Z のイデアルになっていることを述べている．証明は易しい．
例 1.6 の演算を考えると，(3 + 4) mod 12 = 7 mod 12 = 7 も (15 +
16) mod 12 = 31 mod 12 = 7 で，
「同じ」時間同士の和は一見違う値にもか
かわらず同じ結果をもたらす．乗法についても同様である．一般に次が成り
立つ．
命題 2.4 N, a, a′ , b, b′ ∈ Z とする．N ̸= 0 で，a ≡ a′ (mod N )，b ≡ b′
(mod N ) とすると a + b ≡ a′ + b′ (mod N ) かつ a · b ≡ a′ · b′ (mod N ) で
ある．
5
証明 (乗法の · は省略して書く．) まず，ab ≡ a′ b′ (mod N ) を示す．前
の命題から，ab − a′ b′ ∈ N Z を示せばよい．ab − a′ b′ = ab + (−a′ b +
a′ b) − a′ b′ = (a − a′ )b + a′ (b − b′ ) と変形しておく．a ≡ a′ (mod N ) より，
a − a′ ∈ N Z，b ≡ b′ (mod N ) より，b − b′ ∈ N Z．N Z は整数倍で閉じ
ているから，(a − a′ )b ∈ N Z，a′ (b − b′ ) ∈ N Z．N Z は和で閉じているか
ら，(a − a′ )b + a′ (b − b′ ) ∈ N Z．したがって，ab − a′ b′ ∈ N Z．すなわち，
ab ≡ a′ b′ (mod N )．
a + b ≡ a′ + b′ (mod N ) の証明は易しい (演習問題)．
□
定義 2.5（剰余類） 0 < N ∈ Z とする．x ∈ Z に対し，
{x + n | n ∈ N Z}
を x の法 N の剰余類と呼び，x + N Z, x (N が文脈からわかるとき) などと
書く．すでにある記法を混用して x mod N と書くことも多い．N > 0 のと
き，法 N の剰余類はちょうど N 個ある．剰余類 S に対し，x ∈ S とすると
S = x である．x を S の代表元と呼ぶ．
たとえば N = 12 のとき，3 = 15 = {. . . , −9, 3, 15, 27, . . .} で，x ∈ Z に
対し，x は x mod 12 と同じ集合である．
命題 2.4 から，例 1.6 の環の要素 x を x = x + 12Z のどの要素 (代表元) と
入れ換えても同様の演算が定義できる．したがって，この例の演算は法 12
の剰余類に関する演算と考えることができる．
定義 2.6（剰余環） 0 < N ∈ Z とし，法 N の剰余類の全体 (要素は N 個)
を R とする．R から 2 つ要素をとるとそれらはある x, y ∈ Z に対し，x, y
と書ける．そこで，x + y = x + y ，x · y = x · y と定義すると，R はこれら
の演算で可換環になる．加法の単位元は 0，乗法の単位元は 1 である．この
定義は代表元に依存した定義であるが，命題 2.4 により，代表元の選び方に
よらない．
6
注意 2.7 法 N の合同は，同値関係と呼ばれる 2 項関係になっている．こ
れは等号のもつ本質的な性質を抜き出したものである．2 項関係 ∼ が，(1)
x ∼ x, (2) x ∼ y ならば y ∼ x, (3) x ∼ y かつ y ∼ z ならば x ∼ z の 3 つを
満たすとき，∼ を同値関係と呼ぶ．何かがある意味で「等しい」という概念
があると，それは同値関係になっているはずである．同値関係があると，
「同
じもの」の集合を 1 つの対称物と考え，同値類と呼ぶ．分数は 1/2 と 2/4 の
ように見た目が違っていても等しいものがあるが，正確には「分数として等
しい」という概念が定義されているのである．分数の四則演算は当たり前の
ように計算しているが，1/2 + 1/3 で計算しても 2/4 + 3/9 で計算しても結
果が「分数として等しい」ということは当たり前ではない．法 N の加法や
乗法，分数の四則演算のように，代表元の取り方によらずに値がうまく定ま
るとき，同値類同士の演算は well-defined である (整合的に定義されている)
という．
3
Z におけるユークリッドの互除法
2 つの整数の最大公約数は，それらの整数の線形和 (整数係数) として書け
る．この事実から，整数環のイデアルが 1 つの元で生成される (単項イデア
ルと呼ぶ) ことがわかる．ユークリッドの互除法というアルゴリズムでこの
形を具体的に求めることがでる．
定義 3.1（約数，公約数） m, d は整数とする．ある整数 a に対し m = a · d
と書けるとき (d|m)，d を m の約数と呼ぶ．2 つの整数 m, n に対し，d|m
かつ d|n のとき d を m と n の公約数と呼ぶ．m, n の公約数のうち最大のも
のを m と n の最大公約数 (the greatest common divisor) と呼び，gcd(m, n)
とか単に (m, n) と書く．最大公約数が 1 のとき，m と n は互いに素である
という．
7
命題 3.2 m, n は整数で，n > 0 とする．m mod n = r のとき，r = 0 な
らば gcd(m, n) = n で，r > 0 ならば gcd(m, n) = gcd(n, r) である．
証明 r = 0 の場合は n > 0 なので定義より明らか．r > 0 の場合．
m = q · n + r と書ける．d|m かつ d|n とすると r = m − q · n より d|r とな
る．逆に，d|n かつ d|r とすると d|m となる．したがって，m と n の公約
数の集合と n と r の公約数の集合は一致するので，そのうちの最大なものも
□
一致する．
この命題を利用すると m と n の最大公約数が高速に求まる．この方法を
ユークリッドの互除法と呼ぶ．二進数表示を考えると n の桁数 (= 約 log2 n)
より r の桁数が真に小くなる．したがって，n の (二進) 桁数回剰余演算
(mod) を行なえば必ず最大公約数が求まる．
例 3.3
gcd(34, 14) = gcd(14, 6) = gcd(6, 2) = 2
gcd(30, 17) = gcd(17, 13) = gcd(13, 4) = gcd(4, 1) = 1
命題 3.4 m, n が整数で，n > 0 とすると
mx + ny = gcd(m, n)
となる整数 x, y が存在する．
証明 次の主張を d2 に関する帰納法で証明する．
主張. m, n は整数で，n > 0 とする．x1 , y1 , d1 , x2 , y2 , d2 が整数で
mx1 + ny1 = d1
mx2 + ny2 = d2
とすると
mx + ny = gcd(d1 , d2 )
8
(1)
(2)
となる整数 x, y が存在する．
d1 = q · d2 + d3 , 0 ≦ d3 < d2 とする．(q, d3 は整数)
r = 0 の場合は gcd(d1 , d2 ) = d2 なので (2) が答えを与える．
r > 0 の場合．(1) − (2) × q を計算すると
m(x1 − x2 · q) + n(y1 − y2 · q) = d3
(3)
を得る．0 ≧ d3 < d2 と帰納法の仮定より，(2), (3) から
mx + ny = gcd(d2 , d3 ) = gcd(d1 , d2 )
となる整数 x, y が存在する．これで主張が示せた．
m·1+n·0=m
m·0+n·1=n
(4)
(5)
より，主張から，
mx + ny = gcd(m, n)
□
なる整数 x, y が存在する．
系 3.5
(1) m, n が整数のとき，d|m, n(公約数) ならば d| gcd(m, n) で
ある．
(2) m と n が互いに素 ⇐⇒ mx + ny = 1 となる整数 x, y が存在する．
注意 3.6 命題 2.7 の証明にそって計算すると，与えられた整数 m, n に対し
mx + ny = gcd(m, n)
となる整数 x, y が具体的に求まる．この方法を拡張されたユークリッドの
互除法と呼ぶ．
このとき，|x| < n，|y| < m となる解が求まることも証明できる．した
がって，
9
x ≧ 0 ならば，x mod n = x，
x < 0 ならば，x mod n = x + n，
y ≧ 0 ならば，y mod m = y ，
y < 0 ならば，y mod m = y + m．
これらは，コンピュータで処理するときに役立つ性質である．
例 3.7 34x + 14y = 2(= gcd(34, 14)) となる x, y を 1 組求める．
1・34 + 0・14 = 34
0・34 + 1・14 = 14 (34 = 2・14 + 6)
1・34 − 2・14 = 6 (14 = 2・6 + 2)
−2・34 + 5・14 = 2
x = −2,
y=5
30x + 17y = 1(= gcd(30, 17)) となる x, y を 1 組求める．
1・30 + 0・17 = 30
0・30 + 1・17 = 17
1・30 − 1・17 = 13
−1・30 + 2・17 = 4 (13 = 3・4 + 1)
x = 4,
4・30 − 7・17 = 1
y = −7
定義 3.8（イデアル） I ⊂ Z とする．
• x, y ∈ I ならば x + y ∈ I.
• x ∈ I, r ∈ Z ならば r · x ∈ I
の 2 つの条件が成り立つとき，I を Z のイデアルと呼ぶ．イデアルは一般の
可換環でも定義される．
例 3.9 a ∈ Z のとき，(a) = aZ = {x ∈ Z | a|x} は Z のイデアルである．
この形のイデアルを単項イデアルと呼ぶ．
10
Z のイデアルは，(a) (a ∈ Z) の形，すなわち，単項イデアルだ
定理 3.10
けである．このような整域を単項イデアル整域 (principal ideal domain, PID)
と呼ぶ．
証明 I を Z の (0) でないイデアルとする．I はイデアルなので，−1 倍で
閉じていることから正の元をもつ．I の正の元の最小なものを a とする．
すると，(a) = I である．これを示す．
(a) ⊆ I は明らかなので，I ⊆ (a) を示せばよい．
b ∈ I, b ̸= 0 を任意にとる．d = gcd(a, b) とする．すると，d = ax + by
となる x, y ∈ Z が存在する．a, b ∈ I より，d ∈ I となる．0 < d|a より，a
の最小性から，d = a である．d|b より，a|b である．すなわち，d ∈ (a)．□
N > 0，a ∈ Z とする．
命題 3.11
(1) a と N が互いに素ならば a は Z/N Z で乗法の逆元をもつ．
(2) a と N が互いに素でなければ a は Z/N Z で 0 あるいは零因子 (0 で
ない要素をかけても 0 になることがある) である．
証明 (1) a と N が互いに素とすると，ax + N y = 1 となる整数 x, y が存
在する．したがって，ax ≡ 1 (mod N ) である．
(2) a と N が互いに素でないとすると，d := gcd(a, N ) > 1 である．
N = bd，a = cd，b, c ∈ Z とする．ここで，b ̸= 0 (mod N ) である．一方，
ab = cdb = cN ≡ 0 (mod N ) より，a は Z/N Z において，0 あるいは零因
□
子になる．
系 3.12
整数 p について次は同値．
(1) Z/pZ が体になる．
(2) p は素数．
11
4
体係数 1 変数多項式環
定義 4.1 実数係数の 1 変数多項式の和，差，積の演算は周知のことと思う．
この演算は，係数がある環の要素になっている場合でも同様にできることは
簡単に想像できるだろう．実数係数の 1 変数多項式の全体を R[X] と書く
が，係数を環 R にしたときの多項式全体を R[X] と書く．これは多項式の
和と積に関して環になる．X を変数あるいは不定元と呼ぶ．もちろん，別
の文字を使っても構わない．
もう少し，形式的な定義を述べよう．R の数列 (a0 , a1 , . . .) のうち，有
限個を除いて 0 になるもの全体を考える．これは，添字ごとの和により加
群になる．i 番目が 1 でそれ以外が 0 の数列を Xi とし，それらの積を，
Xi Xj = Xi+j で決める．すると，自然に数列同士の積が決まり，このような
数列全体に環の構造が入る．X1 を X と書き，X0 を 1 と書くと，Xn = X n
(n 個の X の積) である．
R[X] の要素 f (X) は，a0 + a1 X + a2 X 2 + · · · + an X n ，an ̸= 0 と書け
る．このとき，n を f (X) の次数と呼び，deg(f ) と書く．
多項式同士の演算は位取り記法による整数の演算と似ているが，繰り上が
りがないので多項式のかけ算の方が簡単である．
注意 4.2 R が整域 (x ̸= 0，y ̸= 0 ならば xy ̸= 0) のとき，R[X] の
要 素 f (X), g(X) に 対 し ，deg(f g) = deg(f ) + deg(g)，deg(f + g) ≤
max{deg(f ), deg(g)} である．
命題 4.3（多項式の割り算の原理） R が環で，f (X), g(X) ∈ R[X] とする．
さらに，f (X) の最高次の係数が R× の元とする．すると，
g(X) = q(X)f (X) + r(X),
deg(r) < deg(f )
となる q(X), r(X) ∈ R[X] がただ 1 組存在する．
12
例 4.4 R = Z/10Z とし，R[X] の要素
f (X) = 3X 3 + 2X 2 + X + 1,
g(X) = 8X 5 + 4X 4 + X + 1
を考える．
3
2 1
1
)
6
8
8
4
4
2
2
2
2
0
6
4
8
6
6
0
6
4
4
0
4
6
1 1
4
7
2 2
5 9
これより，
g(X) = (6X 2 + 4X + 2)f (X) + 6X 2 + 5X + 9.
定義 4.5 R は環で，f , g ∈ R[X] とする．g = qf となる q ∈ R[X] が存在
するとき，f |g と書き，f を g の約数とよぶ．f の最大次の項の係数が 1 の
とき，f はモニックであるという。
R[X] において，f と g の公約数の中で次数最大でモニックなものを f と
g の最大公約数と呼ぶ．R[X] の単元 (可逆元) は R の単元と一致する．すな
わち，R[X]× = R× である．f と g の公約数が R[X] の単元だけのとき，f
と g は互いに素と呼ぶ．R[X] における f の約数が f と R[X] の単元だけの
とき，f は既約であるという．g, h ∈ R[X] に対し，f |gh ならば f |g または
f |h となるとき，f を素元と呼ぶ．
Z において，割り算の原理から最大公約数を求めるためにユークリッドの
互除法が使えた．これから，Z が PID(単項イデアル整域) であることや，p
が素数 (既約) のとき，Z/pZ が体になることが導かれた．また，一般に PID
ならば素元分解 (素因数分解) の一意性も導かれる (このとき UFD(Unique
Factorization Domain) と呼ぶ)．
13
F を体 (例えば，Q, R, C, F2 , F3 など) とすると，F [X] において割り算の
原理がいつも成り立つので，Z と同じ議論により，F [X] は PID，したがっ
て UFD になり，また，f (X) を F [X] の既約元 (F 上の 1 変数既約多項式)
とすると F [X]/(f (X)) は体になる．
命題 4.6 F は体とする．f (X), g(X) ∈ F [X] に対し，h(X) を f (X) と
g(X) の最大公約数とすると f (X)A(X) + g(X)B(X) = h(X) となる多項
式 A(X) と B(X) が F [X] に存在する．
問 4.7 Z においてこれは命題 3.4 に対応する．命題 3.4 は次のようにも証
明できる．これを書き直して，命題 4.6 を証明せよ．
命題 3.4 の別証明．
m と n が整数で，m, n ̸= 0 とする．I = {am + bn | a, b ∈ Z} とする．
I ̸= (0) なので，この中で絶対値が最小なものを d とする．d = a0 m + b0 n
と書けるので，m, n の公約数は d を割り切る．x が m と n の公約数とする
と，|x| ≤ |d| である．gcd(m, n)|d となるので，あとは d が m と n の公約
数であることが言えれば，gcd(m, n) = d または −d となる．
d が m あるいは n を割り切らないとする．たとえば d̸ | n とする．す
ると，n = qd + r, 0 < r < |d| と書ける．すると，0 < r = n − qd =
n − q(a0 m + b0 n) ∈ I となる．これは，d が I の中で絶対値最小にとったこ
とに反する．したがって，d は m と n の約数になる．
注 意 ．F [X] の 要 素 f (X), g(X) ̸= 0 に 対 し ，deg(f ) = deg(g) か つ
f (X)|g(X) な ら ば g(X) = cf (X) (c は 0 で な い 0 次 式 ，す な わ ち
0 ̸= c ∈ F ) と書ける．F が体なので，f (X) = c−1 g(X) とも書ける．
定理 4.8 F [X] は PID である．
問 4.9 定理 4.8 を証明せよ．定理 3.10 と同様にできる．
14
定義 4.10
F を 体 と し ，F [X] の 要 素 f (X), g(X), h(X) に 対 し ，
f (X)|g(X) − h(X) のとき，g(X) ≡ h(X) (mod f (X)) と書く．これは同
値関係になる．この同値類の全体を F [X]/(f (X)) と書く．Z/nZ = Z/(n)
の場合と同様に，これは自然に環になる．
命題 4.11
F が体，f (X) を F 上 n 次の多項式とすると，F [X]/(f (X)) は
加法群として，F (X) の n − 1 次以下の多項式の全体のなす加法群と同型に
なる．よって，F 上 n 次のベクトル空間になる．
証明 g(X) と h(X) を n − 1 次以下の多項式とすると，g(X) − h(X) の
次数は n − 1 次以下になり，n 次式 f (X) が因数になることはない．また，
F (X) の任意の要素 g(X) に対し，g(X) = q(X)f (X) + r(X) (deg(r) < n)
と表現できるが，g(X) ≡ r(X) (mod f (X)) となる．
例 4.12
□
F2 = Z/2Z とし，F2 [X] を考える．1 次式は X と X + 1 でこれ
らは既約である (1 次式は必ず既約)．2 次式は X 2 + aX + b のパターンなの
で 4 通りあるが，1 次式で割り算してみると，X 2 + X + 1 だけが既約にな
ることがわかる．
F2 [X]/(X 2 + X + 1) の積の演算表を作ると次のようになる (0 の欄を
除く)．
×
1
X
X +1
1
1
X
X +1
X
X
X +1
1
X +1
X +1
1
X
これは 4 元体 (4 つの元からなる体) になる．また， mod(X 2 + X + 1) で，
X 2 ≡ X + 1，X 3 ≡ 1 となり，X の巾で 0 以外の元が生成されている．
Fp [X] の既約多項式は Z におけるエラトステネスのふるいと同じ方法で
求めることができる．Fp [X] の要素は 0 から p − 1 までの整数の列と考えら
れるが，これは整数の p 進法による表記と対応するので，コンピュータで処
15
理するときは便利である (特に p = 2 のときはとても便利)．
問 4.13
F2 [X] の 4 次までの既約多項式をすべて求めよ．
例 4.14
Fp = Z/pZ において，乗法の逆元を求めるには次のようにユーク
リッドの互除法で求められる．a mod p の逆元を求めるのには ax + py = 1
を解かなくてもよい (y はいらない)．
7x ≡ 1 (mod 31) を解く．
31x ≡ 0 (mod 31)
7x ≡ 1 (mod 31)
((1) − (2) × 4) 3x ≡ −4 (mod 31)
((2) − (3) × 2)
x ≡ 9 (mod 31)
(1)
(2)
(3)
(4)
F2 [X] において，(X 2 + 1)g(X) ≡ 1 (mod X 5 + X 2 + 1) を解く (そのよ
うな g(X) を見つける)．
f (X) = X 5 + X 2 + 1 と置く．
(X 5 + X 2 + 1)g(X) ≡ 0 (mod f (X))
(X 2 + 1)g(X) ≡ 1 (mod f (X))
((1) − (2) × (X 3 + X + 1))
Xg(X) ≡ X 3 + X + 1 (mod f (X))
((2) − (3) × X)
g(X) ≡ X 4 + X 2 + X + 1 (mod f (X))
(1)
(2)
(3)
(4)
ここで，たとえば ((1) − (2) × (X 3 + X + 1)) の X 3 + X + 1 は，(X 5 +
X 2 + 1) ÷ (X 2 + 1) の筆算で求まる．
問 4.15
(1) F31 において，27−1 を求めよ (27x ≡ 1 (mod 31) を解け)．
(2) F2 [X]/(X 5 + X 2 + 1) において，(X 4 + X 3 + X 2 + X + 1)−1 を求めよ．
16
5
体，特に有限体
命題 5.1 F が体，f (X) を F [X] における既約元とすると F [X]/(f (X))
は体になる．
p が素数のとき Z/(p) が体になることと同じ理由である．
L = F [X]/(f (X)) とすると，命題 4.11 により，F は 0 次式 (定数項のみ
の多項式) として L の部分集合で，演算も L における演算が F の上ではもと
もとの F における演算になっている．F と L が体，F が L の部分集合で，
L の演算を F に制限すると F の演算になるとき，F を L の部分体，L を F
の拡大体と呼ぶ．このことを体の拡大 L/F と書く．f (X) が F [X] で既約
ならば L = F (X)/(f (X)) は F の拡大体になる．命題 4.11 により，L は F
上の有限次元ベクトル空間になる (次元は，f (X) が n 次ならば n 次元)．一
般に，体の拡大 L/F があると L は F 上のベクトル空間になる．この次元
を拡大次数と呼ぶ．体の拡大 L/F 拡大次数が n で有限とする．α ∈ L をと
ると，1, α, α2 , . . . , αn は一次従属になるので，
a0 + a1 α + a2 α2 + · · · + an αn = 0
となる．すなわち，ある g(X) ∈ F [X] に対し，g(α) = 0 となる．このと
き，α を g(X) の根と呼ぶ．
体の拡大 L/F において，L の元 α が F [X] のある元 (多項式) の根になっ
ているとき，α は F 上代数的という．L の任意の元が F 上代数的なとき，
この拡大を代数拡大と呼ぶ．
定義 5.2（標数） F を体とする．1 + · · · + 1 = 0 となる 0 でない自然数
|
{z
}
n
n が存在するとき，そのような自然数 n の最小値 p を F の標数と呼び，
ch(F ) = p と書く．このような n がないとき，ch(F ) = 0 とする．
17
命題 5.3 体の標数は 0 または素数である．また，標数 0 の体は有理数 Q と
同型な体を最小の部分体としてもち，標数 p > 0 の体は Fp と同型な体を最
小の部分体としてもつ．Q や Fp (p は素数) を素体と呼ぶ．
ここで，環論の重要な基本概念を述べておく．
定義 5.4 環 R1 , R2 と写像 f : R1 → R2 に対し，f が環の演算と定数 (0 と
1) を保存するとき，すなわち，
f (x + y) = f (x) + f (y)
f (xy) = f (x)f (y)
f (0) = 0
f (1) = 1
のとき (左辺の f の引数はすべて R1 の演算と定数，右辺は R2 の演算と定
数)，f を環の準同型写像と呼ぶ．f がさらに全単射のとき，f を環の同型写
像と呼ぶ．f が環の同型写像のとき，逆写像 f −1 も環の同型写像になる．こ
のとき，R1 と R2 は環として同型であるといい，R1 ∼
= R2 と書く．
問 5.5 f : R1 → R2 が環の準同型写像のとき，Ker(f ) = {x ∈ R1 | f (x) =
0} が R1 のイデアルになることを示せ (一般の環のイデアルの定義は Z や
F[X] のイデアルの定義を一般化したもの)．Ker(f ) を f の核と呼ぶ．
定理 5.6（環の準同型定理） f : R1 → R2 が全射な環の準同型とすると
R1 /Ker(f ) ∼
= R2 である．
証明は，自然に思いつく写像が well-defined になることだけが一番の問題
であるが，難しくない．
命題 5.3 の証明．
F を標数 p の素体とする．f : Z → F を f (m) = 1 の m 個の和 (m ≥ 0
のとき)，f (m) = −1 の |m| 個の和 (m < 0 のとき) とすると f は Z から
F への準同型写像になる．f (Z) は F の部分環になる．ch(F ) = 0 のとき，
18
Ker(f ) = (0) なので，f (Z) は Z と同型になる．Q = {f (m)/f (n) | m, n ∈
Z, n ̸= 0} とすると，Q ∼
= Q がわかる (商体)．
ch(F ) = p > 0 のとき，Ker(p) = (p) となり，Z/(p) ∼
= f (Z) となる．
p = qr (0 < q, r < p) と分解したとすると 0 = f (p) = f (pq) = f (p)f (q)
となり，F が体なので，f (p) = 0 あるいは f (q) = 0 となる．これは標数
の定義 (最小性) に反する．したがって，p は素数である．p が素数なので，
Fp = Z/(p) ∼
= f (Z) ⊂ F ．
また，これらの体は 1 と四則演算だけで生成されているから，F における
□
最小の部分体になる．
定義 5.7 L/F が体の拡大で，α ∈ L とする．多項式環 F [X] に対し，
G : F [X] → L を G(f (X)) = f (α) で定義すると，G は環の準同型になる．
G による F [X] の像を F [α] と書く．
α が F 上代数的のとき，Ker(G) = {g(X) ∈ F [X] | g(α) = 0} は
F [X] のイデアルであるが，その中の次数最小の多項式 f (X) をとると
Ker(G) = (f (X)) となる．この f (X) は最高次の係数が 1 にとれる．これ
を α の F 上の最小多項式と呼ぶ．f (X) は既約になる (問．L が体であるこ
とを使ってこれを示せ)．
命題 5.8 体の拡大 L1 /F と L2 /F があり，α1 ∈ L1 ，α2 ∈ L2 が共に F 上
代数的で同じ最小多項式をもつとすると，F [α1 ] ∼
=F F [α2 ] となり，これら
は体になる．ここで，∼
=F は F の元をすべて固定する同型写像がとれるとい
う意味である．
命題 5.9 F は体とする．1 次以上の f (X) ∈ F [X] に対し，F の代数拡大 L
で f (X) が L[X] の 1 次式だけの積に分解できるようなものがある．f (X)
が n 次とすると，f (X) = c(X − b1 ) · · · (X − bn ) となる bi ∈ L が存在す
ることになるが，F と b1 , . . ., bn から L の中で生成される体 F (b1 , . . . , bn )
が存在し，そこでも f (X) は同じ 1 次式に分解する．この F (b1 , . . . , bn ) を
19
f (X) の最小分解体と呼ぶ．f (X) の最小分解体はすべて F 上同型になる．
共通の体の中にある最小分解体は一致する．
証明 f (X) ∈ F [X] とする．f (X) の分解体 (f (X) を 1 次式の積に分解で
きる係数体) の存在を示す．まず，f (X) を F [X] の既約元の積に分解する．
これは，f (X) の次数に関する帰納法で示せる．f (X) = f1 (X)f2 (X) と次
数の低い多項式の積に分解できなければ f (X) が既約になる．このように
分解できたなら，f1 (X) と f2 (X) の次数は共に f (X) の次数より真に低い．
帰納法の仮定からどちらも既約元の積に分解できる．したがって，f (X) は
既約元の積に分解できる．
では，f (X) の分解体が F の代数拡大で存在することを f (X) の次数に関
する帰納法で示す．
さ て ，f (X) = f1 (X)f2 (X) で ，f1 (X) が 既 約 で あ る と す る ．F1 =
F [X]/(f1 (X)) とすると，F1 の中で α = X とすると，α は f1 (X) の根
である．したがって，f (X) の根でもある．割り算の原理から，F1 [X] の中
で f (X) = (X − α)q(X) と分解できる．q(X) の次数は f (X) の次数より真
に小さいので，帰納法の仮定から F1 の代数拡大 L で q(X) の分解体になっ
ているものがある．すると，この L は f (X) の分解体にもなっている．
最小分解体の一意性は命題 5.8 と F [X] の元の素因数分解の一意性を使
うと示せる．素因数分解の一意性はきちんと証明しようとすると少し長く
□
なる．
この節の残りで有限体の基本的な性質を調べる．
補題 5.10
有限体の元の数はある素数 p のべき (pn の形) になる．
証明 有限体 F において 1 を足していくと，いつか同じ要素が現れる (部屋
割論法)．たとえば 1 + 1 + 1 + 1 + 1 = 1 + 1 だったとすると 1 + 1 + 1 = 0
となり，標数が正になる．それは素数なので p としよう．Fp が F の部分体
となるが，F は Fp -ベクトル空間となり，有限なので Fp 上有限次元になる．
20
その次元を n とすると，ベクトル空間として Fn
p と同型になるからその大き
□
さは pn である．
命題 5.11（フロベニウス写像） F が体で，ch(F ) = p > 0 とすると F に
おいて
(x + y)p = xp + y p
したがって，Fr(x) = xp は F から F への単写準同型になる．
証明 2 項展開の係数を考えると
p Cm
=
p(p − 1) · · · (p − m + 1)
m!
となる．m!(p Cm ) ≡ 0 (mod p) となるが， mod p で m! は乗法の逆元をも
つので p Cm ≡ 0 (mod p)．すると p|p Cm となり，F において p 倍すると 0
になることから上の等式を得る．Fr が単写になるのは体において xp = 0 の
□
根が 0 だけだからである．
定理 5.12
F が有限体ならば F × は巡回群である．
この定理の証明はあとまわしにする．この定理により，F が q 元体なら
ばある α ∈ F によって F × = {1, α, α2 , . . . , αq−1 } と書ける．この α を F
の原始元と呼ぶ．したがって，F の要素はすべて X q − X = 0 の根である．
X q − X は q 次の多項式なので，F の要素はこの多項式の根全体になる．
ch(F ) = p とすると q = pn と書けるが，F はその拡大体の中で考えても
Frn の固定元全体になる (写像 σ の固定元とは σ(x) = x となる x のこと)．
定理 5.13
有限体 F の n 次拡大は F 上の同型 (F の元を固定する同型) を
除いて 1 つしかない．特に，F の大きさを q とすると，その素体上の拡大体
は 1 つしかない．これを Fq や GF(q) と書く．
21
証明 #F (元の個数) = l とする．F の n 次拡大 K を考えると #K = ln
である．q = ln とすると K の要素は X q − X の根の全体になっている．
F の n 次拡大 K ′ が別にあったとすると，やはり #K ′ = ln = q で，K ′
の要素は X q − X の根の全体になっている．K ′ の原始元 β の F 上の最小多
項式を f (X) とすると K ′ ∼
= F [X]/(f (X)) となる．β を根にもつ F [X] の
元全体がイデアルになり，その生成多項式が β の最小多項式 f (X) だったの
で，f (X)|X q − X である．F [X] における素元分解の一意性により，f (X)
は K でも解をもつ．それを α とすると F [α] ∼
= F [X]/(f (X)) が K の部分
体になるが，F [α] の大きさと K の大きさが一致するので F [α] = K であ
る．したがって，K ∼
= F [X/(f (X))] ∼
= K ′ で K と K ′ は同型になる．
問 5.14
□
F7 の原始元をすべて求めよ．
有限体のこの構造を利用した誤り訂正符号として巡回符号がある．巡回符
号は誤り検出のために実際によく使われている (通信，ハードディスクの読
み書きなど)．また，この構造を利用した公開鍵暗号として，ElGamal 暗号
や DSA がよく使われている．
以下，有限体に対し，任意の自然数 n について n 次拡大体が存在するこ
とを示す．ちなみに，R の有限次拡大体は 2 次拡大 C だけで，C の有限次
拡大体は存在しない．
定義 5.15
F を体とする．多項式環 F [X] における (形式的) 微分を c ∈ F
に対し (c)′ = 0，(X n )′ = nX n−1 で定義し，F [X] の一般の元については各
項の微分の和として定義する．
補題 5.16
L/F を体の拡大とする．f (X) ∈ F [X] が L[X] で f (X) =
(X − α)2 g(X) と分解できる (このとき f(X) は重根をもつという) ための必
要十分条件は，f (X) と f ′ (X) が共通根をもつことである．
22
証明 f (X) = (X − α)2 g(X) と分解できたとすると f ′ (X) = 2(X −
α)g(X) + (X − α)2 g ′ (X) となり，α が f (X) と f ′ (X) の共通根になる．
逆に，f (X) と f ′ (X) の共通根 α があったとする．すると割り算の原理か
ら f (X) = (X − α)q(X) となり，f ′ (X) = q(X) + (X − α)q ′ (X) となる．
f ′ (X) が α を根にもつので，割り算の原理より X − α|f ′ (X) となるので，
上の式より，X − α|q(X) である．すなわち，q(X) = (X − α)q1 (X) と書
け，f (X) = (X − α)2 q1 (X) となる．
定理 5.17
□
p を素数，n を 1 以上の自然数とすると，pn 個の元からなる体
が存在する．一般に，F が有限体ならば F の n 次拡大体が存在する．
証明 F を有限体とし，#F = l，q = ln とする．F の拡大体で大きさ q
のものを見つければよい．F [X] の元 X q − X の分解体を L とする．まず，
X q − X の L における解の集合を S とする．ch(F ) = p とすると l は p の
べきでさらに q もそのべきなので，p · 1 = 0 から q · 1 = 0 であることに注
意すると (X q − X)′ = qX q−1 − 1 = −1 となり，X q − X と (X q − X)′ は
共通根をもたない．したがって，X q − X は q 個以上の根を L でもつ．素因
数分解の一意性より，#S = q である．
この S が体になることを示す．q = pm とする．σ = Frm とすると，σ
は L から L への単写準同型である．σ(x) = xq なので，x ∈ L に対し，
σ(x) = x と x ∈ S は同値になる．
まず，0, 1 ∈ S は明らか．次に x, y ∈ S とする．σ(x+y) = σ(x)+σ(y) =
x + y なので x + y ∈ S ．また，σ(xy) = σ(x)σ(y) = xy なので xy ∈ S ．
また，xx−1 = 1 より σ(xx−1 ) = σ(1)．したがって，σ(x)σ(x−1 ) = 1．
σ(x) = x より，xσ(x−1 ) = 1．よって，σ(x−1 ) = x−1 となり，x−1 ∈ S で
ある．
これで S が q 元体であることが示せた．
23
□
K/F を有限体の n 次拡大とし，α ∈ K を K の原始元とする．α の F
上の最小多項式を f (X) とすると f (X) は n 次で K ∼
= F [X]/(f (X)) とな
ることがこれまでの事実によりわかる．f (X) は F [X] の既約多項式である
が，X mod f (X) が原始元になるので，f (X) を F 上の原始既約多項式と
呼ぶ．これは X q − X の因数である．
例 5.18
(1) F2 の元は 2 個で，X 2 − X の根の全体であり，それは 0 と 1
である．
(2) F2 の 2 次拡大は F4 (22 = 4) である．F2 上の既約 2 次式を f (X) と
すると F2 [X]/(f (X)) は F2 の 2 次拡大体で α = X mod f (X) が f (X) の
根になるから，α の最小多項式は f (X) である．すると，F2 [X] において
f (X)|X 4 − X となる．
X 4 − X = X(X − 1)(X 2 + X + 1) となるので，X 2 + X + 1 が F2 上の
既約 2 次式のすべてである．2 次拡大が存在するので，2 次の既約多項式は
存在し，これになる．原始既約多項式は必ず存在するのでこれは原始既約多
項式でもある．また 4 − 1 = 3 は素数なので，F×
4 の要素はすべて原始元で
ある．
(3) F2 の 3 次拡大は F8 (23 = 8) である．F2 [X] で因数分解すると X 8 −
X = X(X − 1)(X 3 + X + 1)(X 3 + X 2 + 1) となる．X 8 − X は重根をもた
ないので，F2 [X] における 1 次の因数は X と X − 1 だけである．X 8 − X
が 2 次の既約因子をもつとすると，F8 が F4 を部分体にもつことになる．F4
を部分体にもつ体は F4 ベクトル空間になるので大きさが 4 のべきになる．
8 は 4 のべきではないのでこれはありえない．因数分解がわかっていなくて
も，4 次以上の既約因子をもつとすると F2 の 4 次以上の拡大体となるので
これもあり得ない．したがって，X 8 − X は 2 つの 3 次既約多項式を因子に
もつ．F2 上の 3 次既約多項式はこれだけである．F×
8 の位数は 7 で素数な
ので，その要素はすべて原始元になる．したがって，F2 上の 3 次既約多項
式はすべて原始既約多項式である．
24
(4) F2 の 4 次拡大は F16 (24 = 16) である．拡大次数を考えるとこの部
分体は F2 と F4 だけである．F4 は X 4 − X の根の集合なので，F16 内
では同型を除かなくても 1 通りしかない．F2 [X] で X 16 − X = X(X −
1)(X 2 + X + 1)(X 4 + X 3 + X 2 + X + 1)(X 4 + X 3 + 1)(X 4 + X + 1)
である．F2 上の既約因子は 4 次以下であるが，重根がないことも併せて考
えると，1 次 2 つ，2 次 1 つ (1 通りしかない) で 3 次の既約因子はない．
したがって，残りの 3 つの 4 次式は既約である．F2 上の既約な 4 次式は
この 3 つである．F×
16 の位数は 15 である．これは巡回群なので，原始元
(乗法群の生成元) は φ(15) = φ(3 × 5) = φ(3)φ(5) = (3 − 1)(5 − 1) = 8
個である．(φ(x) は Euler 関数．この事実はこの後で示される．) 4 次式の
根は 4 つずつあり，原始既約多項式の根はすべて原始元になるから，3 つ
の 4 次式のうち 2 つが原始既約多項式で，そうでないものが 1 つあるこ
とがわかる．位数が 5 の元が 4 つ，位数が 3 の元が 2 つあるはずだが，
X 4 + X 3 + X 2 + X + 1 の 4 つの根の位数が 5 で，X 2 + X + 1 の 2 つの根の
位数が 3 である．F16 ∼
= F2 [X]/(X 4 + X 3 + X 2 + X + 1) で計算してみる．
降べきに書いたときの係数の 2 進列で表示すると次のようになる．たとえば
X = 10 で，X 4 + X 3 + X 2 + X + 1 = 11111 である．すべて，mod 11111
で計算する．102 = 100, 103 = 1000, 104 = 10000 ≡ 1111 (mod 11111),
105 ≡ 11110 ≡ 1 (mod 11111).
F16 ∼
= F2 [X]/(X 4 + X + 1) という表示で計算してみる．mod 10011
で計算すると 10 が原始元になっている．(問．これを確かめよ．105 ̸≡ 1
(mod 10011) を確かめればよい．) 103 = 1000 が mod 10011 で位数 5 に
なる．これが，X 4 +X 3 +X 2 +X +1 の根になっていることを確かめてみる．
x = 1000 とすると，x+1 = 1001，x2 +x+1 = (x+1)x+1 = 1001001 ≡ 101
(mod 10011)，x3 + x2 + x + 1 = (x2 + x + 1)x + 1 = 101001 ≡ 1111
(mod 10011)，x4 + x3 + x2 + x + 1 = (x3 + x2 + x + 1)x + 1 = 1111001 ≡ 0
(mod 10011)．たしかになっている．
25
(5) F2 の 5 次拡大は F32 (25 = 32) である．拡大次数を考えるとこの部分
体は F2 だけである．したがって，X 32 − X を既約な因子に因数分解すると
2 つの 1 次式 (X(X − 1)) と (32 − 2)/5 = 6 つの既約な 5 次式に因数分解で
きる．F2 上既約な 5 次の 1 変数多項式はこの 6 つだけである．F×
32 の位数
は 31 で素数なので，その要素はすべて原始元である．したがって，5 次の
既約多項式は 6 つとも原始既約多項式である．
この節の最後に，定理 5.12 を証明しよう．もう少し一般に次の定理が成
り立つ．
定理 5.19
体 K の乗法群 K × の有限部分群は巡回群である．
この定理において，K は有限でなくてもよい．K = R のとき K × の有限
部分群は {1} と {−1, 1} しかないが，K = C に対しては e2πi/n で生成され
る位数 n の群がある．
(G, ·, 1) を群とし，a ∈ G とする．a の位数が n のとき，m ∈ Z
に対し m mod n 7→ am により，(加法群) Z/(n) ∼
= ⟨a⟩ である．ここで，
補題 5.20
⟨a⟩ は a で生成される G の部分群 (巡回群と呼ぶ) である．
証明 補題の写像が群の全射準同型で，well-defined なことを示せばよい．
これは簡単である．Z (加法群) → ⟨a⟩ (m 7→ am ) が群の全射準同型である
ことを示して，群の準同型定理を使ってもよい．
補題 5.21
□
加法群 Z/(n) の位数 n の要素の個数は φ(n) = n と互いに素な
整数の剰余類の個数である．(φ(n) を Euler 関数と呼ぶ．)
証明 φ(n) は Z/(n) の乗法群の位数でもあることを注意しておく．a が n
と互いに素とする．するとユークリッドの互除法により ab ≡ 1 (mod n) と
なる b ∈ Z が存在する．a の位数を d > 0 とすると da ≡ 0 (mod n) である
が，d ≡ dab ≡ 0 (mod n) である．したがって，n|d となり，d = n となる．
26
a と n が互いに素でないとすると 1 より大きい公約数 b をもつ．a = a′ b，
n = n′ b とすると 1 < n′ < n で，n′ a = n′ a′ b = a′ n ≡ 0 (mod n) となり，
a の位数 ≤ n′ < n である．
補題 5.22
□
有限加群 G の要素 a ∈ G の位数は #G の約数である．(G が有
限非可換群であってもこの定理は成り立つ．)
証明 G の演算を +，単位元を 0 とする．a ∈ G とする．すると，x 7→ x+a
は G から G への全単射になる．#G = n で G = {b1 , . . . , bn } とする．する
と，G = {b1 + a, . . . , bn + a} である．G の要素すべての和は加える順によ
らないから，b1 + . . . + bn = (b1 + a) + . . . + (bn + a) = b1 + . . . + bn + na．
したがって，na = 0．a の位数を d として n = qd + r，0 ≤ r < d とすると
0 = na = qda + ra = ra．r < d より，位数の定義から r = 0 である．した
□
がって，d|n である．
補題 5.23
n > 0，d|n とすると Z/(n) の位数 d の元はちょうど φ(n) 個存
在する．したがって，
∑
φ(d) = n
d|n
証明 d|n とする．a = n/d とすると a の位数は d である．⟨a⟩ は位数 d の
加法群で，Z/(d) と加法群として同型になる．
補題 5.21 より Z/(d) の中に位数 d の要素が φ(d) 個存在するので，⟨a⟩ の
中にもそれだけある．a′ = qa + r, 0 < r < a とすると da′ = qda + dr ≡ dr
(mod n) となり，0 < r < a = n/d より 0 < dr < n である．すなわち，
da′ ̸≡ 0 (mod n) となり，a′ の位数は d でない．すなわち，位数 d の元は
すべて ⟨a⟩ の元である．すなわち，Z/(n) の位数 d の元はちょうど φ(n) 個
存在する．
Z/(n) の元の位数は n の約数なので，位数ですべての元を分類することが
できる．したがって，上の公式が成り立つ．
27
□
定理 5.19 の証明．K × の部分群 G の大きさを n とする．d|n に対し，位数
d の元 x は xd = 1 の解である．このような元 x が存在すると，⟨x⟩ の元は
ちょうど d 個あるが，これらが xd = 1 の K における解すべてである．し
たがって位数 d の元はすべて ⟨x⟩ に属し，その数はちょうど φ(d) 個である．
G の元の個数を位数で分類して数えると
∑
d|n
φ(d) = n 以下となり，位数
d の元がないような d|n が存在すると n より真に小さくなる．したがって，
d|n ならば位数 d の要素が存在する．特に位数 n の要素が存在し，G はその
□
元によって生成される．
この定理は加法群の基本定理によってもすぐに証明できる．
28
6
Reed-Solomon 符号
6.1
Reed-Solomon 符号の定義
ここまでの知識で，Reed-Solomon 符号と呼ばれる誤り訂正符号が説明
できる．一般に有限体 Fq に対し，誤り訂正能力 t の Reed-Solomon 符号
RS(q, t) が定義される．(2t + 1 が符号の「最小距離」なので，RS(q, 2t + 1)
と表記されることが多い．) Reed-Solomon 符号は CD，DVD，放送，バー
コード，宇宙探査機などで広く使われている．
Fq 上の Reed-Solomon 符号は，Fq の要素を (q − 1) 個並べた列 (ベクト
ル) である．これは Fq [y] の要素 (多項式) として (q − 2) 次多項式と考える．
1 つの係数を符号語 (codeword) と呼ぶ．(q − 1) 個の係数 (符号語) のうち t
個が何らかの理由で壊れて別のものになっても，正しい符号 (多項式) に復
元できるようになっている．q の値が大きければ，誤り訂正能力 t は大きく
したり，小さくしたりできる．
q = 28 のときの Fq = F2 [x]/(f ) (f ∈ F2 [x] は 8 次の既約多項式，
例えば f = 110000111 = x8 + x7 + x2 + x + 1) がよく使われるが，
F929 = {0, 1, 2, · · · , 928} を使った 2 次元バーコード (PDF417) もある．
定義 6.1（Reed-Solomon 符号） Fq の原始元 α を 1 つ決める．また「誤
り訂正能力」t を 1 つ決める．
g(y) = (y − α)(y − α2 ) · · · (y − α2t−1 )(y − α2t )
とする．
RS(q, t) = {f ∈ Fq−1
| Fq [y] の要素として f (y) ≡ 0
q
(mod g(y))}
| Fq において f (αi ) = 0 (i = 1, 2, . . . , 2t)}
= {f ∈ Fq−1
q
を Reed-Solomon 符号 (の集合) と呼ぶ．g(y) を RS(q, t) の生成多項式と
呼ぶ．
29
RS(q, t) の要素はデータに対する符号の空間として用意されたものであ
る．与えられたデータを RS(q, t) の要素に変換する方法はいくつかあるが，
次の方法がよく使われる．
定義 6.2（Reed-Solomon 符号への符号化） RS(q, t) の生成多項式を g と
する．Fq−2t−1
の要素は次の方法で，RS(q, t) の要素に変換される．
q
f = (a0 , . . . , aq−2t−2 ) ∈ Fq−2t−1
に対し，次のように順に計算して，f˜ を
q
求める．
f1 := f · y 2t = (a0 , . . . , aq−2t−2 , 0, . . . , 0)
| {z }
2t 個
r := f1 mod g
f˜ := f1 + (−r) = (a0 , . . . , aq−2t−2 , ∗, . . . , ∗)
| {z }
−r
すると，f˜ mod g = 0，すなわち f˜ ∈ RS(q, t) となる．
f˜ は f の係数ベクトルと −r の係数ベクトルをつないだものになって
いる．
−r という余分な情報をつけてデータを大きくすることにより，データの
破損に対して強くしていることになる．
例 6.3 RS(8, 2) を考える．F8 = F2 [x]/(1011) と書ける．α = 10 = x と
する．α のべきを計算すると次の表になる．
α α2
10 100
α3
11
α4
110
α5 α6
111 101
α7
1
α3 = 103 mod 1011 = 1000 mod 1011 = 11,
α5 = (110 × 10) mod 1011 = 111,
α6 = (111 × 10) mod 1011 = 101,
α7 = (101 × 10) mod 1011 = 1
30
となる．RS(8, 2) の生成多項式は
g(y) = (y − α)(y − α2 )(y − α3 )(y − α4 )
= (y + α)(y + α2 )(y + α3 )(y + α4 )
= (y 2 + α4 y + α3 )(y 2 + α6 y + 1)
= y 4 + α3 y 3 + y 2 + αy + α3
係数ベクトルは
g = (1, α3 , 1, α, α3 )
= (1, 11, 1, 10, 11)
RS(8, 2) の要素は g(y) を因数にもつ高々 6 次の多項式全体である．係数
ベクトルの長さは 7(以下) である．
F38 の要素は次のように RS(8, 2) の要素に変換できる．
F8 の要素をすべて長さ 3 の 2 進列で表現することにすると F38 の要素は
長さ 9 の 2 進列と考えられる．
f = 010111101 = (010, 111, 101) = (α, α5 , α6 ) に対し，
f1 = f · y 4 = (α, α5 , α6 , 0, 0, 0, 0)
f1 mod g = (α, 0, 0, α5 )
f˜ = (α, α5 , α6 , α, 0, 0, α5 )
= 010 111 101 010 000 000 111
f1 mod g の計算は次の通りである．
1
α3
1 α
α
3
α )α
α
1
α5
α4
1
1
31
α2
α6
α
α5
α3
α2
α2
0
α2
α2
1
α6
α5
α
0
α4
α4
α
α2
α2
0
0
0
α3
α3
α3
0
α5
α5
命題 6.4 定義 6.2 の符号化法は，Fqq−2t−1 と RS(q, t) の間の 1 対 1 対応を
与えている．したがって，RS(q, t) の要素数は q q−2t−1 である．
証明 Fq−1
に属するベクトルを多項式と見るとき，上位 q − 2t − 1 個の係
q
数を任意に決めても，下位の 2t 個の係数を調整すれば RS(q, t) の要素にで
きることがこの符号化からわかる．
逆に 2 つの多項式 f1 , f2 ∈ R(q, t) の上位 q − 2t − 1 個の係数が一致する
ならば，f1 − f2 は 2t − 1 次以下の多項式になる．一方，f1 ≡ 0 (mod g)，
f2 ≡ 0 (mod g) より，f1 − f2 ≡ 0 (mod g) となる．g が 2t 次で f1 − f2 が
2t − 1 次以下なので，(f1 − f2 ) mod g = f1 − f2 となり，f1 = f2 である．
□
6.2
Reed-Solomon 符号の誤り訂正能力
定義 6.5（Hamming 距離） f1 = (a0 , a1 , . . . , am−1 )，f2 = (b0 , b1 , . . . ,
bm−1 ) を Fm
q の要素とするとき，{i | ai ̸= bi } の要素の個数を f1 と f2 の
Fq 上の Hamming 距離と呼ぶ．
f1 , f2 ∈ RS(q, t)，f1 ̸= f2 のとき，f1 と f2 の Fq 上の Hamming 距離が
2t + 1 以上であることを示す．これがわかれば，f ∈ RS(q, t) に対し，f の
係数のいくつかが変更を受けて f1 ∈ Fq−1
となったとき，その変更を受けた
q
係数の個数が t 以下のとき，f1 と Hamming 距離が t 以下の RS(q, t) の要
素はもとの f しかない．したがって，原理的には誤りを修正できる．
定義 6.6 α を Fq の原始元とする．Φα : Fqq−2t−1 → Fq−1
を次のように定
q
義する．f ∈ Fq−2t−1
を 1 変数多項式 f (y) と考えて，
q
Φα (f ) = (f (αq−2 ), f (αq−3 ), . . . , f (α), f (1))
と定義する．変換 Φ を離散的 Fourier 変換と呼ぶ．
32
任意の Fq 係数多項式 f に対し，この Φα (f ) の定義は意味をもつ．
命題 6.7 次が成り立つ．
(1) {Φα (f ) | f ∈ Fq−2t−1
} の異なる要素の Fq 上の Hamming 距離は
q
2t + 1 以上．
(2) Φα は 1 対 1 写像である．
(3) RS(q, t) = {Φα (f ) | f ∈ Fq−2t−1
}.
q
(4) RS(q, t) の異なる要素の Fq 上の Hamming 距離は 2t + 1 以上．
証明 以下，演算は Fq 上の多項式としての演算とする．また，Φα を単に
Φ と書く．
(1) f1 , f2 ∈ Fqq−2t−1 とすると，定義から Φ(f1 ) − Φ(f2 ) = Φ(f1 − f2 ) であ
る．Φ(f1 ) ̸= Φ(f2 ) のとき，f3 = f1 − f2 とすれば，Φ(f1 ) − Φ(f2 ) = Φ(f3 )
で，f3 ̸= 0 である．
Φ(f3 ) = (f3 (αq−2 ), f3 (αq−3 ), . . . , f3 (α), f3 (1))
であるが，f3 (y) は q − 2t − 2 次以下の 0 でない多項式だったので，その根
(f3 (y) = 0 となる y の個数) は高々 q − 2t − 2 個である．すなわち， Φ(f3 )
の成分 (係数) のうち，0 となるものは高々 q − 2t − 2 個となり，残りの成分
は 0 でない．(q − 1) − (q − 2t − 2) = 2t + 1 なので，Φ(f3 ) の 2t + 1 個以
上の成分は 0 でない．これは，Φ(f1 ) と Φ(f2 ) の Hamming 距離が 2t + 1 以
上であることを意味する．
(2) f1 ̸= f2 とする．Φ(f1 ) ̸= Φ(f2 ) を示せばよい．f3 = f1 − f2 とする
と f3 ̸= 0 である．(1) の議論から，Φ(f1 ) − Φ(f2 ) = Φ(f3 ) ̸= 0 である．し
たがって，Φ(f1 ) ̸= Φ(f2 ) である．
(3) 定義より，f1 , f2 ∈ Fq−2t−1
に対し，Φ(f1 + f2 ) = Φ(f1 ) + Φ(f2 ) で，
q
さらに，c ∈ Fq とすると Φ(cf1 ) = cΦ(f1 ) である．f ∈ Fqq−2t−1 は
f (y) = c0 y q−2t−2 + c1 y q−2t−3 + · · · + cq−2t−3 y + cq−2t−2
33
と書けるので，f (y) = y j (j = 0, 1, . . . , q−2t−2) のときに，Φ(f ) ∈ RS(q, d)
を示せばよい (RS(q, t) が多項式の和と Fq の要素倍の演算で閉じているこ
とも定義からすぐにわかる)．h = Φ(f ) とすると，
h = Φ(f ) = ((αq−2 )j , (αq−3 )j , . . . , αj , 1j )
= ((αj )q−2 , (αj )q−3 , . . . , αj , 1).
h を y の関数の形で書くと
h(y) = (αj )q−2 y q−2 + (αj )q−3 y q−3 + · · · + αj y + 1
= (αj y)q−2 + (αj y)q−3 + · · · + αj y + 1.
主張 1 h(α) = h(α2 ) = · · · = h(α2t ) = 0.
h(y) = y j で，j は 0, 1, . . . , q − 2t − 2 のどれかである．1 ≤ k ≤ 2t とす
ると，1 ≤ j + k ≤ q − 2 である．
h(αk ) = (αj αk )q−2 + (αj αk )q−3 + · · · + αj αk + 1
= (αj+k )q−2 + (αj+k )q−3 + · · · + αj+k + 1.
さて，αq−1 = 1 だったので，(αq−1 )j+k = 1 である．よって，(αj+k )q−1 = 1
となる．β = αj+k とすると，α の位数が q−1 であることと 1 ≤ j+k ≤ q−2
より，β ̸= 1 かつ β q−1 − 1 = 0 である．
(β − 1)(β q−2 + β q−3 + · · · β + 1) = β q−1 − 1 = 0
と β − 1 ̸= 0 より，
β q−2 + β q−3 + · · · β + 1 = 0
となる．すなわち， h(αk ) = 0 である．
Φ が単射だったので，{Φ(f ) | f ∈ Fqq−2t−1 } の要素の個数は q q−2t−1
である．一方，命題 6.4 より，RS(q, t) の要素の個数も q q−2t−1 である．
{Φ(f ) | f ∈ Fq−2t−1
} ⊂ RS(q, t) なので，この 2 つの集合は一致する． □
q
34
例 6.8 例 6.3 の RS(8, 2) を考える．F8 = F2 [x]/(1011) で，α = 10 であ
る．例 6.3 より，
(α, α5 , α6 , α, 0, 0, α5 ) ∈ RS(8, 2)
であった．
h = (α3 , 1, α6 ) (h(y) = α3 y 2 + y + α6 )
とすると
Φα (h) = (α, α5 , α6 , α, 0, 0, α5 )
である．実は c = (α, α5 , α6 , α, 0, 0, α5 ) とすると
Φα−1 (c) = h
である．
一般に，Fq の原始元 α と f ∈ Fq−1
に対し，
q
−Φα−1 (Φα (f )) = f,
−Φα (Φα−1 (f )) = f
である．F2 がベースの場合は −1 = 1 なので，符号の − は必要ない．
6.3
Reed-Solomon 符号の誤り訂正
RS(q, t) のデータに t 箇所以下の誤りが生じたとき (送信中に雑音がはい
る，CD にきずがつく，バーコードがかすれる，読取で少し失敗する等)，そ
れを復元する方法を述べる．この方法はいくつも提案されているが，ここで
はユークリッドの互除法を使う方法を紹介する．
ここでは，添字の付け方を多項式の次数にあわせる．
f = (cq−2 , cq−3 , . . . , c1 , c0 ) ∈ RS(q, t) に誤りが生じて f1 になったとす
る．変更を受けた係数の位置 (次数) の集合を I とすると f1 (y) = f (y) +
∑
i∈I
ei y i (ei ∈ Fq ) となる．e(y) =
∑
i∈I
ei y i を誤り多項式と呼ぶ．誤り
多項式が求まればもとのデータが復元できる．
最初に方法を述べ，なぜ求まるかはあとで説明する．
35
誤り多項式の求め方
f (y) ∈ RS(q, t)，α ∈ Fq を RS(q, t) で使う原始元とする．f1 (y) =
f (y) + e(y) で，e(y) の 0 でない係数をもつ次数の集合を I とすると，
e(y) =
∑
ei y i
i∈I
である．|I| ≤ t のとき，誤り位置の集合 I と係数 ei を求めるのが目標と
なる．
S := (f1 (α2t ), f1 (α2t−1 ), . . . , f1 (α)) とする．
S を多項式と考える．すると，2t − 1 次以下の多項式になる．もし，誤り
がなければ (すなわち e(y) = 0 ならば) RS(q, t) の定義より，S(y) = 0 であ
る．以下，S(y) ̸= 0，すなわち誤りがあったとする．
S = S(y) をシンドローム多項式と呼ぶ．
次に，
y 2t ≡ 0 · S(y) (mod y 2t )
(1)
S(y) ≡ 1 · S(y) (mod y 2t )
(2)
の左辺に対してユークリッドの互除法を適用して，
Ω(y) ≡ Λ(y) · S(y) (mod y 2t )
(3)
となる互いに素な多項式 Ω(y) と Λ(y) を
deg Λ(y) ≤ t,
deg Ω(y) < deg Λ(y)
となるように求める．この方程式は鍵方程式 (key equation) と呼ばれる．
|I| ≤ t のとき，ユークリッドの互除法により解が必ず求まることが知られて
いる．さらに，Λ(0)−1 (Fq における乗法の逆元) を (3) の両辺にかけ，Λ(y)
の定数項が 1 になるようにしておく．
36
Λ(y) = 0 の Fq における解をすべて求める．実は，
∏
Λ(y) =
(1 − αi y) (I は誤りの位置)
i∈I
となっており，Λ(y) = 0 の根は丁度 {α−i | i ∈ I} である．よって，
i ∈ I ⇐⇒ Λ(α−i ) = 0
である．これで，誤り位置 I がわかる．Λ(y) を誤り位置検出多項式 (error
locator polynomial) と呼ぶ．
さらに，i ∈ I に対し，e(y) の y i の係数 ei は，
−i
i
−i
Ω(α ) = ei α χi (α ),
∏
χi (y) =
(1 − αj y)
j∈I,j̸=i
により求まる．
例 6.9 f = (α, α5 , α6 , α, 0, 0, α5 ) に誤りが生じて，f1 = (α, α5 , α4 , α, 0, α2 , α5 )
に な っ た と す る ．わ か っ て い る の f1 で け で あ る ．誤 り 多 項 式 は
e(y) = α3 y 4 + α2 y であるが，これはまだわからない．まず，
S = (f1 (α4 ), f1 (α3 ), f1 (α2 ), f1 (α)) = (α, α6 , 0, α)
である．
y 4 ≡ 0 · S(y)
(mod y 4 )
(1)
αy 3 + α6 y 2 + α ≡ 1 · S(y)
(mod y 4 )
(2)
の左辺に着目してユークリッドの互除法の計算を行う．
α
α6
α6 α4
0 α)1 0
1 α5
α5
α5
37
0
0
0
α3
α3
0 0
1
1
0 α5
1 α5
を使って，(1) − (2) × (α6 y + α4 ) (両辺の演算) を考えると
α3 y 2 + y + α5 ≡ (α6 y + α4 ) · S(y) (mod y 4 )
(3)
次に
α3
α5
1 α5 ) α
α
α5
α6
α5
α
α
0
α3
α3
α5
α2
α
α
α3
1
を使って，(2) − (3) × (α5 y + α5 ) を考えると
α2 y + 1 ≡ (α4 y 2 + αy + α6 ) · S(y) (mod y 4 )
(4)
となる．左辺の次数が右辺の S の係数の次数より低くなったので，鍵方程
式の解が得られた．(実は，左辺と右辺の S の係数が互いに素という条件は
自動的に満たされている．) α6 の逆元である α を (4) の両辺にかけると，
α3 y + α ≡ (α5 y 2 + α2 y + 1) · S(y) (mod y 4 )
次に誤り位置検出多項式 Λ(y) = α5 y 2 + α2 y + 1 の根を求める．y =
α, α2 , . . . について調べると，y = α3 のとき，Λ(y) = 0 となる．(α3 )−1 =
α4 なので，4 次の係数が誤りの 1 つである．α4 y − 1 で Λ(y) は割り切れ，
Λ(y) = (αy − 1)(α4 y − 1) となる．
すなわち，誤りが 1 次と 4 次の係数であることがわかった．誤り多項式を
e(y) = e4 y 4 + e1 y
と置くと，
α3 y + α = e1 α(α4 y + 1) + e4 α4 (αy + 1)
となる (理由は次節)．y = α−1 を代入すると，α2 + α = e1 α(α3 + 1) とな
り，e1 = α2 が得られる．
38
y = α−4 を代入すると，α−1 + α = e4 α4 (α−3 + 1) となり，e4 = α3 が得
られる．
これで，誤り多項式
e(y) = α3 y 4 + α2 y
が求まる．
誤り多項式が求まる理由
上の「誤り多項式の求め方」を詳しく分析する．鍵方程式の解の存在と一
意性がポイントとなる．
以下，f (y) ∈ RS(q, t)，α ∈ Fq を RS(q, t) で使う原始元とする．f1 (y) =
f (y) + e(y) で，e(y) =
∑
i∈I
ei y i ，i ∈ I ならば ei ̸= 0 とする．さらに，
|I| ≤ t とする．
定理 6.10
S := (f1 (α2t ), f1 (α2t−1 ), . . . , f1 (α)) とする．鍵方程式
Ω(y) ≡ Λ(y) · S(y)
deg Λ(y) ≤ t,
(mod y 2t )
deg Ω(y) < deg Λ(y)
Ω(y) と Λ(y) は互いに素
に対し，次が成り立つ．
(1) この方程式の 1 つの解は
∏
Λ(y) =
(1 − αj y),
Ω(y) =
j∈I
∑
ei αi χi (y)
i∈I
∏
ここで， χi (y) =
j∈I,j̸=i
であり，解はこれだけである．
39
(1 − αj y) =
Λ(y)
1 − αi y
(2) この方程式は，
y 2t ≡ 0 · S(y) (mod y 2t )
S(y) ≡ 1 · S(y) (mod y 2t )
の左辺に着目して y 2t と S(y) の最大公約数 (公因子) をユークリッド
の互除法で求めようとすると途中で鍵方程式の解を得る．y 2t /S(y)
の商を q2 (y)，余りを r2 (y) とすると
y 2t = q2 (y) · S(y) + r2 (y)
となるが，上の連立方程式は
S(y) ≡ 1 · S(y)
(mod y 2t )
r2 (y) ≡ −q2 (y) · S(y) (mod y 2t )
と同値となる．この操作を次数の条件が満たされるまで繰り返すと解
が得られる．
証明 (1) 1 ≤ j ≤ 2t のとき，f (αj ) = 0 なので，f1 (αj ) = f (αj ) + e(αj ) =
e(αj ) である．成分毎に考えると
S = (e(α2t ), e(α2t−1 ), . . . , e(α))
である．i ∈ I に対し，
Si = (ei · (α2t )i , ei · (α2t−1 )i , . . . , ei · αi )
とすると
S=
∑
Si
i∈I
である．各 i について Si (y) は等比級数になっており，その和は簡単な形で
ある．高校で習うのは実数の場合であるが，同じ議論がこの場合もできる．
Si (y) = ei αi ((αi y)2t−1 + (αi y)2t−2 + . . . + αi y + 1)
であるが
40
αi ySi (y) = ei αi ((αi y)2t + (αi y)2t−1 + . . . + (αi y)2 + αi y)
として両辺を引くと
(1 − αi y)Si (y) = ei αi (1 − (αi y)2t )
となり，
(1 − αi y)Si (y) ≡ ei αi
(mod y 2t )
である．
以下の議論は 1/(1 − αi y) の i ∈ I に関する和を念頭に行なう．通分の操
作から次の χi (y) を考えるのが自然である．
χi (y) =
∏
j
i
j∈I,j̸=i (1 − α y) に対し χi (y)(1 − α y) =
∏
j∈I (1 − α
j
y) なの
で，上の両辺に χi (y) をかけると


∏

(1 − αj y) Si (y) ≡ ei αi χi (y) (mod y 2t )
j∈I
である．i ∈ I すべてについて両辺の和をとると


∏

(1 − αj y) S(y) ≡
j∈I
ここで，
∏
j∈I (1
∑
ei αi χi (y) (mod y 2t )
i∈I
− αj y) は |I| 次式 (|I| ≤ t) で，
∑
i∈I
ei αi χi (y) は |I| − 1
次以下の式である．
また，
∑
i∈I
∏
j∈I (1
− αj y) の因数は 1 次式 1 − αj y (j ∈ I) のみであるが，
ei αi χi (y) に α−j (j ∈ I) を代入すると，
∑
ei αi χi (α−j ) = ej αj χj (α−j ) ̸= 0
i∈I
である．したがって，因数定理より，
∏
互いに素であることがわかる．
41
j
j∈I (1 − α y) と
∑
i∈I
ei αi χi (y) は
以上より，
Λ(y) =
∏
(1 − α y),
j
Ω(y) =
j∈I
∑
ei αi χi (y)
i∈I
が鍵方程式の 1 つの解であることがわかる．
主張 1 鍵方程式の解は定数倍を除いて 1 組しかない．すなわち，
Ω1 (y) ≡ Λ1 (y) · S(y) (mod y 2t )
Ω2 (y) ≡ Λ2 (y) · S(y) (mod y 2t )
でどちらも鍵方程式の条件を満たすならば，
Ω2 (y) = cΩ1 (y),
Λ2 (y) = cΛ1 (y)
となる c ∈ Fq が存在する．
鍵方程式の解として Λ(y) = Λ1 (y)，Ω(y) = Ω1 (y) と Λ(y) = Λ2 (y)，
Ω(y) = Ω2 (y) があったとする．すると，
Ω1 (y) ≡ Λ1 (y) · S(y) (mod y 2t )
(a)
Ω2 (y) ≡ Λ2 (y) · S(y) (mod y 2t )
(b)
であるが，(a) の両辺に Λ2 (y) をかけ，(b) の両辺に Λ1 (y) をかけると
Λ2 (y)Ω1 (y) ≡ Λ2 (y)Λ1 (y) · S(y) (mod y 2t )
Λ1 (y)Ω2 (y) ≡ Λ1 (y)Λ2 (y) · S(y) (mod y 2t )
となる．両辺同士を引くと
Λ2 (y)Ω1 (y) − Λ1 (y)Ω2 (y) ≡ 0 (mod y 2t ).
この左辺は 2t − 1 次以下の多項式なので，多項式として
Λ2 (y)Ω1 (y) − Λ1 (y)Ω2 (y) = 0.
42
すなわち，
Λ2 (y)Ω1 (y) = Λ1 (y)Ω2 (y).
体係数の 1 変数多項式については，既約因子分解の一意性が定数倍 (係数体
の要素倍) を除いて成り立つことが知られている (証明は，整数の素因数分
解の一意性の証明と同様で，割り算の原理が本質的である)．Ω1 (y) と Λ1 (y)
が互いに素なので Ω1 (y) は Ω2 (y) を割り切る．また，Ω2 (y) と Λ2 (y) も互
いに素なので，Ω2 (y) は Ω1 (y) を割り切る．したがって，次数を考えると，
Ω2 (y) は Ω1 (y) の定数倍である．同様に，Λ2 (y) も Λ1 (y) の定数倍である．
Ω2 (y) = cΩ1 (y)，Λ2 (y) = c′ Λ1 (y) (c, c′ ∈ Fq − {0}) とすると
c′ Λ1 (y)Ω1 (y) = cΛ1 (y)Ω1 (y)
となり，c = c′ がわかる．
(2) 証明の概略だけ述べる．連立合同式ではなく，次の連立方程式で考
える．
y 2t = 1 · y 2t + 0 · S(y)
(a)
S(y) = 0 · y 2t + 1 · S(y)
(b)
この左辺に着目してユークリッドの互除法を繰り返す．すなわち，上の式を
r0 (y) = a0 (y) · y 2t + b0 (y) · S(y)
(a)
r1 (y) = a1 (y) · y 2t + b1 (y) · S(y)
(b)
と考え，
ri−1 (y) = ai−1 (y) · y 2t + bi−1 (y) · S(y)
ri (y) = ai (y) · y 2t + bi (y) · S(y)
43
が得られているとき，ri−1 (y) = qi (y)ri (y) + ri+1 (y), deg ri+1 < deg ri と
なるように割り算で分解し，ai+1 (y) = ai−1 (y) − qi (y)ai (y)，bi+1 (y) =
bi−1 (y) − qi (y)bi (y) として，
ri+1 (y) = ai+1 (y) · y 2t + bi+1 (y) · S(y)
を導く．すると，数学的帰納法により次の主張 2 と主張 3 が証明できる．
主張 2 i ≥ 1 のとき，
deg bi+1 (y) = deg r0 (y) − deg ri (y) = 2t − deg ri (y),
deg bi+1 (y) > deg bi (y),
deg ri+1 (y) < ri (y).
主張 3
{
⇐⇒
{
y 2t = 1 · y 2t + 0 · S(y)
S(y) = 0 · y 2t + 1 · S(y)
ri (y) = ai (y) · y 2t + bi (y) · S(y)
ri+1 (y) = ai+1 (y) · y 2t + bi+1 (y) · S(y)
である．しかも，各等式の両辺を多項式倍して，辺々を加えることにより，
どちらの方向も導ける．
ri (y) の次数は i が大きくなるほど下がっていき，ri (y) が y 2t と S(y) の
最大公約数になったあと 0 になって終わる．
ri (y) = 0 のとき，deg bi (y) > 1 である．よって，deg ri (y) < deg bi (y)
となる最小の i がとれる．それを i0 としよう．取り方より，deg ri0 −1 (y) ≥
deg bi0 −1 (y) である．
主張 4
R(y) = A(y) · y 2t + B(y) · S(y),
44
deg R(y) < deg B(y)
とすると，
deg bi0 (y) ≤ deg B(y).
主張 3 により，
ri0 −1 (y) = ai0 −1 (y) · y 2t + bi0 −1 (y) · S(y)
ri0 (y) = ai0 (y) · y 2t + bi0 (y) · S(y)
に対し，ある多項式 u0 (y) と v0 (y) が存在して，
u0 (y)ri0 −1 (y) =
u0 (y)ai0 −1 (y) · y 2t
+) v0 (y)ri0 (y) =
v0 (y)ai0 (y) · y 2t
+
v0 (y)bi0 (y) · S(y)
1 · y 2t
+
0 · S(y)
y 2t
=
+ u0 (y)bi0 −1 (y) · S(y)
さらにある多項式 u1 (y) と v1 (y) が存在して，
u1 (y)ri0 −1 (y) =
u1 (y)ai0 −1 (y) · y 2t
+) v1 (y)ri0 (y) =
v1 (y)ai0 (y) · y 2t
+
v1 (y)bi0 (y) · S(y)
0 · y 2t
+
1 · S(y)
y 2t
=
+ u1 (y)bi0 −1 (y) · S(y)
よって，ある多項式 u(y) と v(y) が存在して，
u(y)ri0 −1 (y) =
u(y)ai0 −1 (y) · y 2t
+ u(y)bi0 −1 (y) · S(y)
+) v(y)ri0 (y) =
v(y)ai0 (y) · y 2t
+
v(y)bi0 (y) · S(y)
R(y) =
A(y) · y 2t
+
B(y) · S(y)
deg B < deg bi0 とすると，v(y)bi0 (y) と u(y)bi0 −1 (y) の次数が同じでな
ければ和の次数はさがらない．主張 2 より，deg bi0 (y) > deg bi0 −1 (y) なの
で，deg u(y) > deg v(y) かつ deg u(y) ≥ deg bi0 (y) − deg bi0 −1 (y) である．
よって，
deg u(y) + deg ri0 −1 (y) ≥ deg u(y) + deg bi0 −1 (y) ≥ deg bi0 (y)．
一方，
deg u(y)ri0 −1 (y) > deg v(y)ri0 (y) なので，deg R(y) = deg u(y)ri0 −1 (y) =
deg u(y) + deg ri0 −1 (y)．
45
deg R(y) < deg B(y) < deg bi0 より，deg u(y) + deg ri0 −1 (y) < deg bi0 ．
これは矛盾である．
主張 4 が示された．
鍵方程式で次数の条件を満たしているものがあるので，deg bi0 (y) ≤ t で
ある．したがって，主張 2 より，deg ri0 −1 (y) ≥ t である．
今度は，鍵方程式の解があるとすると，それは，ある u(y) と v(y) を使っ
て次のように得られる．
u(y)ri0 −1 (y) =
u(y)ai0 −1 (y) · y 2t
+ u(y)bi0 −1 (y) · S(y)
+) v(y)ri0 (y) =
v(y)ai0 (y) · y 2t
+
v(y)bi0 (y) · S(y)
R(y) =
A(y) · y 2t
+
B(y) · S(y)
このとき，u(y) ̸= 0 とすると，deg R(y) < t なので，deg v(y)ri0 (y) =
deg u(y)ri0 −1 (y) である必要がある．
deg ri0 (y) < deg ri0 −1 (y) なので，deg v(y) > deg u(y) である．さらに，
deg v(y) + deg ri0 (y) = deg u(y)ri0 −1 (y) ≥ t．
deg bi0 (y) > deg bi0 −1 (y) と deg v(y) > deg u(y) より，
deg B(y) = deg(u(y)bi0 −1 (y) + v(y)bi0 (y))
= deg v(y)bi0 (y)
= deg v(y) + deg bi0 (y)
> deg v(y) + deg ri0 (y)
≥ t．
これは，B(y) が鍵方程式の解の一部で deg B(y) ≤ t であることに反する．
従って，左辺が ri0 (y) の式の多項式倍で，鍵方程式の解が得られるはずで
ある．もし，ri0 (y) と bi0 (y) が互いに素でないとすると，鍵方程式の解も互
いに素でないことになり矛盾する．したがって，ri0 (y) と bi0 (y) は互いに素
であり，鍵方程式の定数倍を除いて一意になる解であることがわかる．
46
□
例
q 元体 Fq の原始元 α をとり，RS(q, 2) を考える．すなわち，誤り訂正能
力 2 の場合を考える．
f ∈ RS(q, 2) ⇐⇒ f (α) = f (α2 ) = f (α3 ) = f (α4 ) = 0
である．
Reed-Solomon 符号 f に対し誤り E が加わって，f1 になったとする．
シンドローム多項式 S(y) は次の通りである．
S(y) = f1 (α4 )y 3 + f1 (α3 )y 2 + f1 (α2 )y + f1 (α)
= E(α4 )y 3 + E(α3 )y 2 + E(α2 )y + E(α).
誤り位置が 2 箇所以内の誤り訂正には，次の鍵方程式の解 Ω(y)，Λ(y) を
求めればよい．
Ω(y) ≡ Λ(y)S(y) (mod y 4 )
deg Ω(y) < deg Λ(y) ≤ 2
Ω(y) と Λ(y) は互いに素
誤り箇所が誤り訂正能力以下の場合は，この鍵方程式の解は定数倍を除い
て一意的である．
さて，E(y) の y a の係数が ea ̸= 0 だったとする．
Sa (y) = ea αa (1 + αa y + α2a y 2 + α3a y 3 )
とおいて両辺を αa y 倍すると
αa ySa (y) = ea αa (αa y + α2a y 2 + α3a y 3 + α4a y 4 )
両辺をそれぞれ引くと
(1 − αa y)Sa (y) = ea αa (1 − α4a y 4 )
となるので
ea αa ≡ (1 − αa y)Sa (y) (mod y 4 ).
(i) 誤り箇所が 1 つの場合，E(y) = ea y a ，S(y) = Sa (y) と書けるので，
鍵方程式の解は定数倍を除いて
47
ea αa ≡ (1 − αa y)S(y) (mod y 4 )
だけである．
事実 1．
誤り箇所が 2 つ以内で，
C ≡ (1 − Ay)S(y) (mod y 4 ) (A, C ∈ Fq )
が成り立つとき，
E(y) = ea y a (誤り箇所は 1 つ)，
C = ea αa ，A = αa と書ける．
(ii) 誤り箇所が 2 つの場合，E(y) = ea y a + eb y b ，
S(y) = Sa (y) + Sb (y) と書ける．
ea αa ≡ (1 − αa y)Sa (y) (mod y 4 ),
eb αb ≡ (1 − αb y)Sb (y) (mod y 4 )
より，
ea αa (1 − αb y) + eb αb (1 − αa y)
≡ (1 − αa y)(1 − αb y)S(y) (mod y 4 )
鍵方程式の解は定数倍を除いてこれだけである．
事実 2．
誤り箇所が 2 つ以内で，
Cy + D ≡ (Ay 2 + By + 1)S(y) (mod y 4 )
A, B, C, D ∈ F8 ，Cy + D と Ay 2 + By + 1 は互いに素
が成り立つとき，
E(y) = ea y a + eb y b (誤り箇所は 2 つ)，
Ay 2 + By + 1 = (1 − αa y)(1 − αb y),
Cy + D = ea αa (1 − αb y) + eb αb (1 − αa y).
と書ける．
例 1．Fq = F8 = F2 [x]/(1011) = {0, 1, 10, 11, 100, 101, 110, 111}
48
で考える．1011 は x3 + x + 1 のこと (係数ベクトル) である．F8 の要素
は係数ベクトルで表現された 2 次以下の F2 係数多項式である．和 + は F2
係数多項式としての和 (桁ごとの mod 2 の和) で，積 · は F2 係数多項式と
してかけた後に 1011 で割った余りをとる演算とする．α = 10 とすると，α
のべきは次の表で表される．下の段が上の式の値である．
α
α2
α3
α4
α5
α6
α7
10 100 11 110 111 101 1
さて，RS(8, 2) の Reed-Solomon 符号を受信したところ，
f1 = (α, α, α6 , α, 0, 0, α5 )
であったとする．シンドローム多項式の係数を計算すると
f1 (α) = α · α6 + α · α5 + α6 · α4 + α · α3 + α5
= 1 + α6 + α3 + α4 + α5
= 1 + 101 + 11 + 110 + 111
= α4 ,
f1 (α2 ) = α2 ,
f1 (α3 ) = 1,
f1 (α4 ) = α5
となる．ユークリッドの互除法により，鍵方程式の解を求める．
(1) y 4 ≡ 0 · S(y) (mod y 4 )
(2) α5 y 3 + y 2 + α2 y + α4 ≡ 1 · S(y) (mod y 4 )
(3) α ≡ (α2 y + α4 ) · S(y) (mod y 4 )
(3) は (1) − (2) × 多項式 で得られる．
(α4 )−1 を (3) の両辺にかけると
α4 ≡ (α5 y + 1)S(y) (mod y 4 )
事実 1 より，誤り多項式は E(y) = ea y a と書け，a = 5 である．
また，事実 1 より，α4 = ea αa なので，ea = α6 である．したがって，も
との符号 f は
f = (α, α5 , α6 , α, 0, 0, α5 )
49
と推測される．
再び Reed-Solomon 符号を受信したところ，
f1 = (α, 1, α6 , 0, 0, 0, α5 )
であった．シンドローム多項式の係数を計算すると
f1 (α) = α，f1 (α2 ) = 0，f1 (α3 ) = α2 ，f1 (α4 ) = α4 である．
ユークリッドの互除法により，鍵方程式の解を求める．
(1) y 4 ≡ 0 · S(y) (mod y 4 )
(2) α4 y 3 + α2 y 2 + α ≡ 1 · S(y) (mod y 4 )
(3) α3 y 2 + α4 y + α2 ≡ (α3 y + α) · S(y) (mod y 4 )
((3) は (1) − (2) × 多項式 による)
(4) α6 y + α4 ≡ (α4 y 2 + α5 y + α3 ) · S(y) (mod y 4 )
((4) は (2) − (3) × 多項式 による)
( 3 )−1
α
を (4) の両辺にかけると
α3 y + α ≡ (αy 2 + α2 y + 1)S(y) (mod y 4 )
を得る．y = α2 とすると，αy 2 + α2 y + 1 = 0 である．
よって，
αy 2 + α2 y + 1 = (α5 y + 1)(α3 y + 1)
事実 2 より，E(y) = ea y a + eb y b ，a = 5，b = 3，
(a = 3, b = 5 でもよい)
α3 y + α = ea αa (αb y + 1) + eb y b (αa y + 1)
と書ける．よって，
E(y) = α4 y 5 + αy 3
であり，もとの符号は
f = (α, α5 , α6 , α, 0, 0, α5 )
と推測される．
例 2．Fq = F7 = Z/(7) = {0, 1, 2, 3, 4, 5, 6}
50
で考える．3 が 1 つの原始元である．標数が 2 でないので，符号に注意が
必要．
3 32
3
33
34
35
36
2
6 4 5 1
さて，RS(7, 2) の Reed-Solomon 符号を受信したところ，
f1 = (2, 4, 3, 1, 6, 3)
であったとする．シンドローム多項式の係数を計算 (mod 7 の計算) すると
f1 (3) = 2 · 35 + 4 · 34 + 3 · 33 + 32 + 6 · 3 + 3 = 4
f1 (32 ) = 3， f1 (33 ) = 4，f1 (34 ) = 3．
ユークリッドの互除法により，鍵方程式の解を求める．
(1) y 4 ≡ 0 · S(y) (mod y 4 )
(2) 3y 3 + 4y 2 + 3y + 4 ≡ 1 · S(y) (mod y 4 )
(3) 1 ≡ −(5y + 5) · S(y) (mod y 4 )
≡ (2y + 2) · S(y) (mod y 4 )
(3) は (1) − (2) × 多項式 で得られる．
2−1 = 4 (in F7 ) を (3) の両辺にかけると
4 ≡ (y + 1)S(y) (mod y 4 )
係数は F7 なので，1 + y = 1 − 6y = 1 − 33 y ．
よって，誤り位置は，y 3 (3 次) の係数．
4 = e3 · 33 .
33 = 6 = −1 より，e3 = 4 · (−1)−1 = −4 = 3.
よって，元の符号は f1 (y) − 3y 3 で
(2, 4, 0, 1, 6, 3).
と推測される．
再び Reed-Solomon 符号を受信したところ，
f1 = (2, 5, 0, 0, 6, 3)
であった．シンドローム多項式の係数を計算すると
f1 (3) = 2，f1 (32 ) = 5，f1 (33 ) = 0，f1 (34 ) = 2 である．
51
ユークリッドの互除法により，鍵方程式の解を求める．
(1) y 4 ≡ 0 · S(y) (mod y 4 )
(2) 2y 3 + 5y + 2 ≡ 1 · S(y) (mod y 4 )
(3) y 2 + 6y ≡ −4y · S(y) (mod y 4 )
((3) は (1) − (2) × 多項式 による)
(4) 2 ≡ (y 2 + y + 1) · S(y) (mod y 4 )
((4) は (2) − (3) × 多項式 による)
y = 2 とすると，mod 7 で，22 +2+1 = 0. 2−1 = 4 なので，1−4y(= 1+3y)
を因数にもつ．よって，
y 2 + y + 1 = (1 − 4y)(1 − 2y) = (1 − 34 y)(1 − 32 y)
事実 2 より，誤り多項式は E(y) = ea y 4 + eb y 2 で，
2 = e4 · 34 (1 − 32 y) + e2 32 (1 − 34 y)
と書ける．よって，y = 4, y = 2 と代入してみることにより，
E(y) = y 4 + 6y 2 = y 4 − y 2
であり，もとの符号は f1 (y) − E(y) で，
(2, 4, 0, 1, 6, 3)
と推測される．
参考文献
[1] 堀田良之，環と体 1 (岩波講座 現代数学の基礎)，岩波書店，1997 年．
[2] 堀田良之，環と体 2 (岩波講座 現代数学の基礎)，岩波書店，1998 年．
[3] D. Cox, J. Little, D. O’shea, Using Algebraic Geometry, GTM 185,
Springer, New York, 1998. (符号理論などの応用が出ている)
[4] D. Cox, J. Little, D. O’shea, Ideals, Varieties, and Algorithms, Springer,
New York, 1996. (邦訳：コックス/リトル/オシー グレブナ基底と代数多
様体入門 (上・下) シュプリンガー・フェアラーク東京，2000 年)
52