■因数分解の算法(その3)
x^2+3x+2=(x+1)(x+2)
は整数係数のおなじみの因数分解の問題であるが,足して3,掛けて2となる2数を見つければよい.1と2がこれを満たすわけであるから,答えは右辺のようになる.
それでは,以下の例はどうであろうか?
x^2+4=(x+1)(x+4)
x^2+2x+2=(x+3)(x+4)
一見分解できなさそうに見える左辺が,右辺のように1次式の積として表されているのだから明らかな誤りと映るに違いない.ところがこれが正しいのである.
そんな馬鹿なと思われるかもしれないが,実はこの因数分解のトリックは「有限体」にある.整数や有理数,実数や複素数の元は無限個あり,演算規則が定義されている.整数は環をなし,有理数,実数,複素数,4元数,p進数は体をなす.このことから,体の定義を思い出してほしいのだが,0以外の元が常に乗法に関する逆元をもつ数体系を「体」という.
そして,有限個の元と体の構造をもつ数体系が「有限体」である.有限体は,計算機や通信などでいまや花形の数学の理論となっている.そんなわけで,今回のコラムでは有限体を係数にもつ多項式の因数分解を扱うことにした.
なお,代数学の教えるところによれば,n元の体(加減乗除の演算が定義された集合)が存在するための必要十分条件は,nが素数(のベキ乗)になっていることで,位数2,3,4=2^2,5の体は存在するが,位数6=2×3の体は存在しない.そして,位数7,8=2^3,9=3^2の体は存在して,位数10=2×5のものは存在しない.今回のコラムは,このことを示すのに絶好のテーマになっていると思う.
===================================
【1】有限環と有限体
整数には奇数と偶数がありますが,
ODD=1,EVEN=0
として,加法と乗法を定義すると
+ 0 1 × 0 1
0 0 1 0 0 0
1 1 0 1 0 1
となります.
偶数か奇数かは2で割ったときの余りで識別できますが,同様に3で割ったときの余りで分類した数体系を考えます.余りは0,1,2のどれかですから,
+ 0 1 2 × 0 1 2
0 0 1 2 0 0 0 0
1 1 2 0 1 0 1 2
2 2 0 1 2 0 2 1
のような演算を定義することができるわけです.
もう少し続けてみることにしましょう.n=4のとき
+ 0 1 2 3 × 0 1 2 3
0 0 1 2 3 0 0 0 0 0
1 1 2 3 0 1 0 1 2 3
2 2 3 0 1 2 0 2 0 2
3 3 0 1 2 3 0 3 2 1
n=5のとき
+ 0 1 2 3 4
0 0 1 2 3 4
1 1 2 3 4 0
2 2 3 4 0 1
3 3 4 0 1 2
4 4 0 1 2 3
× 0 1 2 3 4
0 0 0 0 0 0
1 0 1 2 3 4
2 0 2 4 1 3
3 0 3 1 4 2
4 0 4 3 2 1
その算法(和と積)はそれぞれ和,積のmod5での余りとなります.足し算では巡回するだけで面白味がないので,これ以降はかけ算だけを続けてみます.
n=6のとき
× 0 1 2 3 4 5
0 0 0 0 0 0 0
1 0 1 2 3 4 5
2 0 2 4 0 2 4
3 0 3 0 3 0 3
4 0 4 2 0 4 2
n=7のとき
× 0 1 2 3 4 5 6
0 0 0 0 0 0 0 0
1 0 1 2 3 4 5 6
2 0 2 4 6 1 3 5
3 0 3 6 2 5 1 4
4 0 4 1 5 2 6 3
5 0 5 3 1 6 4 2
6 0 6 5 4 3 2 1
いずれのかけ算の表でも,
1)0の行・列はすべて0
2)主対角線に関して対称
です.また,0以外の行・列では,n=2,3,5,7の場合,0〜n−1が一度ずつ現れましたが,n=4,6ではそうはならず,非常に大きな違いがあることに気づきます.
a・a^(-1)=1となるa^(-1)をaの逆元といいます.n=7の表で説明すると,1の逆元は1,2の逆元は4,3の逆元は5,4の逆元は2,5の逆元は3,6の逆元は6となるというわけです.
0以外の元が常に乗法に関する逆元をもつ数体系を「体」といいますが,以上の結果において,2,3,5,7は素数,4,6は合成数ですから,集合
{0,1,2,・・・,n−1}
はnが素数のとき体となる,合成数のとき環であって体ではないことを示しているのです.
重要なのは,
「pが素数のとき,Z/pZは体である.」
ということで,素数pで割ったときの余りで分類した数体系を考えると,p個の元からなる有限体ができあがります.そして,素数pに対して定まる有限体をFpと書きます.
F7={0,1,2,3,4,5,6}
はあるが,F6というものは存在しないというわけです.
なお,有限体は乗法の交換法則を満たすので可換体となります.有限体が必ず可換体になることを証明したのはウェダーバーンです(1905年).
===================================
有限体Fpの0以外の元をaとします.このとき,aをp回足すとはじめて0になります.素数7を例にとって,F7でa=3を何回もたしてみると
3+3=6
3+3+3=6+3=2
3+3+3+3=2+3=5
3+3+3+3+3=5+3=1
3+3+3+3+3+3=1+3=4
3+3+3+3+3+3+3=4+3=0
このpを有限体Fpの標数といいます.
また,aをp−1回掛けると1になります.F7において
a\^n 1 2 3 4 5 6
1 1 1 1 1 1 1
2 2 4 1 2 4 1
3 3 2 6 4 5 1
4 4 2 1 4 2 1
5 5 4 6 2 3 1
6 6 1 6 1 6 1
最後の列はすべて1です.
このように,pで割り切れない整数aに対して,フェルマーの定理
a^(p-1)=1 (mod p)
が成り立つというわけです.また,このことからa^(p-2)がaの逆元となることも理解されます.
1/a=a^(p-2)
F7では,
1/3=3^5=5,1/6=6^5=6
なお,この表において,1は1乗してはじめて1になりますが,2は3乗して,3は6乗して,4は3乗して,5は6乗して,6は2乗してはじめて1になります.pと互いに素な整数aがp−1乗してはじめて1になるとき,aを原始根といいます.F7においては3,5が原始根です.
Fpにおける原始根aが与えられたとき,0以外のすべての元は,
a^i (i=0〜p-2)
の形に表すことができます.
===================================
【2】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]が環をなすことは簡単に証明できます.
冒頭に掲げた問題は,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]は有限個の既約多項式の積に分解されるのですが,整数と同様に,この分解は係数の違いを無視すれば一意に決まります.
===================================
【3】拡大体Fp^2
前節では,f(x)=0が根をもつ場合を考えましたが,逆に,根が一つもなかったらどうなるのでしょうか?
答えを先にいうと,環Fp[x]をmodf(x)で考えた剰余環を
Fp[x]/f(x)
と記すのですが,f(x)が既約ならば
Fp[x]/f(x)
は体となります.
すなわち「剰余体になる」が答えですが,証明には興味がないので,ここでは根が一つもないような方程式を利用して,有限体Fpを拡大したFp^2を具体的に構成することにします.証明法を述べるのはやめて,考え方に焦点をあててみたいというわけです.
たとえば,F3における2次方程式
x^2+1=0
を考えます.
f(0)=1,f(1)=2,f(2)=5=2
ですから,これはF3の中には根をもちません(=既約多項式).
F3[x]/(x^2+1)
では,剰余の次数は高々1次ですから,
F3[x]/(x^2+1)={ax+b|a,bはF3の元}
また,F3=Z/3Zの元の集合は{0,1,2}ですから,
{0,1,2,x,x+1,x+2,2x,2x+1,2x+2}
の9個の剰余類からなります.
F3では−1=2すなわち{0,1,2}={0,1,−1}ですから,
{0,1,−1,x,x+1,x−1,−x,−x+1,−x−1}
としても同じことです.ともあれ,f(x)の次数をdとすると,Fp[x]/f(x)の位数はp^d個あることがわかります.
===================================
次に,この9個の元が体をなすだろうか? すなわち,加減乗除が可能だろうか? という問題が派生します.
F3[x]/(x^2+1)={ax+b|a,bはF3の元}
において,ax+bをabとして3進数表示すれば,集合としては
{00,01,02,10,11,12,20,21,22}={0,1,2,3,4,5,6,7,8}
桁ごとのF3の加法,たとえば,
3+5=x+(x+2)=2x+2=22=8
をまとめると
+ 0 1 2 3 4 5 6 7 8
0 0 1 2 3 4 5 6 7 8
1 1 2 3 4 5 6 7 8 0
2 2 3 4 5 6 7 8 1 2
3 3 4 5 6 7 8 1 0 2
4 4 5 6 7 8 0 1 2 3
5 5 6 7 8 0 1 2 3 4
6 6 7 8 0 1 2 3 4 5
7 7 8 0 1 2 3 4 5 6
8 8 0 1 2 3 4 5 6 7
また,乗法は多項式としての積のx^2+1による剰余,すなわち,右辺の乗算はx^2+1が出てくるたびに0に置き換える(=x^2が出てくるだびに−1に置き換える)ことによって,たとえば,
3×5=x(x+2)=x^2+2x=2x−1=2x+2=22=8
が実現されます.
× 0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
1 0 1 2 3 4 5 6 7 8
2 0 2 1 6 8 7 3 5 4
3 0 3 6 2 5 8 1 4 7
4 0 4 8 5 6 1 7 2 3
5 0 5 7 8 1 3 4 6 2
6 0 6 3 1 7 4 2 8 5
7 0 7 5 4 2 6 8 4 1
8 0 8 5 7 3 2 5 1 6
このように0〜8が一度ずつ現れましたし,0以外の元が
1×1=1
2×2=1
(x+1)×(x+2)=1
(x+2)×(x+1)=1
2x×x=1
(2x+1)×(2x+2)=1
(2x+2)×(2x+1)=1
のように常に乗法に関する逆元をもっているわけですから,
F3[x]/(x^2+1)
が「体」となっていることがわかります.
この拡大体をF9と書きます.添字の9は9個の元からなることを表しています.前述したように
Z/9Z={0,1,2,3,4,5,6,7,8}
(一般にZ/p^2Z)では,有限環とはなっても有限体にはならないわけですから,紛らわしいので,F3^2あるいは一般にFp^2と書いた方がいいかもしれません.
なお,Fp^nの0でない元の全体は,位数p^n−1の乗法群をなします.この群のすべての元は
f(x)=x^(p^n-1)−1=0,すなわち,x^(p^n)=x
を満たします.また,
(x+y)^p=x^p+y^p (和のp乗はp乗の和)
(xy)^p=x^py^p (積のp乗はp乗の積)
ですから,p乗の算法は体をなしています.一般に,
{f(x)}^p=f(x^p)
が成立します.
===================================
有限体を係数にもつ方程式を考えて,その根をつけ加えて得られる数体系も有限体と呼ばれます.
体F3にx^2+1の形式的な解を考えて,それをαとします.
F3(α)=F3[x]/(x^2+1)
と定義すると,
F3(α)={a+bα|a,b=F3}
={0,1,−1,α,α+1,α−1,−α,−α+1,−α−1}
です.
x^2+1=0のもう一つの解−αがこの体に入っていることから,x^2+1はこの体で1次式の積に分解されることがわかります.
x^2+1=(x−α)(x+α)
また,F3には{0,1,2}={0,1,−1}を代入しても0にならない2次式(2次の既約多項式)がさらに2つあります.
x^2+x+2=x^2+x−1,
x^2+2x+2=x^2−x−1
x^2+x−1=0の解は1+α,1−α,x^2−x−1=0の解は−1+α,−1−αであって,F3にx^2+1=0の解を添加した体F3(α)はすべての既約2次方程式の解を含むことになります.もちろん有理数体においてはこのようなことは起こりません.
何が問題なのかを意識していないと肝心なところがわからないので,説明を繰り返しますが,結局,「Fp係数の既約方程式f(x)=0は
Fp[x]/f(x)
において根をもつ.」すなわち,Fpを係数とする方程式を考え,その根をどんどん新しい数としてつけ加えていくと,ついにはどんな方程式からもそれ以上新しい根がでないような数の体系にたどりつくというわけです.
換言すると,有限体Fpを含んでいて,しかもあらゆるFp係数既約2次方程式が解けるというきわめて有用な有限Fpの2次拡大体Fp^2を構成したことになります.
なお,ここで用いた既約多項式は
f(x)=x^2+1
ですから,この話はiを添加して実数体(R:a)を複素数体(C:a+bi)に拡大した話と完全に並行していることが窺えます.
===================================
【4】拡大体F2^n
ここでは,F2係数既約n次方程式がその中に根をもつような有限体F2^nを構成します.この体は,近年,符号理論・暗号理論などの分野でますます重要な枠割りを果たしています.
まず,素体F2の2次拡大:F4=F2^2をつくることにしますが,
f(x)=x^2+1
は
f(0)=1,f(1)=2=0
より,
x^2+1=(x+1)^2
のように因数分解されます.したがって,既約多項式ではありません.
F2係数2次方程式のうち,F2の中に根をもたないものは,
x^2+x+1
だけなのです.そこで,
F2[x]/(x^2+x+1)={ax+b|a,bはF2の元}
では,剰余の次数は高々1次で,F2=Z/2Zの元の集合は{0,1}ですから,
{0,1,x,x+1}
の4個の剰余類からなります.
ax+bをabとして2進数表示すれば,集合としては
F4=F2^2={00,01,10,11}={0,1,2,3}
加算はビットごとのF2の加法なので省略して,かけ算だけを示しますが,
x^2=−x−1=x+1 (F2では−1=1)
に置き換えると
× 0 1 2 3
0 0 0 0 0
1 0 1 2 3
2 0 2 3 1
3 0 3 1 2
また,素体F2の3次拡大
F8=F2^3={ax^2+bx+c|a,b,cはF3の元}
の原始方程式は
x3+x+1=0
より,
x^3=−x−1=x+1
に置き換えると,例えば,
3×5=011・101=(x+1)(x^2+1)=x^3+x^2+x+1
=x+1+x^2+x+1=x^2=100=4
× 0 1 2 3 4 5 6 7
0 0 0 0 0 0 0 0 0
1 0 1 2 3 4 5 6 7
2 0 2 4 6 3 1 7 4
3 0 3 6 5 7 4 1 2
4 0 4 3 7 6 2 5 1
5 0 5 1 4 2 7 3 6
6 0 6 7 1 5 3 2 4
7 0 7 5 2 1 6 4 3
以上より,F4もF8も体であることが確認されました.
===================================
一般のnに対するF2^nの計算も,原始方程式を見つけることができれば,まったく同様にできます.したがって,問題は原始方程式を見つけることです.任意のn次既約多項式はx^(p^n)−xの約数なのですが,1次因子〜高次因子をすべて求める方法にはこれ以上深入りせず,nが比較的小さいときの原始方程式をいくつか掲げておきます.
最高次数の係数が1の多項式をモニックな多項式というのですが,多項式の場合,モニックで既約な多項式が,整数における素数に対応します.ここでは,F2[x]において,モニックな既約多項式のみを考えます.
1)1次のモニックな既約多項式は,
x,x+1
の2個.
2)2次のモニックな既約多項式は,
x^2+x+1
ただひとつです.
定数項が0のものはxで割り切れますから,候補はx^2+1とx^2+x+1の2つしかないのですが,x^2+1=(x+1)^2なので不可.x^2+x+1は0,1を代入しても0にならないので,1次因子をもたない.従って既約多項式です.
3)3次のモニックな既約多項式は
x^3+x+1,x^3+x^2+1
の2個.
x^3+ax^2+bx+cに0,1を代入すると,c,1+a+b+cで,これがどちらも0にならないのはa+b+1=0,c=1のとき.つまり,
a=1,b=0,c=1またはa=0,b=1,c=1.
4)4次のモニックな既約多項式は
x^4+x+1,x^4+x^3+1,x^4+x^3+x^2+x+1
の3個.
x^4+ax^3+bx^2+cx+dに0,1を代入すると,d,1+a+b+c+dで,これがどちらも0にならないのはa+b+c+1=0,d=1のとき.これは1次因子をもたない条件.
2次の既約多項式はx^2+x+1だけ.これで割ってみると余りは,(b+c+1)x+a+b+d.これが0でないのは,b+c=0またはa+b+d=1.合わせればa=1,b=cまたはa=b,c=1.よって,
a=1,b=c=0とa=b=c=1とa=b=0,c=1
5)5次の既約多項式は
x^5+x^2+1
など5個.
x^5+x+1=(x^3+x^2+1)(x^2+x+1)
はF2[x]上で既約ではない.
6)6次の既約多項式は
x^6+x+1
など9個.
7)7次の既約多項式は
x^7+x+1
など18個.
8)8次の既約多項式は
x^8+x^4+x^3+x^2+1
など30個.
===================================
【5】p進数
有限体の話とよく似た例にp進数があります.p進数は,有理数から実数とは違う方向に枝分かれした数といってもよい数体系なのですが,たとえば,7進数の世界では
1+7+7^2+7^3+・・・=−1/6
2進数では
1+2+2^2+2^3+・・・=−1
が正しいのです.正数の総和が負になって、一見して目がくらんでしまいますが,別に冗談をいっているのではありません.
また,有限体の場合と同様,p進数を係数とする方程式を考え,その根をどんどん新しい数としてつけ加えていくと,ついにはどんな方程式からもそれ以上新しい根がでないような数の体系にいきつきます.
有限体とかp進数とか,どちらもpが素数のとき体をなすのですが,われわれの知らない数はまだまだあるのです.
===================================
[補]ブール代数
コンピュータはたくさんのスイッチ(ON/OFF素子)からできているわけですが,
ON=1,OFF=0
という2つの元からなる数体系を対応させることができます.
そして,演算規則
+ 0 1 × 0 1
0 0 1 0 0 0
1 1 1 1 0 1
がそれぞれOR回路,AND回路に相当します.
このような演算体系は「ブール代数」と呼ばれます.F2のときの2を法とした通常の剰余とは,演算規則が1+1=1のところで異なっています.
===================================