バーレカンプ・マッシィ法　具体例準備

前回のnoteで述べたバーレカンプ・マッシィ法の動作例を述べたい。その前に表記を楽にするために新しくガロア体表現を導入する。

次からはまぎれのない時は、$${\alpha^i}$$のベクトル表現を2進数表記の数値とみなして、数値で表現する。すなわち

BBC WHC031 Table1、GF(16)、原始多項式がx^4 + x + 1のケースにおける10進数表現。

表現の説明

べき表現(index form): まず原始元$${\alpha}$$があり、$${\alpha}$$のべきだけで$${GF(16)}$$の元は列挙できる。

多項式表現(polynomial form): 原始多項式から決まる関係$${p(\alpha)  = \alpha^4 + \alpha + 1 = 0}$$により、すべての元は$${\alpha^3, \alpha^2,\alpha,1}$$の一次結合で表現できる。

ベクトル表現(binary form): 多項式表現の係数を並べて表記する。

10進数表現(decimal form): ベクトル表現を数値として解釈して表記する。

表現と式の対応

掛け算をするときはべき表現を使って、指数を足し合わせるようにすること。
NGなのは10進数表現で掛け算をしようとすること。例えば15 x 13は195 = 3(mod16)などではない。正しくは15のべき表現$${\alpha^{12}}$$と13のべき表現$${\alpha^{13}}$$をかけて、$${\alpha^{25} = \alpha^{10}}$$とし、10進数表現に直して7となるから、15 x 13 = 7である。

足し算をするときは多項式表現かベクトル表現を使って、各項や各桁においてxorを計算すること。これも10進数表現で足してはいけない。例えば15+13 = 28 = 12(mod16)などではない。1111 + 1101 = 0010により2である。