ガロア体の逆元計算について

前へ 次へ
このQ&Aのポイント
  • ガロア理論における逆元計算方法と、実際の計算例を紹介します。
  • AES暗号の勉強中にガロア体の逆元計算につまづいています。具体的には、逆元の求め方と逆数変換テーブルの関係について疑問があります。
  • 質問者が問題としているページでは16進数の逆元の計算が説明されていますが、質問者の計算結果と異なる結果が得られています。質問者は自身の計算結果に間違いがあるのかどうか、確認したいと思っています。
回答を見る
  • ベストアンサー

ガロア体の逆元計算について

私は今、AES暗号の勉強をしているのですが、ガロア体の所でつまづいています。 ガロア理論での逆元はx∈GF(p)のとき、 GF(p)でx * y が1になる時のyがxの逆元だと思うのですが、 下記のページの上から1/6ぐらいの場所にある逆数変換テーブルを見る限り、 この方法では求められないような気がします。 このページでは16進数の53の逆元を計算しているので、10進数では83になります。 (83 * 219 - 1 )/256= 0なので、53の逆元は219かなと思ったのですが、 以下のページでは16進数のCAで、10進数では202になってしまいます。 私は、どこで間違っているのか、指摘していただけないでしょうか。 http://bw-www.ie.u-ryukyu.ac.jp/~wada/design04/spec_j.html

  • m-kur
  • お礼率87% (7/8)

質問者が選んだベストアンサー

  • ベストアンサー
  • keyguy
  • ベストアンサー率28% (135/469)
回答No.1

ガロア体を勉強しましょう むちゃくちゃなことをしていますぞ GF(2^8)の元を2つかける時に それらの元をそれぞれ十進数にして整数の掛け算をしてはいけません aとbをかけるには aの多項式表現を作り bの多項式表現を作り それら多項式を多項式として掛け算し 参考のページにのっている既約多項式でその結果を割った余りを求め その余り多項式の係数を並べて16進表現をだすのである a逆元をもとめるには aに0を除く255個の元すべてを上の方法でかけてみて1(上の意味で0x01)になるものを選べばいいのです

m-kur
質問者

お礼

回答ありがとうございます。 ガロア体について、全然理解できていなかったようです。 何か本を読んで勉強したいと思うのですが、もしお勧めの本があれば、教えていただけないでしょうか。

その他の回答 (2)

  • keyguy
  • ベストアンサー率28% (135/469)
回答No.3

GF(2)は0と1からなり 0+0=0,0+1=1,1+0=1,1+1=0 0・0=0,0・1=0,1・0=0,1・1=1 で演算が定義されます GF(2^2)はGF(2)の元を係数とする1次以下多項式 0,1,x,x+1からなり a,bをGF(2^2)の元としたとき a+bは自然に定義し a・bはaとbの多項式としての積をx^2+x+1(これは既約)で割った余りで定義する なお 0を「0」と記し 1を「1」と記し xを「2」と記し x+1を[3]と記す GF(2^8)の場合は上のことからどう定義されるか想像つくでしょうね? そのときにx^2+x+1に対応するのはそのサイトの8次既約多項式ですね 位数2^8個のすべての体はその体に同型である 位数が素数の自然数冪乗以外の有限体は存在しない つまり有限体は本質的にガロア体だけなのです 有限体=ガロア体

m-kur
質問者

お礼

返事が遅くなって申し訳ありません。 紙の上でゴリゴリやっていたら、なんとなく理解できました。 丁寧な回答をありがとうございました。

  • keyguy
  • ベストアンサー率28% (135/469)
回答No.2

勉強したいと： 「体」とは何でしょうか？

  1. カテゴリ
  2. 学問・教育
  3. 数学・算数

