原始多項式がよくわからない

定義は

既約でかつ周期が最大の多項式

これだけだとさっぱりだ。これは符号理論の世界で使われる概念である。
符号の世界はちょっと特殊であることをまず前提としなければいけない。たとえば以下の足し算はだれの目にも明らかである。

 150 + 106 = 256

しかし、符号理論が一般的に活躍するデジタルの世界では上の計算は、場合によっては下記の通りになる

 150 + 106 = 1

要するに桁あふれが起こる。この例では計算結果をchar(1byte)に格納しようとしたために情報の欠落が発生している。とはいえ符号を作るのに足したり掛けたりするのはあまりにも普通のことである。桁あふれしないようにデータの最大値を数ビットにしてしまうというのはあまりにも非効率。ということで考えられたのが有限体である。有限体は次のような性質を持っている

構成要素（元）の数が有限である
元同士の演算（四則）が閉じている（体になっている）

要するに、桁あふれしない、最大数が決まっている、という、デジタル世界にマッチした性質を持っている。では有限体というのは具体的にはどんなものであるか。
たとえば整数を5で割ったあまりの数、は有限体をなす。GF(5)というようにあらわされる。ここでGFはたぶんGalois Field。5に限らず、素数で整数を割ったあまりの数は有限体になる。証明はたぶん下記のとおりでいいのかな

0 < k < p, 0 < i < p, 0 < j < p, i ≠ j, pは素数のとき
和算
(i + k)%p = (j + k)%p
乗算
i・k%p = j・k%p
が成り立つと仮定して矛盾を導く。

じゃぁこれを使って符号を作ろう、と思うのだが、実はまだ足りない。というのも、素数というのはそんなに扱いやすい条件ではない。計算機上でデータを表現する場合、たとえばchar、intなどがあげられる。それらはそれぞれ1byte、4byteであることが一般的。とりあえずcharの場合は、符号なしで0〜255の数を表現できる。ではcharで表現されたデータを適当な符号に変換するにはどの素数を使った有限体を用いればいいか。一番近い素数は257である。GF(257)は0〜256の数を内包する。1違うだけだが、たとえば符号化の過程で計算結果が256になった場合そのストア先がcharであると桁あふれによる情報損失が起こる。そんなわけでこのままでは有限体も使いづらい。

で、ここでようやく原始多項式が絡んでくるのだが、原始多項式によって生成される数列は0〜2^m-1個の元をもった体となる。m=8ととれば、1byteと同じ0〜255の数空間を得ることができる。というわけで世の中の符号、たとえばCRCやReed-Solomonなんかは原始多項式を利用しているわけである。疑似乱数とかもそうだったっけかなぁ。

では原始多項式がそういった性質を持っているのはなぜか？というか原始多項式って何だ。…そこでタイトルへ。

いや、確かに作られた数列は体になってるし、生成過程もわかるんだけれど、なんで？って感じになってしまう。なんとなくわかるんだけど説明ができない…。

ちゃんと本買って調べるかなぁ