整数係数一変数多項式の因数分解

else

F₁ ←F₁∪ {h}

} F ←F1

}

returnF

6.7 整数係数一変数多項式の因数分解

計算機代数システムにおいて用いられている因数分解アルゴリズムは,何らかの準同 型により多項式をより扱いやすい空間に写像し, その空間で, 多項式の像を因数分解 し,なんらかの方法によりその分解された像からもとの空間における因子を構成する, という方法によるものが多い. 特に, 二変数以上の多項式の因数分解は一変数多項式 に帰着されるなど, 一変数多項式の因数分解は, 因数分解アルゴリズムにおいて重要 な位置を占める. ここでは,もっとも普通に用いられている Zassenhausによるアルゴ リズムについて述べる.

無平方なf ∈Z[x]の因数分解アルゴリズムは, 有限体上の因数分解, Hensel構成, 試し割りの三つの部分からなる.

命題 6.31 (Hensel) f ∈Z[x], p∈N は素数で,

f ≡^Yf1i modp, f1i ∈GF(p)[x], deg(f) = deg(^Y

i

f1i)

f1i は GF(p) 上で互いに素とする. この時, 任意の k に対し, fki ∈ Z/(p^k)[x] が存在 して,

f ≡^Y

i

f_ki modp^k, f_1i ≡f_kimodp, deg(f_1i) = deg(f_ki).

[証明]k に関する帰納法で示す. k が 1 の時は正しい. k まで正しいとする.

f_(k+1)i =f_ki+p^kh_i なる形を仮定すると,

Y

i

f_(k+1)i ≡^Y

i

f_ki+p^kX

i

h_i^Y

j6=i

f_kj modp^k+1

一方, f ≡^Q_if_ki modp^k より, f =^Y

i

f_ki+p^khmodp^k+1 と書ける. よって,

h≡^X

i

hi

Y

j6=i

fkj ≡^X

i

hi

Y

j6=i

f1j modp

となるように,h_i ∈GF(p)[x],deg(h_i)≤deg(f_1i)を決めることができることを示せば よい. これは,命題 5.11 により言える. 2

命題 6.32 f ∈Z[x], p∈N は素数,

f ≡g₀h₀ modp, g₀, h₀ ∈GF(p)[x], deg(f) = deg(g₀h₀), GCD(g₀, h₀) = 1 とする. この時, f ≡ gh ≡ g⁰h⁰ modp^k かつ g ≡ g⁰ ≡ g₀ modp, deg(g) = deg(g⁰) = deg(g₀), deg(h) = deg(h⁰) = deg(h₀), lc(g)≡lc(g⁰) modp^k ならば,

g ≡g⁰ modp^k, h≡h⁰ modp^k.

[証明]k に関する帰納法で示す. k まで正しいとする. k+ 1 のとき, 帰納法の仮定に より,

g⁰−g =p^kr, h⁰−h=p^ks

と書ける. 一方, gh ≡ g⁰h⁰ modp^k+1 から rh₀ +sg₀ ≡ 0 mod p が成り立つ. もし s≡0 modp ならばrh0 ≡0 mod pより k+ 1 で正しい. もし s6≡0 ならばg0|r. ここ で, lc(g) ≡ lc(g⁰) modp^k+1 より, deg(rmodp) <deg(g0). よって r ≡ 0 mod p とな り, この場合も k+ 1 で正しい. 2

定義 6.33 f =^Pn_i=0a_ixⁱ ∈C[x]に対し, f のノルム kf k₁, kf k₂ をそれぞれ, kf k1=

Xn

i=0

|ai|, kf k2=

vu utXⁿ

i=0

|ai|²

(|a|は a の絶対値)で定義する.

命題 6.34 (Landau-Mignotte[27]) f =^Pn_i=0a_ixⁱ ∈Z[x], g =^Pm_i=0b_ixⁱ ∈Z[x] とする.

この時g|f ならば, kg k₁≤ |b_m/a_n|2^m kf k₂

系 6.35 f, g ∈Z[x], g|f ならば, klc(f)/lc(g)·g k1≤2^deg(g) kf k2