関連するQ&A

  • ガロア体の逆数

    ガロア体の逆数演算で、 GF(2^8)->GF(4^2) に変換して計算しようとしています。 GF(4^2) 上での計算はうまく行っていますが、 GF(2^8)->GF(4^2)の線形変換がうまくいきません。 つまり、y=A*xの線形変換です。 これだと、x=1,2,3の場合の関係が、 y=A*3=A*(1+2) の関係が成立している場合しか変換できません。 GF(2^8)とGF(4^2)の値を見ていると、この関係は成立してません。 GF(2^8)->GF(4^2)の相互変換テーブルをつくるとうまく行っているので、どこかのパラメータの変更で何とかなると思うのですが、 考え方がわかりません。 もともと、逆数テーブルを無くすのが目的なので、テーブルは使えません。

  • ガロア拡大体に関すること

    http://bw-www.ie.u-ryukyu.ac.jp/~wada/vhdl/GaloisField.html で、αというのが出てきますが、これは何者ですか？ つまり、自然数なのか実数なのか虚数なのかそのどれでもないのか？ このページの中でα^(2^w - 1)＝１とは書いてありますが、 α＝（何々）というのがないので今一イメージがわきません。

  • 有限体における0以外元の位数と積の逆元

    GF(9)={0,1,2,3,4,5,6,7,8},g(x)=x^2+x+2 のときのGF(9)の0以外の元の位数と積における逆元の求め方を教えてください。さっぱりわかりません。。また、GF(7)のようなときはどうするのでしょうか？

  • ガロア拡大体とその部分体について

    ガロア群の構造を考えているのですが煮詰まっています。 Qを有理数として、体の拡大Q(√2,exp(2πi/5))/Qについて考えています。(以後√2=x,exp(2πi/5)=z,L=Q(x,z)と書きます。） この時、xの最小多項式がx^2-1,zの最小多項式がz^4+z^3+z^2+z+1となるから、LはQのガロア拡大となり拡大次数は2*4=8。よって、ガロア群の位数も8。ここでガロア群の生成元を考えたいのですが、一つは、τ(x)=-x,τ(z)=zとなるようなτであると思うのですが、もう一つをどのように考えればよいのかわかりません。 (1)z→z^2,z^2→z^3,z^3→z^4,z^4→z^5,z^5→z のように一個ずつずれるような写像 (2)z→z^2となるような写像 (3)その他 何が正解でなぜなのかを教えていただけないでしょうか。5乗根だけでなく、他の円分体のときのガロア群の生成元についての考え方についても教えていただけると幸いです。

  • 有限体　ガロア体　多項式

    大学の期末試験の過去問なのですがわからないので,ヒント,方針を与えてもらえればうれしいです。 ある大問の中の一つの問題です。前提条件は 「Ｚ3上の多項式p(x)=x^3+2x+1を考える。αをp(x)=0の解とし,元の個数が27個の有限体GF(27)をＺ3上の３次の拡大体Ｚ3(α)として実現する。 このとき,α^2+1を一つの解とするＺ3上の3次方程式を求めよ。」 です。Ｚ3はＺ/Ｚ(3)のことです。「元の個数が27個の有限体GF(27)をＺ3上の３次の拡大体Ｚ3(α)として実現する。」はこの問題で,使わないかもしれませんが, よろしくお願いします。

  • 単位元とか逆元とかの問題がわからなくて困ってます。

    ｐを素数とし、集合ＦをＦ={0,1,2…p-1}と定める。Ｆｎｏ元の和と積をｐに関する譲渡を用いて定める。すなわち、ｚがｘ＋ｙであるとは、ｚ＝ｘ＋ｙmodｐとなることで、ｚがｘｙであるとは、ｚ＝ｘｙmodｐとなることである。 このとき、 和に関する単位元ではないＦの元ｘに対して、積に関する逆元が存在することを示せ。 ヒントとして 『aとｂが互いに素な正の整数なら０≦ｃ＜ｂ、０≦ｄ＜aとなるｃとｄで「ca+db=1」となるものがある』 とあります。。 教えていただけると幸いです。

  • ５次方程式のガロア群について

    ５次方程式のガロア群について 以下は有理数体（Ｑ）で考える。 ３次方程式f(x)のガロア群は ３次の対象群 f(x)が既約で判別式の値が平方数でない場合 ３次の交代群 f(x)が既約で判別式の値が平方数である場合 ２次の対象群 f(x)が１次式×２次式と分解できる場合 単位元のみの群 f(x)が１次式×２次式×１次式と分解できる場合 である。 ４次方程式f(x)のガロア群は ４次の対象群 f(x)の３次分解式のガロア群の位数＝６ ４次の交代群 f(x)の３次分解式のガロア群の位数＝３ ４元数群 f(x)の３次分解式のガロア群の位数＝１ Ｚ４ f(x)の３次分解式のガロア群の位数＝２ である。 f(x)=x^4+qx^2+rx+s としたとき g(x)=x^3 -2px^2 +(q^2-3s)x + r^2 のg(x)をf(x)の３次分解式という。 さて質問です。 既約な５次方程式のガロア群は何でしょうか。 ５次の対象群でしょうか、５次の交代群でしょうか。その他があるでしょうか。 方程式により複数の群があるとした判定基準は何でしょうか。 色々（中島、アルチン、ロットマンの本等）なガロアの理論の本を読んでも書いてません。一般論で書いてある。 ５次の具体的な群は何でしょうか。知っていたら教えて下さい。

  • GF(2^8)->GF((2^4)^2)の変換

    ガロア体の逆数演算で、 GF(2^8)->GF((2^4)^2) に変換して計算しようとしています。 それで、GF(2^8)元aより、GF((2^4)^2)の元bへの変換、 b=A*aがうまく行きません。 GF(2^8)では、生成多項式 X^8=p7*X^7+p6*X^6--- で元を順次つくります。1ビット単位のシフトレジスタを使って、 α^0=1h α^1=2h α^2=4h と言う風になります。 GF((2^4)^2)では、生成多項式 Y^2=q1*Y+q0 で元をつくります。ここで、q1,q2は、GF(2^4)の元です。 したがって、4ビット単位のシフトレジスタを使って、 β^0=1h β^1=10h となります、ここでわからないのは、b=A*aの変換手順です。 a=α^0=1h の場合は、 b=β^0=1h に対応します。 問題は次で、 a=α^1=2hの場合は、 b=β^1=10hに変換するように、Aを設計しています。 つまり、 10h=A*2h の関係を成立させています。 これでは、b=3h、つまり、 A*3h がうまく行きません。 多分、α^1とβ^1を直接変換するのが、間違いだと思いますが、 どうすればいいでしょう？

  • モノイド（左逆元の個数）

    モノイド M の元 x が左逆元 y をもつとき、y は x の逆元であるか、x は左逆元を無数にもつは真ですか。 質問の背景は、モノイドの元 x が有限個の左逆元をもつ場合、個数が１個だけで、その左逆元が x の逆元という例は多数ありますが、別パターンを見つけるのに挫折したことです。 考えても一向に解決しないので、お知恵をお貸しくださいますよう、よろしくお願いします。

  • x^3=2のガロア拡大体の元

    x^3=2の係数体は有理数体Q 、また1の3乗根をωとすると、この方程式のガロア拡大体をEとすれば、E=Q{³√2 ,³√2ω ,³√2(ω^2)} ここで基礎体として有理数体に1のn乗根を必要なだけ添加した体を考え、これをKとするK=Q(ω)。するとE=K{³√2 ,³√2ω ,³√2(ω^2)}となる。 ここからがわからないところです。 K(³√2 )の元は、³√2,ωと有理数を加減乗除したすべての数になり、³√2 について整理すれば、qやpのmやnは右下につく添え字として、 {qm(³√2)^m + qm-1(³√2)^(m-1)+qm-2(³√2)^(m-2)・・・+q0} /{pn(³√2)^n + pn-1(³√2)^(n-1)+pn-2(³√2)^(n-2)・・・+p0}・・・(1) となる。 自分でK(³√2 )の元を具体的に計算してみても、a,b,c,d整数として、 (³√2-ω+b/a)÷(d/c)={³√2c-ωc+bc/a}/dと(1)式と似てもにつきません。 一つ目の疑問として、(1)式ではなぜωがでてこないのか。 次はpやqは有理数なのか、そして最後に(1)式の分母や分子だけでもK(³√2 )の元なのだが、厄介な形の割り算になっているのかということです。 どなたか疑問に答えてください。お願いします。

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する