誰かが全部まぼろしだと教えてくれたら、わたしはどこへ行くだろう

２００３年度

10月1日 符号の消失を復元する

10月8日　ユークリッド互除法。最大公約数

10月15日　多項式環、ユークリッド互除法と最大公約多項式

10月22日ガロア体の表現（既約多項式の根による巡回群としての表現同じことだが　べき表現）

10月29日　べき表現、多項式表現、ベクトル表現

11月5日　　パリティ検査行列、正しく復号される確率

11月12日　　ハミング符号、RM符号

11月19日　　 巡回符号、多項式による符号化

11月26日　　最小多項式、1文字まで訂正（BCH）

12月3日　　　2文字まで訂正（BCH）

12月10日　　Reed−Solomon符号

12月17日　　代数的復号法

1月14日

符号代数練習帳　ｐｄｆ版

目次：

第１部　ガロアが考えたことガロアが知らなかったこと

第２部 ガロア拡大体の理論（気合入れて書いたよ。だれか読んでね。）

第３部　リードソロモン符号

第１部　ガロアが考えたことガロアが知らなかったこと

公開鍵暗号・共通鍵暗号(under consruction)

：整数　…-4,-3,-2,-1,0,1,2,3,4,…

: をｍで割ったあまりの空間

ものがたり：

ｍが素数なら は都合が良い。そのときは、 は体になる。

有限な体を考察したいから。

コンピュータは有限。

でも、２進数０，１だけでできぬか？

２は素数だ、つまりで考えよう。

しかし、記号のバラエティが少なすぎる。

　は・・・

これは絶望的？

いや演算規則を変えればいいのだ

、 ・・・ で演算規則をうまくやるとできる。

一般に　ｐ：素数でうまくできる理論。

それがというものがロア体

ぼくらはやがてで物事を考えるだろう。

そこへいたる道程は長い。

しかし、若干２０歳のガロアがそこまで見通したのか・・・

じゃ行こう

整数環

足し算表

＋	０	１
０	０	１
１	１	０

掛け算表

・	０	１
０	０	０
１	０	１

べき乗表

・	１	２
０	０	０
１	１	１

　は体である。

　　

足し算表

＋	０	１	２
０	０	１	２
１	１	２	０
２	２	０	１

かけ算表

・	０	１	２
０	０	０	０
１	０	１	２
２	０	２	１

べき乗表

・	２	３	４
０	０	０	０
１	１	１	１
２	１	２	１

　は体である

　

足し算表

＋	０	１	２	３
０	０	１	２	３
１	１	２	３	０
２	２	３	０	１
３	３	０	１	２

かけ算表

・	０	１	２	３
０	０	０	０	０
１	０	１	２	３
２	０	２	０	２
３	０	３	２	１

べき乗表

・	２	３	４	５
０	０	０	０	０
１	１	１	１	１
２	０	０	０	０
３	１	３	１	３

　は環でない：掛け算が群になっていない（掛け算表で１が現れない行がある）

　　　　　０でないもので逆元がないものがある（２は冪零）

　体でない： を体にする方法――＞の拡大体を考える　

　　

足し算表

＋	０	１	２	３	４
０	０	１	２	３	４
１	１	２	３	４	０
２	２	３	４	０	１
３	３	４	０	１	２
４	４	０	１	２	３

かけ算表

・	０	１	２	３	４
０	０	０	０	０	０
１	０	１	２	３	４
２	０	２	４	１	３
３	０	３	１	４	２
４	０	４	３	２	１

べき乗表

	２	３	４	５
０	０	０	０	０
１	１	１	１	１
２	４	３	１	２
３	４	２	１	３
４	１	４	１	４

　は体である。

2,3は原始元である。

＝

　

足し算表

＋	０	１	２	３	４	５
０	０	１	２	３	４	５
１	１	２	３	４	５	０
２	２	３	４	５	０	１
３	３	４	５	０	１	２
４	４	５	０	１	２	３
５	５	０	１	２	３	４

かけ算表

・	０	１	２	３	４	５
０	０	０	０	０	０	０
１	０	１	２	３	４	５
２	０	２	４	０	２	４
３	０	３	０	３	０	３
４	０	４	２	０	４	２
５	０	５	４	３	２	１

２、４に逆元なし

