生成元の最小多項式

質問

情報代数学を勉強しています。次のことについて教えていただきたいです。私の書き方がわかりづらいかもしれないので、最初にその単元の教科書に載っている説明を添えておきます。

補足
K=Fqとする。K-{0}が乗法についてつくる群（K×）は位数（q－1）の巡回群である。

問1　F7×の生成元をすべて求めよ。
問2　F2^4×の生成元をすべて求め、それらのF2上の最小多項式を求めよ。

問1に関して
上の補足部分にあるとおりに考えていくと、これは位数が6の巡回群を求めることと同値。6個の元をあげると、｛1,x,x^2,x^3,x^4,x^5}になり、kを自然数としてx^kを生成元とするとkは6と互いに素であればよいから求める答えは(x,x^5)となりました。
答えは出たのですが、なぜこれで生成されるのかがいまいちピンときませんし、ほんとにあっているのかどうか・・・。生成元をべき乗していったらすべての元をまかなえるっていう感じですよね？
(x^5)^2=x^10=x^4
みたいに。でもこれだったら生成元はxだけでいいような気がします。きっと私がどこかで考え間違いしていると思うので、指摘してほしいです。

問2に関して
教授からのヒントで
F2^4×=F2[x]/(x^4+x+1)　
（F2の4次拡大）と書き換え、x^4+x+1の根をωとすると、
F2^4={a0+a1ω+a2ω^2+a3ω^3|a0,a1,a2,a2∈F2}とできる。
というのが与えられました。ここから
F2^4={0,1,ω,ω+1,ω^2+ω+1,ω^3+ω^2+1,ω^3+ω+1}
としたのですが、これが求める生成元になっているのでしょうか？？
こちらに関してはお手上げ状態です。その生成元を求めた後の最小多項式の求め方、あとヒントにある4次拡大についてもよくわからないので教えていただきたいです。よろしくお願いいたします。

回答No.7

guuman

GF(2)上の任意の多項式g(x)においては
(g(x))^2=g(x^2)・・・(*)
が成り立つからじゃ
だからωがg(x)=0の根ならば
任意自然数nについてω^(2^n)もg(x)=0の根になるのじゃ
簡単な(*)の証明を補足に書け

補足

(nCrは二項演算)

Gf(2)上の任意の多項式g(x)を
g(x)=x^n+x^(n-1)+x^(n-2)+…+1
とおく。
(g(x))^2=(x^n+(x^(n-1)+x^(n-2)+…+1))^2
=2C0x^(2n) + 2C1x^(n-1)(x^(n-1)+…+1) + 2C2(x^(n-1)+(x^(n-2)+x^(n-3)+…+1))^2
=x^(2n) + 2C0x^2(n-1)+2C1x^(n-2)(x^(n-2)+…+x^(n-3)+…+1)+2C2(x^(n-2)+(x^(n-3)+x^(n-4)+…+1))^2
=x^(2n)+x^2(n-1)+…この演算を繰り返し行う…+1
=g(x^2)

回答No.6

guuman

次数4の多項式式は2^4個
原始多項式は既約多項式だから
x,(x+1),(x^2+x+1)
で割れるものを省く
すなわち
f(0)=0になるものとf(1)=0になるものとf(x)=(x^2+x+1)^2=x^4+x^2+1を省く
残った原始多項式の候補である既約多項式
f(x)=x^4+x+1
f(x)=x^4+x^3+1
f(x)=x^4+x^3+x^2+x+1
について
mod(x^1,f(x)),mod(x^2,f(x)),mod(x^3,f(x)),mod(x^4,f(x)),mod(x^5,f(x))
を計算する
1が出現しなければf(x)は原始多項式である
ただし、mod(g(x),f(x))はg(x)をf(x)で割った余りである

例：
f(x)=x^4+x+1の検査

x
x^2
x^3
x^4=x+１
x^5=x・x^4=x^2+x //この時点までに1が出ていないのでf(x)は原始
x^6=x・x5=x^3+x^2
x^7=x・x6=x^4+x^3=x^3+x+1
x^8=x・x7=x^2+1
x^9=x・x8=x^3+x
x^10=x・x9=x^2+x+1
x^11=x・x10=x^3+x^2+x
x^12=x・x11=x^3+x^2+x+1
x^13=x・x12=x^3+x^2+1
x^14=x・x13=x^3+1
x^15=x・x14=1

f(x)=x^4+x+1
は原始多項式だったのでこれを生成多項式としてGF(2^4)を作成する
f(x)=0の根をωとすると
ω,
ω^2,
ω^4=ω+1,
ω^7=ω^3+ω+1,
ω^8=ω^2+1,
ω^11=ω^3+ω^2+ω,
ω^13=ω^3+ω^2+1,
ω^14=ω^3+1
が生成元である。

