■有限体の世界(その2)

 今回のコラムでは有限体を係数にもつ多項式の因数分解を扱うことにした.

===================================

【1】Fp係数多項式(方程式)

 有限体Fpを係数にもつ1変数多項式の集合Fp[x]を考えます.たとえば,

  x^2+2x+3

において,mod5の多項式と考えるというのは,係数がmod5で合同な多項式はすべて同じものと見なすということです.

  x^2+2x+3

 =x^2+7x+8

 =6x^2−3x+3

 =−4x^2−12x−23

Fp[x]が環をなすことは簡単に証明できます.

 (その1)に掲げた問題は,F5において,多項式を1次式の積として表せというものなのですが,整数係数のときのように足して3,掛けて2となる2数1,2はF5でも1と2でよく,答えは

  x^2+3x+2=(x+1)(x+2)

となります.

  x^2+4

では足して0,掛けて4となる2数は整数ではあり得ませんが,前述の足し算とかけ算と表を見ると,F5では1と4がこれを満たすので,

  x^2+4=(x+1)(x+4)

同様に足して2,掛けて2はF5では3と4より,

  x^2+2x+2=(x+3)(x+4)

となります.

 この例ではF5だったので,前述の足し算とかけ算と表を見ながらやるとわかりやすいのですが,pが大きくなると簡単ではなくなります.そこで,因数定理「n次方程式f(x)=0がαを根にもつならば,

  g(x)=(x−α)q(x)

という形に分解できる」を用いることにします.

 この定理は(普通の)多項式の因数分解の方法を与えているのですが,Fp係数のn次方程式がFpの中に根をもつ場合でも適用され,確実でしかも速いやり方になっています.

 たとえば,

  f(x)=x^2+4

とおいて,xに順次0から4まで代入して,mod5として計算してゆくと

  f(0)=4,f(1)=5=0,f(2)=8=3,f(3)=13=3,f(4)=20=0

より,f(x)=0の2根は1(=−4)と4=−1.したがって,

  x^2+4=(x−1)(x−4)=(x+4)(x+1)

 同様に,

  g(x)=x^2+2x+2

では

  g(0)=2,g(1)=5=0,g(2)=10=0,g(3)=17=2,g(4)=22=2

より,g(x)=0の2根は1(=−4)と2(=−3)の2個.したがって,

  x^2+2x+2=(x−1)(x−2)=(x+3)(x+4)

 普通にできる因数分解も,有限体F5上で考えると

  h(x)=x^2+3x+2

  h(0)=2,h(1)=6=1,h(2)=12=2,h(3)=20=0,h(4)=30=0

したがって

  x^2+3x+2=(x−3)(x−4)=(x+2)(x+1)

 このように,任意のFp係数多項式Fp[x]は有限個の既約多項式の積に分解されるのですが,整数と同様に,この分解は係数の違いを無視すれば一意に決まります.

===================================