べき乗表

べき	２	３	４	５	６	７
２	４	２	４	２	４	２
３	３	３	３	３	３	３
４	４	４	４	４	４	４
５	１	５	１	５	１	５

３、４は冪等

は体ではない

には原始元がない（巡回群でない）

　

足し算

+	0	1	2	3	4	5	6
0	0	1	2	3	4	5	6
1	1	2	3	4	5	6	0
2	2	3	4	5	6	0	1
3	3	4	5	6	0	1	2
4	4	5	6	0	1	2	3
5	5	6	0	1	2	3	4
6	6	0	1	2	3	4	5

掛け算

・	1	2	3	4	5	6
1	1	2	3	4	5	6
2	2	4	6	1	3	5
3	3	6	2	5	1	4
4	4	1	5	2	6	3
5	5	3	1	6	4	2
6	6	5	4	3	2	1

すべて逆数があることがわかる（掛け算で群になっている）

べき	1	2	3	4	5	6	7
２	２	4	1	2	4	1	2
3	3	2	6	4	5	1	3
4	4	2	1	4	2	1	4
5	5	4	6	2	3	1	5
6	6	1	6	1	6	1	6

3,5が原始元である。

原始元

＝

∖{0}は巡回群である。

ユークリッド互除法

a,bの最大公約数

　となる整数の存在。

を素数とするといつもになり、

すなわち

勝手なゼロでない整数が与えられると、

を満たす、が存在する。

つまり、素数に対して、は有限体（ガロア体）

となる事を意味してる。

要するに、はが素数だと有限体（ガロア体）になるが素数でなければ体にならない。

は　体でないと上で述べた。しかし、掛け算の規則を次のように変更してみる

かけ算表

・	０	１	２	３
０	０	０	０	０
１	０	１	２	３
２	０	２	３	１
３	０	３	２	１

これはと書かれるガロア体とよばれるものになる。

かけ算表

・	０	１
０	０	０	０	０
１	０	１
	０			１
	０			１

において、、、としたもので、多項式の掛け算をして、

でわったあまりを取ったものになっている。一般に素数をとってが多項式環

は、を係数とする多項式を適当な多項式を使って構成することができる。

ここで、多項式は既約、あるいは因数分解できないものを選ぶことによって、体に出来る。

これは、と表現される。

をでわったあまりが等しいものを同一視（同じ類に属する集合を要素とする集合、商空間という）

したものをあらわす。

メモ

多項式環：のように多項式の空間で、和、積について閉じているもの。

ユークリッド互除法：多項式環において２つの多項式の最大公約多項式などを整数の場合とまったく同様に計算できる。

体の拡大：から、をつくったように、からを作ること。

を作る為の既約多項式＝０の根を用いれば、

とあらわされ、ここではにおいてベクトル空間として

一次独立でありの基底になっていることを示すことができる。

を原始元を原始多項式という。

これはと同じ

係数が０か１の２次式は　

、、、

ですべてだがこのうち因数分解できないのは

だけである。

なぜなら、だし、などとなる。

そこで係数が０か１の多項式全体の空間においてで割ったあまりを同一視する

空間を考えると上で寛上げた

と書かれるガロア体とよばれるものになる。

かけ算表

・	０	１
０	０	０	０	０
１	０	１
	０			１
	０			１

であった。このとき、の根は

をみたし、

とかける。が原始元である。掛け算表ではをこの元と同一視しても見かけ上かわらない。

のとき

係数が０か１の３次式は

、、、、

、、、

だけあるが、このうち既約なのは

と

の二つだけである。

をかんがえることにすると次の表を得る。読者はを考えてみよ。

	１
１	１
					１
						１
							１
		１
			１
				１

これをみると当然だが、対角線で対称になっていること、各行には必ず１がある（これは逆元の存在を保証する）。このようにできたのは　が既約であるからである。

ハミング符号

巡回符号

BCH符号

リードソロモン符号

暗号理論

楕円暗号

参考文献

平澤茂一・西島利尚　符号理論入門　培風館　

岩永恭雄　代数学の基礎　日本評論社

硲　文夫　初等代数学　森北出版

硲　文夫　代数学　　　森北出版

硲　文夫　代数幾何学　森北出版

第２部 ガロア拡大体の理論

