Modular アルゴリズム

前節で述べた互除法による GCD の計算は, GCD の次数が比較的高い場合には良好 に動作するが, GCD の次数が低い場合,特に GCD が 1の場合などでは, 部分終結式 法によっても係数の増大は避けられない. このような理由から, GCD は, modular アルゴリズムにより計算されることが多い. modular アルゴリズムとは, 係数環の剰 余環における演算結果からもとの環上の結果を得るタイプのアルゴリズムの総称であ る. modular アルゴリズムには, 中国剰余定理を用いるものと, Hensel 構成を用いる ものがある. 後者については因数分解の節で詳しく述べることとし,ここでは,前者に ついて述べる.

命題 5.22 (中国剰余定理)可換環AのイデアルA₁,· · ·, A_rの任意の対(A_i, A_j)(i6=j) に対し,A_i+A_j =A ならば,

A/^YA_i '^MA/A_i.

[証明]r = 2 のときを示す. A₁ +A₂ = A より a₁ +a₂ = 1 なるa_i ∈ A_i が存在す る. 任意の x, y ∈ A に対し, z =xa₂ +ya₁ と置くと, z ≡ x (mod A₁) かつ z ≡ y (mod A₂) より,標準的写像

φ :A →A/A₁⊕A/A₂

は全射かつKer(φ) = A₁ ∩A₂ よりA/A₁ ∩ A₂ ' A/A₁ ⊕A/A₂. ここで, A₁A₂ ⊂ A₁∩A₂ = (A₁∩A₂)·(A₁+A₂)⊂A₁A₂ より, A₁A₂ =A₁∩A₂.よって

A/A1A2 'A/A1⊕A/A2.

一般の場合は, A₁+A₂· · ·A_r ⊃^Q_i≥2(A₁+A_i)31 より帰納法が使える. 2

5.5. MODULAR アルゴリズム 39 系 5.23 A を Euclid 環とする. m_i ∈A が互いに素ならば, A/(^Qm_i)'^LA/(m_i).

例 5.24 K を体とする. f_i ∈K[x] が互いに素ならば,K[x]/(^Qf_i)'^LK[x]/(f_i).

これは, 有限体上の因数分解に用いられる. また, f_i としてx−a_i なる形のものを とれば, 補間法をあらわすと考えられる.

例 5.25 m_i ∈Zが互いに素ならば, Z/(^Qm_i)'^LZ/(m_i).

次の補題は, modular 演算によるイメージをもとの空間に引き戻す際に常に用い られる.

補題 5.26 a ≡a⁰ modA, |a| ≤B, |a⁰| ≤A/2,A >2B ならば,a =a⁰.

[証明]a−a⁰ =kA とする. |a−a⁰| ≤ |a|+|a⁰| ≤B+A/2< A よりk = 0. 2

中国剰余定理の応用として, Z[x]における GCD 計算を例にとる.

f, g ∈Z[x], h= GCD(f, g)∈Z[x]

とする. この時,

GCD(f modp_i, g modp_i) = hmodp_i

なる素数p_i が与えられれば, 係数に対して中国剰余定理を適用して, m =^Ypi|(h−h1)

なる h1 を構成できる. ここで, m が十分大きければ, h1 の法 m での一意性により, h₁ の係数にm を加減して係数の絶対値を m/2以下としたものは, h と一致する. 問 題は,あらかじめ, 法p_i でのGCD が,真の GCD の像となっている, すなわち妥当で あるかどうか不明であるという点であるが, 妥当でないp は有限個しかないことがわ

かる(互いに素な場合の終結式を考えればよい). pの妥当性は法 pでの GCDの次数

が最低という条件で特徴づけられるため, さまざまなp での GCD計算を繰り返すこ とにより判定できる.

このほか, 整数に対する中国剰余定理は, 拡張Euclid 互除法, 行列式,終結式の計 算に用いられる. この方法が効力を発揮するのは,結果の大きさに比較して,途中の計 算において大きな式が現れる場合(中間式膨張)である. 現在主要なシステムにおいて は, GCD は, 後で述べる Hensel 構成により計算される場合が多いが, 前処理として,

いくつかの数あるいは式を法としてGCD を計算してみることは, GCD が 1 である 場合のチェックとして有効である.

最後に,剰余環での像から, 逆像を求める方法を2 つ紹介する. 環 R は, 整数環ま たは, 体上の一変数多項式環とし, m₁,· · ·, m_r ∈R は互いに素であるとする. この時, 与えられた u1,· · ·, ur ∈R に対し

u≡ui (mod mi)

なるu∈R を求めることが目標である. m=^Qmi とおく.

方法 5.27 (Lagrange 補間) GCD(m_i, m/m_i) = 1 より, ある v_i, w_i ∈ R が存在して v_im/m_i+w_im_i = 1. この時L_i =v_im/m_i とおけばL_i ≡δ_ij (mod m_j). これにより, u=^PuiLi とおけば u≡ui (mod mi).

これは, 法の数が固定の時, 一度, 基底 L_i を計算してしまえば, 任意のu_i に対して 線形結合を作るだけで解が得られるが, 法の数が増えた時に基底を計算し直す必要が ある.

