Saturday 20 March 2010

映画 スパイアニマル・Gフォース

有限体 一変数多項式 因数分解
 モグラのスペクルズが、暗号解読に取り組んでいる場面で、次のように言っていました。
----
"I have to factor univariate polynomial over a finite field.(有限体上の一変数多項式を因数分解しなければならないんだ。)"
----
 有限体上の一変数多項式因数分解は、暗号理論に使われています。体とは、有理数・実数・複素数などのように、加法・乗法の演算が定義されていて、0以外の元が常に乗法逆元をもつ集合をいいます。その中で、有限個の元をもつものが有限体(ガロア体ともいう)で、簡単な例として剰余類というものがあります。例えばFpとは、素数pで割った余りが等しいものを同じ数とみなしてできる有限体で、p=3のときは{0,1,2}の3個の元から成ります。この場合、普通の計算で4になったら、それは3で割った余りが1なので、1と表します。この関係を4≡1(mod 3)と表します。
[例]
 p(x)=x^3+x+1を、有限体F3上の(有限体F3の元を係数にもつ)一変数多項式として因数分解してみましょう。
 p(1)=3≡0(mod 3)よりp(x)は因数x-1を持ちます(因数定理)。そこでp(x)=x^3+x+1をx-1で普通に割り算すると、商がx^2+x+2で余りが3になりますが、3≡0(mod 3)だから割り切れました。したがって、
   p(x)=(x-1)(x^2+x+2)
となりますが、係数をF3={0,1,2}だけで表せば、-1≡2(mod 3)なので、
   p(x)=(x+2)(x^2+x+2)
と因数分解されました。

3 comments:

  1. 見っけたぞぉお!!!!!!

    ReplyDelete
  2. みつけてしまった(・ω・`)

    ReplyDelete
  3. 意外と簡単に見つけれた(^O^)/

    ReplyDelete