拡大体

四則演算（＋、−、×、/ ）が定義されている代数を体という。

登場人物：、、、、

整数。これは割り算すると整数でないものがあるから体ではない。

例：だがはできない。

。整数でで割ったあまりは同一のものと考える。

が素数のときは体になる。ここで、整数論や素数理論が必要である。

（素数入門　芹沢 講談社　Blue Backs　参照。　暗号も書いてあり面白い）

と書いて、ガロア体と呼ぶ。

これは

0+0=0,0+1=1+0=1,1+1=0という足し算と

0×0=0,0×1=1×0=0,1×1=1なる掛け算があり、

1/1=1 なる割り算がある。

よって体である。

有限要素からなる体をガロア体と呼ぶ。

や、やがあり、

は、個の要素からなっている体で、を満足する。

体が３つありと記号をきめるとなる関係があるとき

はの拡大体、はの拡大体、はの拡大体などという。

はの部分体、はの部分体、はの部分体などという。

はとの中間体、この３つの関係で一番小さいは基礎体という。

この言い方すると

のようになり、どれが拡大体、部分体、中間体と呼んでいいかは明白であろう。

ハミング符号は0と1　だけから成る符号で基礎体だけの演算の範囲での線形代数を考える。しかし、ハミング符号では１文字の誤りは訂正できるが、２文字以上の誤りがあるものは訂正できない。そこで、拡大体やを考えるとＢＣＨ符号、リードソロモン符号といった、という記号を追加しながら、２文字以上の誤り訂正可能な符号を考えることが出来る。基本的には、２文字の誤り訂正には２次方程式が

３文字には３次方程式が、４文字には４次方程式がでてきて、これら方程式の根（＝０となる解）を計算することにより、誤り位置を検出しこれを訂正できることになる。

話を拡大体の説明に戻す。

整数の割り算全体を考えるとこれらの要素は、四則演算してもまた整数の割り算として表されている。これを有理数といってとあらわす。（有理数はrationalの日本語訳でrational　には「合理的な」という意味と、「比率ratio」という意味が含まれていて明治時代の日本人が後者とするべきところを前者と間違えて翻訳し、間違えられたまま使われ続けているばかばかしい例ではないかとぼくは考えた）。

は体である。

は実数全体。は体である。

は複素数全体。は体である。

はの拡大体、はの拡大体。はとの中間体。

はの拡大体。

拡大体にはいつもを係数に持つ方程式を考えることから定義される。この場合

という方程式を考えると、この方程式にはには解がない。そこでこの方程式を満たす数

を導入してというもの全体を考える。

足し算、引き算は

掛け算は

でここで、がの根であることからをもちいて、

となり、通常はという記号をもちいて、複素数　と書く。

この全体を複素数全体になり、はの拡大体であるという。

との中間体も考えることが出来る。

方程式はのなかに解を持たない。（多分はしってるだろうけどこれは

整数の比、分数ではかけない。証明は高校で習った？）

の解をと書いて、全体を考え、

足し算、引き算は

掛け算は

でここで、がの根であることからをもちいて、

となる。この全体は、との中間拡大体になる。

―――――

ガウスはなどというものを考え、これを整数とよび、普通の整数を有理整数といったんだ（わけわかんないけどね）

さて本題に戻ろう：

体を体の拡大とする。

体を体の有限拡大とする。つまり、は上のベクトル空間である。

どんなが与えられても、の基底をもちいて（次元としておこう）、これに対してを見つけることが出来、

とあらわせることである。（拡大体においての足し算と掛け算を定義の仕方からこうなるのだけど一次独立とか、線形空間とかの概念はいる。線形代数のことを思い出しておこう）

例：はの有限拡大である。基底を、とする。２次元ベクトル空間と考えられる。実際、複素数は２次元平面上の点として表される。

定義：をの拡大体であるとする。はある多項式（を係数とする多項式）の根　となっているとき、は上代数的という。

定義：をの拡大体であるとする。の要素がすべて上代数的のとき、

をの代数拡大という。多項式の根だけをつかって拡大できる場合代数拡大というのである。

自明だが：

定理：はの代数的拡大である。

証明：はの根である。

定理：がの有限拡大ならはの代数的拡大である。