方法 5.28 (Newton 補間) i < j のとき GCD(m_i, m_j) = 1 より, ある v_ij, N_ij ∈ R が存在して v_ijm_j +N_ijm_i = 1. この時N_ijm_i ≡ 1 (mod m_j), i < j. これにより u=v_rm_r−1m_r−2+· · ·+v₂m₁ +v₁ なる形で uを求めると

v₁ =u₁

v_j = (· · ·((u_j −v₁)N_1j −v₂)N_2j− · · · −v_j−1)N_j−1,j (mod m_j))

· · ·

これは, m₁,· · ·, m_r に対して構成された解を用いてm₁,· · ·, m_r+1 での解を計算して いる. その際,新たに付け加えたm_r+1 を法とする, m₁,· · ·, m_r の逆元の計算を行なっ ている. v_j の計算が複雑に見えるが,実際には,j −1 に対する解 u⁰ を用いて,

(uj −u⁰)(m1· · ·mj−1)⁻¹ modmj

を計算しているに過ぎない. 構成法からわかるように,これは,法の数を増やして精度 を上げていくタイプのアルゴリズムに向く.

Chapter 6

多項式の因数分解

6.1 有限体

計算機代数においては, 整数に関する演算を効率よく行うことを目的として, 適当な 素数 pを選んで,p を法とする演算 (modular演算) を行ったのち,整数に関する結果 を得るという手法がしばしば用いられる. また,暗号に関する計算のように,有限体に おける計算そのものが対象となっている場合もある. 本節では, 有限体に関する基本 的事項に関し, なるべく self contained な形で述べる.

定義 6.1 有限個の元からなる体を有限体と呼ぶ. q 個の元からなる体を GF(q) と 書く.

命題 6.2 GF(q) の標数はある素数 p で, q=pⁿ. ここで, n= [GF(q) :GF(p)].

[証明]標数 0 ならば Q ⊂ GF(q) となるから標数は正. p > 0 を標数とすると, GF(p)⊂GF(q)より GF(q)/GF(p) は有限次代数拡大. その拡大次数をn とおけば, {w₁,· · ·, w_n} ⊂GF(q)なる GF(p) 上線形独立な基底が存在して,

GF(q) =GF(p)w₁⊕ · · · ⊕GF(p)w_n よって, |GF(q)|= (|GF(p)|)ⁿ =pⁿ. 2

命題 6.3 GF(q) (q=pⁿ)はx^q−1−1,x^q−xの最小分解体で,x^q−x= ^Y

α∈GF(q)

(x−α).

[証明]乗法群 GF(q)^× は有限群で, その位数は q−1 より, 全ての元 α ∈ GF(q)^× に 対しα^q−1 = 1 すなわちα は x^q−1−1 の根. x^q−1−1 の根はこれで尽くされるから,

x^q−1−1 = ^Y

α∈GF(q)^×

(x−α), x^q−x= ^Y

α∈GF(q)

(x−α).

2

41

系 6.4 GF(q) の標数が奇数とする.

F₊ ={α∈GF(q)|α^(q−1)/2 = 1}, F₋={α∈GF(q)|α^(q−1)/2 =−1}

とおけば,GF(q) = F+∪F−∪ {0} で |F+|=|F−|= (q−1)/2.

[証明]x^q−x=x(x^(q−1)/2−1)(x^(q−1)/2+1)なる分解が成り立つから,GF(q)が上のよう に分解されることがわかる. F₊ はx^(q−1)/2−1の根全体で,次数から|F₊|= (q−1)/2 がわかる. F₋ も同様. 2

命題 6.5 一つの体 K に含まれる GF(q) (q=pⁿ), GF(q⁰) (q⁰ =pⁿ⁰) に対し GF(q)⊂GF(q⁰)⇔n|n⁰.

[証明]GF(q)⊂GF(q⁰)とすれば,[GF(q) :GF(p)]|[GF(q⁰) :GF(p)]よりn|n⁰. 逆にn|n⁰ とする. GF(q⁰) は K に含まれる, x^q0 −x の最小分解体だから,

GF(q⁰) ={α ∈K |α^q0 −α= 0}

同様に,

GF(q) ={α∈K |α^q−α= 0}

n|n⁰より(q−1)|(q⁰−1)が言えるから,x^q−x|x^q0−x.よって,α∈GF(q)⇒α∈GF(q⁰).

2

系 6.6 GF(p) の代数的閉包 Ω を一つ定めれば, GF(q) ⊂ Ω は, Ω における x^q−x の最小分解体として一意に定まる.

命題 6.7 GF(q)^× は位数q−1の巡回群.

[証明]G=GF(q)^× は有限アーベル群より, 1< ni ∈Z(i= 1,· · ·, l), ni|nj (i < j)が 存在して,

G'^MZ/(ni).

l > 1 とすれば, 少なくとも n²₁ 個の元が xⁿ¹ −1 = 0 の根となるが, これは不可能.

よって

l= 1, G'Z/(n₁).

2

6.2. 無平方分解 43