GF(2^8)からGF((2^4)^2)への変換とは？

質問

• GF(2^8)からGF((2^4)^2)への変換について質問しています。
• GF(2^8)とGF((2^4)^2)の生成多項式と元のつくり方について説明しています。
• GF(2^8)からGF((2^4)^2)への変換手順について悩んでいる状況を述べています。

回答No.7

reiman

前回の編集ミスを修正

わかりやすくするために
GF(2^4)→GF((2^2)^2)
の場合にやってみます。

GF(2^4)の生成多項式として
x^4+x+1
を使い
GF(2^2)の生成多項式として
x^2+x+1
を使い
GF((2^2)^2)の生成多項式として
x^2+ax+b
(a,b∈GF(2^2))
を使うとし
GF(2^2)の生成元をαとし
GF(2^4)の生成元をβとする。
すると以下が成立する。
β^4+β+1=0…(1)
α^2+α+1=0…(2)
β^2+aβ+b=0…(3)
fを3次以下多項式として
α=f(β):=α[3]β^3＋α[2]β^2+α[1]β+α[0]
とし
(2)に代入して
f(β)^2+f(β)+1=0
これを(1)を使って3次以下のβの多項式にして
βのべき乗の係数を0としてfすなわちαをβの式として求める。
(未知数も式も4個なので求まる。)
×＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
α[3]β^6＋α[2]β^4+α[1]β^2+α[0]+α[3]β^3＋α[2]β^2+α[1]β+α[0]+1=0
よって
(α[3]+α[1]+α[2])β^2+(α[2]+α[1])β+(α[2]+1)=0
よって
α[2]=1
α[2]=α[1]
α[3]+α[1]+α[2]=0
よって
α[0]=0
α[1]=1
α[2]=1
α[3]=0
とできる。
よって
α=β^2+β
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
同様に
g,hをそれぞれ2次以下の多項式として
a=g(f(β)):=a[1]α+a[0]=a[1](β^2+β)+a[0]
b=h(f(β)):=b[1]α+b[0]=b[1](β^2+β)+b[0]
として(3)に代入して
β^2+g(f(β))β+h(f(β))=0
これを(1)を使って3次以下のβの多項式にして
βのべき乗の係数を0としてgとhすなわちa,bをβの式として求める。
(未知数も式も4個なので求まる。)
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
β^2+(a[1](β^2+β)+a[0])β+b[1](β^2+β)+b[0]=0
よって
(a[1])β^3+(1+a[1]+b[1])β^2+(a[0]+b[1])β+(b[0])=0
a[1]=0
1+a[1]+b[1]=0
a[0]+b[1]=0
b[0]=0
よって
a[0]=1
a[1]=0
b[0]=0
b[1]=1
よって
a=1
b=α
よって
β^2+β+α=0
これは先に求めた式と同じ
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
そして
α^0=1
α^1=β^2+β
βα^0=β
βα^1=β(β^2+β)=β^3+β^2
R=[β^0　β^1　β^2　β^3]^T
B=[α^0　α^1　βα^0　βα^1]^T
とおくと上記の関係式により求まるGF(2)上の4次正方行列Gによって
B=GR
とできる。
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
G=
［１　０　０　０］
［０　１　１　０］
［０　１　０　０］
［０　０　１　１］
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
一方
GF(2)上の4次元行ベクトルx,yにより
xR=yB
ならば
xR=yGR
すなわち
x=yG
すなわち
y^T=(G^T)^-1x^T
結局
A=(G^T)^-1
とすればよい。
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
A=
［１　０　０　０］
［０　０　１　１］
［０　１　１　１］
［０　０　０　１］
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