GF(2^2)上での逆元算出方法

代数学を勉強中の者です。
GF(2^2)上での逆元算出方法で、その具体的な計算過程がわからず困っています。

A(x) = a・x + b (a, b∈{0, 1})
があって、A(x)の逆元をB(x) = c・x + d (c, d∈{0, 1})とおくとします。
規約多項式はx ^ 2 + x + 1とします。
ここで、
A(x)・B(x)
=(a・x + b)(c・x + d)
=(a・c) ・x ^ 2 + (a・d + b・c)・x + b・d
=(a・c) ・(x + 1) + (a・d + b・c)・x + b・d <-----x^2=x+1を利用
=(a・c + a・d + b・c)・x + (a・c + b・d) ---(※)
=1
となるから、(※)式の係数の関係から、
a・c + a・d + b・c = 0
a・c + b・d = 1
となる。
この2式をcとdで解くために、一旦まとめると、
(a + b)・c + a・d = 0 ---(①)
a・c + b・d = 1---(②)
となる。次にcについて解くため、①・b + ②・aをとり、cでまとめると、
(b・(a + b)+ a^2)・c = a

ここまでは分かるのですが、
これをcについて解こうとすると、
c = a・(b・(a + b)+ a^2)^(-1)
みたいなこと?になってしまいます。
A(x)=a・x + b の逆元を求めたくて計算しているのに、
(b・(a + b)+ a^2)の逆元を求めるとか、意味がわからなくなってきました。。。

どこかで変なことをしているでしょうか？

また、他にもっと効率のよい計算方法をご存知の方がいれば、お手数ですが上記のような具体的な計算で教えていただきたく思います。

よろしくお願いします。

No.1 ベストアンサー 回答者： Tacosan 回答日時： 2016/12/08 11:58

「A(x) の逆元」は GF(2^2) での逆元であるのに対し, 「(b・(a + b)+ a^2)の逆元」というのは GF(2) における逆元を求めるってことだよね.

そして, A(x) が逆元を持つためには「a と b の少なくとも一方は 1」でないといけないんだけど, この条件を突っ込んだら b・(a + b)+ a^2 は必ず 1 (だからその逆元も 1) になりませんか?

この回答へのお礼

なるほど、全くその通りですね。

そうすると、c = aとなり、①式から、
(a + b)・a + a・d = 0
⇔ a・d = (a + b)・a
で、d = a + b
と求まりますね。
で、
逆元B(x)も
B(x) = c・x + d = a・x + (a + b)
と得られます。
A(x)・B(x)を検算してみても確かに1になるので、間違いないです。

すっきりしました。ありがとうございました！

お礼日時：2016/12/08 13:22

No.4 回答者： Tacosan 回答日時： 2016/12/09 00:43

あぁ, a=1 のときは (a=c=1 を) ①式に代入しちゃえばいいんですよ. それで d が出てきます.

これに対し, a=0 だと①式は (c=a なので) 0=0 という自明な等式になってしまい, ここから d を求めることはできません. その場合 b=1 でなければならないので, ②式に代入すると
d=1
が得られます. あわせると
c=a かつ
・a=0 なら d=1
・a=1 なら d=b+1
となり, 工夫すれば d=a+b と書けます.

この回答へのお礼

なるほどですね。感服しました。
何度も解答して頂きありがとうございます。

おかげさまで、少しGF(2)の計算のコツも掴めた気がします。

お礼日時：2016/12/09 01:16

No.3 回答者： Tacosan 回答日時： 2016/12/08 16:21

ちょっとコメント.

そうすると、c = aとなり、①式から、
(a + b)・a + a・d = 0
⇔ a・d = (a + b)・a
で、d = a + b
と求まりますね。

は危険です. a=0 の場合に「①式から」d が求まらないことに注意.

この回答へのお礼

ご指摘ありがとうございます。
c=aを①に代入して変形した式は、
a・d = (a + b)・a
で、これはa=0だと、d=a+bになるとは限らないから、ということですね。
確かにa=0のときは、
0・d = (a + b)・0 -----(③)
となり、d=0, a+b=1のときでも③式を満たすことになってしまうので、おかしいということですね。

そうすると①ではなく②式にc=aを代入して、
a・a + b・d = 1
⇔ b・d = a (∵GF(2)ではa・a = a)
になると思うのですが、ここからどうやってd=の形に持っていくのでしょう。

初歩的な質問ですみません。

お礼日時：2016/12/08 17:54

No.2 回答者： uyama33 回答日時： 2016/12/08 13:31

簡単な例で考えたら納得しやすいと思います。

たとえば、A(x)＝１・x +１
のときは
A(x)・B(x)
=(１・x + １)(c・x + d)
＝ｃｘ＾２+ｃｘ+ｄｘ+ｄ
＝c(x+1)+cx+dx+d
=2cx+c+dx+d
=dx+(c+d)
=1
より
ｄ＝０、ｃ＝１
よって、(１・x + １)の逆元は(１・x +０)
確認
(１・x + １)(１・x +０)
＝x^2+x
=x+1+x
=2x+1
=1
他のものも具体的に計算してから
もう一度文字式の部分を見直せば納得できると思います。

頑張ってください。

この回答へのお礼

uyama33さん、ご回答ありがとうございます。
大変助かります。

ここまで平易な例で噛み砕いてくださると、大変理解が深まります。
納得納得です。

今後ともよろしくお願いします。

お礼日時：2016/12/08 13:58