証明：なる任意要素は、ある多項式の根となることを示す。は上有限次元=次元であるから、

は一次従属である。よって、あるすべてはゼロでないが存在して

。

これは、が　の根となることを意味している。

証明おわり。

因数分解：

のように多項式を、いくつかの多項式の掛け算として表すことを因数分解という。は因数分解できるだろうか？

実数の範囲で考えるとこれは出来ないが複素数の範囲で考えると

と因数分解できる。拡大というのは上で根を持たない多項式をゼロにする要素を導入して拡大（代数拡大）するので、上因数分解できても上で因数分解できないことが起きる。因数分解というのは根を用いという因子でくくりだすということでもあるから。うえでは、はの代数拡大であることを説明している。

因数分解できない多項式を既約多項式（これ以上、約せないもの）という。

ただし、この場合「上」で因数分解できないというように、考えている体をいちいち

明記する必要がある。また、最高次数の係数が１の多項式をモニック多項式という。

つまり、

となってる多項式である。

定理　が上代数的ならば、でとなる、既約なモニック多項式がひとつだけ存在する。

証明：となる。が既約なら、最高次数の係数で割ったものを

とすればよい。と因数分解されたらと出来るはずで

次数が一番小さいものはひとつしかないことがユークリッド互除法を使えば証明できる。

この多項式をの最小多項式と呼ぶ。

定義：が上代数的で、をの最小多項式とする。最小多項式は、モニックの係数が１であることに注意しておく。

次のような集合を考える。

の要素　と

の足し算は

＝

と定義されるし、掛け算についてはがの根であることから、

を変数とみなして普通に計算して、次より大きなのべきは

を用いて、掛け算の結果を、だけの一次結合で表される。

の要素どうしの掛け算したものはまたの要素となる。これが割り算をゆるすことすなわち、逆元が存在することはが既約であることがその理由である。

このようにしてはの拡大体で、の部分体である。

このような方法で、を拡大することを単純拡大という。

定理　は体である。

証明　をゼロでない元として、この元の逆元を求めてやろう。

その存在が示せれば、が体であることがいえる。

次以下の多項式をとると、である。さもなければ、最小多項式の次数がであることとつじつまがあわなくなる。

多項式環におけるユークリッドの互除法により、とが互いに素だと、２つ多項式、をみつけて、

とできる。（一般に右辺は、との最大公約関数だがは既約である）

この式にを代入すれば、となり、となるように

を変形しておけば、がの逆元であり、証明できたことになる。

おわり。

定理　はの拡大でとを含む拡大体のなかでは最小のものである。

巡回符号の理論

符号全体の集まりをと書く。

の要素つまり０か１を元とするベクトルが巡回符号とは

と定義する。これは多項式の空間で考えると、つまり多項式全体を

でわったあまりは同一視する。今の場合、は１とおきかえる、

-------

たとえば、とすると

はとなり

はとなる。1+1=0を使った。

---------

を考えるとき、

と表せる。言い直せば符号多項式の全体はのなかのイデアルとなっている。

符号を次のように構成する。という送りたい情報ベクトルがあるとき

の因子で次の多項式をとり、として符号を作る。

は生成多項式と呼ばれる。を満たす次以下の多項式を考え

パリティ検査行列という。すると、

　

となる。

以下教科書

符号理論　平澤、西島　培風館

４章以下を参照されたい。

第３部　リードソロモン符号

で考える。送信符号。

注意：ももその要素は拡大体であることに注意する。

問題　　をたしかめよ。

をみたすはリードソロモン符号と呼ばれる。

（１）誤りが１個の場合：

桁目がに化けたとする。

これから、２番目を１番目で割りを求める。次に、１番目をで割りを求める。

（２）誤りが２個の場合：

、とおき、上の４つの要素をとする。

、、、

つぎに、自明な式を２つ考える。

、

はじめの式にをかけ２番目にをかけて加えると

はじめの式にをかけ２番目にをかけて加えると

この連立方程式から、とが得られ、

の2次方程式を解くことによりが得られる。

の連立一次方程式より、とが得られる。たとえば、

のときを考えると、

これから、、、、となり

これから、。

なるは。よって、。

つぎに、、より

はじめの式にをかけてこれら２つを加えると

。つまり、。よって、。

また、より。

が答え。