有限体 一変数多項式 因数分解
モグラのスペクルズが、暗号解読に取り組んでいる場面で、次のように言っていました。
----
"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)
と因数分解されました。
