APX1-2 元吉論文のアルゴリズムでの\(f(x)\)の因数分解計算
(step.1) \(v\) の定義多項式を \(g(x)\) とする。但し \(g(v)=0\) である。
(step.2) \(f(x-s \cdot v)\) と \(g(v)\) とで、\(v\) に関する終結式 \(Res(f(x-sv),g(v),v)=R(x)\)
を求めるが、この時 \(R(x)\) が無平方になるように\(s\)を決める。
(step.3) \(R(x)\) を \(F_0\) 上で因数分解する。 \(R(x)=(-1) \cdot R_1(x)R_2(x)R_3(x)\)
（注【例題2】の場合、符号を気にしないように(-1)を抜き出しました）
(step.4) 各\(R_i(x)\)と\(f(x-sv)\) とのGCDをとる。
\(f_i(x)=GCD(R_i(x),f(x-sv))\) とすると
\(f(x)=f_1(x+sv)f_2(x+sv)f_3(x+sv)\) となって因数分解が出来る。
実は、上記アルゴリズムの(step.1)～(step.3)までは、既に前節で計算が完了しております。
簡単に結果を再掲します。 （なお、以下の計算では \([s=-1]\) としております。）
\begin{align} \setCounter{33} (step.1) \quad &f(x)=x^3-3x+1=(x-\alpha)(x-\beta)(x-\gamma) \qquad g(v)=v^3-9v-9 \\ &\notag \\ (step.2) \quad &Res(f(x+v),g(v),v)=R(x) \notag \\ & \qquad =-(x^3-21x+37)(x^3-12x-8)(x^3-3x+1)\\ \notag \\ (step.3) \quad &R(x)=-R_1(x) \cdot R_2(x) \cdot R_3(x) \notag \\ \notag \\ & R_1(x)=x^3-21x+37, \quad R_2(x)=x^3-12x-8, \quad R_3(x)=x^3-3x+1\\ \end{align}
以降は「(step.4) 各 \(R_i(x)\) と \(f(x-sv)\) とのGCDをとる。」を計算してみます。
GCDの計算は共通因子を求める計算です。 では、「 \(R_i(x)\) と \(f(x-sv)\) の共通因子は何か？」
前頁の式(25)より \(R_i(x)\) は式(37)で表現されます。一方 \(f(x+v)\) を \(\{ \ v,\alpha,\beta,\gamma \ \}\) を 使って、1次式の積で表現したのが式(38)です。更に \(\bbox[#FFC0CB]{[ \ v_1=v \ ]}\) である事を考慮すると、 \(f(x+v)\) の3つの因子と、\(R_i\) の同じ色の中で共通因子を探すと、 簡単に見つける事が出来て、各GCDは式(39)となる事が判ります。
逆に考えると、式(38)は\(f(x+v)\)が代数体\(F_0(v)\)で1次式に因数分解された式です。即ち式(38)の 各1次多項式が計算出来れば、\(f(x)\)が因数分解されたことになります。「その各1次多項式は 式(39)ですよ」と言っているわけですね。これが、代数体上での因数分解とGCDを結びつけている ポイントだと思います。
元吉アルゴリズムの核心が式(37)～(39)に凝縮されているのではないでしょうか！
\begin{align} &\left\{ \begin{array}{l} R_1(x)=\bbox[#FFFF00]{ H_1=(x+v_1-\alpha)(x+v_4-\beta)(x+v_5-\gamma)}\\ R_2(x)=\bbox[#7FFF00]{ H_2=(x+v_1-\beta)(x+v_4-\gamma)(x+v_5-\alpha)}\\ R_3(x)=\bbox[#00FFFF]{ H_3=(x+v_1-\gamma)(x+v_4-\alpha)(x+v_5-\beta)} \end{array} \right. \\ \notag \\ &f(x+v)=\bbox[#FFFF00]{ (x+v-\alpha) }\bbox[#7FFF00]{(x+v-\beta)}\bbox[#00FFFF]{(x+v-\gamma)} \\ \notag \\ &\left\{ \begin{array}{l} f_1(x)=GCD(R_1(x),f(x+v))=GCD(H_1,f(x+v))=\bbox[#FFFF00]{(x+v-\alpha)}\\ f_2(x)=GCD(R_2(x),f(x+v))=GCD(H_2,f(x+v))=\bbox[#7FFF00]{(x+v-\beta)}\\ f_3(x)=GCD(R_3(x),f(x+v))=GCD(H_3,f(x+v))=\bbox[#00FFFF]{(x+v-\gamma)} \end{array} \right. \\ \end{align}
計算例：互除法による \(R_1(x)\) と \(f(x+v)\) のGCDの計算
それでは、実際に互除法を用いて \(r_i\) と \(f(x+v)\) のGCDを求めてみます。互除法は変数 \(x\) に関して実行されていることに注意してください。計算は \(g(v)\) が生成する 代数体 \(F_0(v)\) 上で計算しております。 又、計算過程の式が見やすいように、各ステップを行列表示しております。更に計算が複雑にならないように、 剰余された多項式の最高次数の係数を \(c_i\) として抜き出し、各 \(r_i\) の最高次数の係数が \(1\) となるように しました。その際 \(c_i\) の逆数 \(ic_i\) も求めておきました。
\begin{align} &(step.4-0) \notag \\ \notag \\ &r_0=R_1={{x}^{3}}-21 x+17 \\ &r_1=f(x+v)=(x+v)^3-3(x+v)-1={{x}^{3}}+3 v {{x}^{2}}+3 {{v}^{2}} x-3 x+{{v}^{3}}-3 v-1 \notag \\ &\qquad \qquad \qquad ={{x}^{3}}+3 v {{x}^{2}}+3 {{v}^{2}} x-3 x+6 v+10 \quad ( \ mod \ g(v) \ )\\ \notag \\ &(step.4-1) \ Euclidean Algorithm \notag \\ \notag \\ &\begin{pmatrix} r_0\\r_1 \end{pmatrix} = \begin{pmatrix} q_1 & c_2 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} r_1\\r_2 \end{pmatrix} \qquad Q_1= \begin{pmatrix} q_1 & c_2 \\ 1 & 0 \end{pmatrix} \qquad Q_1^{-1}=\frac{1}{c_2}\cdot \begin{pmatrix} 0 & c_2 \\ 1 & -q_1 \end{pmatrix} \\ \notag \\ &q_1=1 \qquad r_2={{x}^{2}}+\frac{2 {{v}^{2}} x}{3}+v x-6 x-{{v}^{2}}+11 \\ &c_2=-3v \qquad \frac{1}{c_2}=ic_2=\frac{1}{3}-\frac{{{v}^{2}}}{27} \qquad c_2\cdot ic_2=1 \quad ( \ mod \ g(v) \ ) \notag \\ \notag \\ &(step.4-2) \ Euclidean Algorithm \notag \\ \notag \\ &\begin{pmatrix} r_1\\r_2 \end{pmatrix} = \begin{pmatrix} q_2 & c_3 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} r_2\\r_3 \end{pmatrix} \qquad Q_2= \begin{pmatrix} q_2 & c_3 \\ 1 & 0 \end{pmatrix} \qquad Q_2^{-1}=\frac{1}{c_3} \cdot \begin{pmatrix} 0 & c_3 \\ 1 & -q_2 \end{pmatrix} \\ \notag \\ &q_2=x-\frac{2 {{v}^{2}}}{3}+2 v+6 \qquad \bbox[#FFFF00]{r_3=x+\frac{{{v}^{2}}}{3}+v-2} \\ &c_3=-2 {{v}^{2}}+4 v+16 \qquad \frac{1}{c_3}=ic_3=-\frac{3 {{v}^{2}}}{38}+\frac{7 v}{38}+\frac{17}{38} \qquad c_3\cdot ic_3=1 \quad ( \ mod \ g(v) \ ) \notag \\ \notag \\ &(step.4-3) \ Euclidean Algorithm \notag \\ \notag \\ &\begin{pmatrix} r_2\\r_3 \end{pmatrix} = \begin{pmatrix} q_3 & c_4 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} r_3\\r_4 \end{pmatrix} \qquad Q_3= \begin{pmatrix} q_3 & c_4 \\ 1 & 0 \end{pmatrix} \qquad Q_3^{-1}=\frac{1}{c_4} \cdot \begin{pmatrix} 0 & c_4 \\ 1 & -q_3 \end{pmatrix} \\ \notag \\ &q_3=x+\frac{{{v}^{2}}}{3}-4 \qquad r_4=0 \\ &c_4=1 \qquad \frac{1}{c_4}=ic_4=1 \qquad c_4\cdot ic_4=1 \quad ( \ mod \ g(v) \ ) \notag \\ \end{align}
\begin{align} &\left\{ \begin{array}{l} \quad f_1(x)=GCD(R_1(x),f(x+v))=\bbox[#FFFF00]{ r_3=x+\frac{{{v}^{2}}}{3}+v-2}\\ \quad f_2(x)=GCD(R_2(x),f(x+v))=\bbox[#7FFF00]{ x-\frac{2 {{v}^{2}}}{3}+2 v+4 }\\ \quad f_3(x)=GCD(R_3(x),f(x+v))=\bbox[#00FFFF]{x+\frac{{{v}^{2}}}{3}-2 } \end{array} \right. \\ \end{align}
Profile
Name:scruta Daily life:mowing
Revision history
1st upload: 2023/06/17
revision2 : 2023/07/27
maxima programs
もしご興味があれば、下記のページよりダウンロード出来ます。
但し、何の工夫もないプログラムです。
download pageへ
Mail
もしご意見があれば下記のメールアドレスにe-mailでお送り下さい
（なおスパムメール対策のために、メールアドレスを画像表示しています）