6.7. 整数係数一変数多項式の因数分解 57 命題 6.36 f ∈Z[x]が無平方ならば,有限個の素数pを除いてdeg(f modp) = deg(f) かつf modp は無平方.

証明は, f の無平方性が,f と f⁰ の終結式が 0でないことと同値であることから明ら か.

以上により Z[x]における因数分解は次のように行なわれる.

アルゴリズム 6.37 (Zassenhaus[49]) Input : f(x)∈Z[x]; f は無平方

Output : {f₁, f₂,· · ·} f =f₁f₂· · · は f の既約分解

p←deg(f) = deg(f modp) かつf modp が無平方となるようなp a←f の主係数

F₁ ←f /amodp の GF(p) 上のモニックな既約因子全体 (有限体上の因数分解) if |F₁|= 1 then return {f}

F₁ ={f₁₁,· · ·, f_1m} とする.

k←p^k >kf k2 ·2^deg(f)+1 なる整数

f ≡^Q_if1i modp からf ≡^Q_ifki modp^k なる Fk ={fk1,· · ·, fkm} を Hensel 構成で求める

l←1 F ← ∅

while ( 2l ≤m ){

(a) S ←S ⊂F_k, |S|=l なる新しい部分集合 if S が存在しない then l←l+ 1

else {

g ←a· · ·^Q_s∈Ss

(b) g ←g の各係数に p^k の整数倍を加えて絶対値が p^k/2 以下としたもの if g|af {

g ←pp(g) (primitive part), f ←f /g, F_k←F_k\S }

}

if (f 6= 1) then F ←F ∪ {f}

returnF

命題 6.38 アルゴリズム 6.37 は f の既約因子分解を出力する.

[証明] (a) において, S が真の因子 G の法p での因子から Hensel 構成により構成さ れた法p^k での因子とする. すると, 法 p^k での一意性により, (b) において

a/lc(G)·G≡g modp^k. ここで, 系 6.35 および k のとり方により,

ka/lc(G)·Gk1≤2^deg(G)kf k2≤2^deg(f) kf k2< p^k/2.

また, kg k₁≤p^k/2 より

kg−a/lc(G)·Gk₁≤kg k₁ +ka/lc(G)·Gk₁<2·p^k/2 =p^k.

以上により, a/lc(G)·G=g. アルゴリズム6.37 では, 法 p での因子の個数が小さい 順に試しているため, 割り切れた時点で既約性が成り立つ. 2

このアルゴリズムでは,

g が f の因子ならば, lc(f)/lc(g)·g は lc(f)f の因子

という簡単な事実が使われている. そして, 予め候補の主係数をlc(f) にしておけば, もし真の因子ならば, 上記の理由により必ずそれは lc(f)f を割り切るのである.

さて, 実際にこのアルゴリズムを計算機上で実現する場合, 効率向上のために注意 する点は数多くある. それらのいくつかを述べる.

1. p の選択

f modpが無平方でさえあれば,アルゴリズムは進行するが,有限体上での因数 分解の出力する modp での因子の個数は p により一般に異なる. 特に, ある p に対し f modpが既約ならば f 自身既約と判定できるが,他のf modpが既約 でない p を選ぶことによって無駄なHensel 構成をする場合もある. このため, 通常はいくつかの p を選んで有限体上での因数分解を複数回起動し, 最も因子 の個数が少ないp を選ぶ.

2. Hensel 構成

ここで述べた Hensel 構成は linear lifting と呼ばれるもので, p の冪が1 次の オーダでしか増えない. 特に pが小さい場合,目的の評価値に到達するのに多く の段数を必要とする. このため, p の冪を2 次のオーダで上げていく quadratic

lifting というアルゴリズムが考案されている. ただしこれは, ^P_iai

Q

k6=ifk = 1

における a_i も同時にHensel 構成しなければならないため, p^k がマシン整数程

度のうちはquadratic liftingし,マシン整数を越えたあたりで linear liftingに切 替えるということが行なわれる.