ω,
ω^2,
ω^4=ω+1,
ω^8=ω^2+1
の最小多項式は
(x-ω)・(x-ω^2)・(x-ω^4)・(x-ω^8)=x^4+x+1

ω^7=ω^3+ω+1,
ω^11=ω^3+ω^2+ω,
ω^13=ω^3+ω^2+1,
ω^14=ω^3+1
の最小多項式は
(x-ω^7)・(x-ω^14)・(x-ω^28)・(x-ω^56)=
(x-ω^7)・(x-ω^14)・(x-ω^13)・(x-ω^11)=x^4+x^3+1

補足

さらに質問させてください。
最後の最小多項式を求めるところでωの巾乗が1、2、4、8と7、11、13、14で分けておられますがこれはなぜでしょうか？見てて気づいたのは巾乗部分が等比数列(13→28、11→56)になっていることくらいです。

回答No.5

guuman

＃２も間違いがあったので修正

次数4の多項式式は2^4個
原始多項式は既約多項式だから
x,(x+1),(x^2+x+1)
で割れるものを省く
すなわち
f(0)=0,f(1)=0,f(x)=(x^2+x+1)^2=x^4+x^2+1
を省く
残った原始多項式の候補である既約多項式
f(x)=x^4+x+1
f(x)=x^4+x^3+1
f(x)=x^4+x^3+x^2+x+1
について
mod(1,f(x)),mod(x^1,f(x)),mod(x^2,f(x)),・・,mod(x^5,f(x))
を計算する
すべて異なっていたらfが原始多項式である
ただし、mod(g(x),f(x))はg(x)をf(x)で割った余りである

例：
f(x)=x^4+x+1
1
x
x^2
x^3
x^4=x+１
x^5=x・x^4=x^2+x

よってf(x)=x^4+x+1は原始多項式、ついでに以後求めると

x^6=x・x5=x^3+x^2
x^7=x・x6=x^4+x^3=x^3+x+1
x^8=x・x7=x^2+1
x^9=x・x8=x^3+x
x^10=x・x9=x^2+x+1
x^11=x・x10=x^3+x^2+x
x^12=x・x11=x^3+x^2+x+1
x^13=x・x12=x^3+x^2+1
x^14=x・x13=x^3+1
x^15=x・x14=1

f(x)=x^4+x+1
は原始多項式だったのでこれを生成多項式としてGF(2^4)を作成する
f(x)=0の根をωとすると
ω,ω^2,ω^4,ω^7,ω^8,ω^11,ω^13,ω^14
が生成元である。
例えばω^7のベクトル表現は
h(x)≡mod(x^7,x^4+x+1)
ならばh(ω)である
例えばω^7の最小多項式は
g(x)=x^4+x^3+1

回答No.4

guuman

＃３の最小多項式は間違い

回答No.3

guuman

f(x)=x^4+x+1
は原始多項式だったのでこれを生成多項式としてGF(2^4)を作成する
f(x)=0の根をωとすると
ω,ω^2,ω^4,ω^7,ω^8,ω^11,ω^13,ω^14
が生成元である。
例えばω^7のベクトル表現は
h(x)≡mod(x^7,x^4+x+1)
ならばh(ω)である
例えばω^7の最小多項式は
7・n≡1 mod 15
の解がn=13だから
mod(f(x^13),f(x))

回答No.2

guuman

次数4の多項式式は2^4個
原始多項式は既約多項式だから
x,(x+1),(x^2+x+1)
で割れるものを省く
すなわち
f(0)=0,f(1)=0,f(x)=(x^2+x+1)^2=x^4+x^2+1
を省く
残った原始多項式の候補である既約多項式
f(x)=x^4+x+1
f(x)=x^4+x^3+1
f(x)=x^4+x^3+x^2+x+1
について
mod(1,f(x)),mod(x^1,f(x)),mod(x^2,f(x)),・・,mod(x^8,f(x))
を計算する
すべて異なっていたらfが原始多項式である
ただし、mod(g(x),f(x))はg(x)をf(x)で割った余りである

例：
f(x)=x^4+x+1
1
x
x^2
x^3
x^4=x+１
x^5=x・x^4=x^2+x
x^6=x・x5=x^3+x^2
x^7=x・x6=x^4+x^2=x^2+x+1
x^8=x・x7=x^3+x^2+x
よってf(x)=x^4+x+1は原始多項式

回答No.1

koko_u_

問１は、体のすべての元のかけ算を九九のようにすべて書き出してしまうのがもっとも分かり易いと思いますよ。

問２については、2^4 = 16個の元からなる体が存在することの証明を思い出すとよいでしょう。

お礼

x^35まで書き出してみたところよくわかりました。
ありがとうございます。