Annotation of OpenXM/doc/compalg/factor.tex, Revision 1.1
1.1 ! noro 1: \chapter{$BB?9`<0$N0x?tJ,2r(B}
! 2:
! 3: \section{$BM-8BBN(B}
! 4: $B7W;;5!Be?t$K$*$$$F$O(B, $B@0?t$K4X$9$k1i;;$r8zN($h$/9T$&$3$H$rL\E*$H$7$F(B,
! 5: $BE,Ev$JAG?t(B $p$ $B$rA*$s$G(B, $p$ $B$rK!$H$9$k1i;;(B (modular $B1i;;(B) $B$r9T$C$?$N(B
! 6: $B$A(B, $B@0?t$K4X$9$k7k2L$rF@$k$H$$$&<jK!$,$7$P$7$PMQ$$$i$l$k(B. $B$^$?(B, $B0E9f$K(B
! 7: $B4X$9$k7W;;$N$h$&$K(B, $BM-8BBN$K$*$1$k7W;;$=$N$b$N$,BP>]$H$J$C$F$$$k>l9g$b(B
! 8: $B$"$k(B.
! 9: $BK\@a$G$O(B, $BM-8BBN$K4X$9$k4pK\E*;v9`$K4X$7(B, $B$J$k$Y$/(B self contained $B$J(B
! 10: $B7A$G=R$Y$k(B.
! 11:
! 12: \begin{df}
! 13: $BM-8B8D$N85$+$i$J$kBN$rM-8BBN$H8F$V(B.
! 14: $q$ $B8D$N85$+$i$J$kBN$r(B $GF(q)$ $B$H=q$/(B.
! 15: \end{df}
! 16:
! 17: \begin{pr}
! 18: $GF(q)$ $B$NI8?t$O$"$kAG?t(B $p$ $B$G(B, $q=p^n$. $B$3$3$G(B, $n=[GF(q):GF(p)]$.
! 19: \end{pr}
! 20: \proof
! 21: $BI8?t(B 0 $B$J$i$P(B $\Q \subset GF(q)$ $B$H$J$k$+$iI8?t$O@5(B. $p>0$ $B$rI8?t$H$9$k$H(B,
! 22: $GF(p) \subset GF(q)$ $B$h$j(B $GF(q)/GF(p)$ $B$OM-8B<!Be?t3HBg(B. $B$=$N3HBg<!?t$r(B
! 23: $n$ $B$H$*$1$P(B, $\{w_1,\cdots,w_n\} \subset GF(q)$ $B$J$k(B $GF(p)$ $B>e@~7A(B
! 24: $BFHN)$J4pDl$,B8:_$7$F(B,
! 25: $$GF(q)=GF(p)w_1\oplus\cdots \oplus GF(p)w_n$$
! 26: $B$h$C$F(B, $|GF(q)|=(|GF(p)|)^n=p^n$. \qed
! 27:
! 28: \begin{pr}
! 29: $GF(q)$ \quad ($q=p^n$) $B$O(B $x^{q-1}-1$, $x^q-x$ $B$N:G>.J,2rBN$G(B,
! 30: $\displaystyle x^q-x=\prod_{\alpha \in GF(q)}(x-\alpha).$
! 31: \end{pr}
! 32: \proof
! 33: $B>hK!72(B $GF(q)^{\times}$ $B$OM-8B72$G(B, $B$=$N0L?t$O(B $q-1$ $B$h$j(B,
! 34: $BA4$F$N85(B $\alpha \in GF(q)^{\times}$ $B$KBP$7(B $\alpha^{q-1}=1$ $B$9$J$o$A(B
! 35: $\alpha$ $B$O(B $x^{q-1}-1$ $B$N:,(B. $x^{q-1}-1$ $B$N:,$O$3$l$G?T$/$5$l$k$+$i(B,
! 36: $$x^{q-1}-1=\prod_{\alpha \in GF(q)^{\times}}(x-\alpha), \quad
! 37: x^q-x = \prod_{\alpha \in GF(q)}(x-\alpha).$$ \qed
! 38:
! 39: \begin{co}
! 40: $GF(q)$ $B$NI8?t$,4q?t$H$9$k(B.
! 41: $$F_{+}=\{\alpha \in GF(q) \mid \alpha^{(q-1)/2}=1\},
! 42: \quad F_{-}=\{\alpha \in GF(q) \mid \alpha^{(q-1)/2}=-1\}$$
! 43: $B$H$*$1$P(B, $GF(q)=F_{+} \cup F_{-} \cup \{0\}$ $B$G(B $|F_{+}|=|F_{-}|=(q-1)/2.$
! 44: \end{co}
! 45: \proof
! 46: $x^q-x = x(x^{(q-1)/2}-1)(x^{(q-1)/2}+1)$
! 47: $B$J$kJ,2r$,@.$jN)$D$+$i(B, $GF(q)$ $B$,>e$N$h$&$KJ,2r$5$l$k$3$H$,$o$+$k(B.
! 48: $F_{+}$ $B$O(B $x^{(q-1)/2}-1$ $B$N:,A4BN$G(B, $B<!?t$+$i(B $|F_{+}|=(q-1)/2$ $B$,$o$+$k(B.
! 49: $F_{-}$ $B$bF1MM(B. \qed
! 50:
! 51: \begin{pr}
! 52: $B0l$D$NBN(B $K$ $B$K4^$^$l$k(B $GF(q)$ ($q=p^n$), $GF(q')$ ($q'=p^{n'}$) $B$KBP$7(B
! 53: $$ GF(q) \subset GF(q') \Leftrightarrow n | n'.$$
! 54: \end{pr}
! 55: \proof
! 56: $GF(q) \subset GF(q')$ $B$H$9$l$P(B,$[GF(q):GF(p)]|[GF(q'):GF(p)]$ $B$h$j(B $n|n'.$
! 57:
! 58: $B5U$K(B $n|n'$ $B$H$9$k(B. $GF(q')$ $B$O(B $K$ $B$K4^$^$l$k(B, $x^{q'}-x$ $B$N:G>.J,2r(B
! 59: $BBN$@$+$i(B,
! 60: $$GF(q')=\{\alpha \in K \mid \alpha^{q'}-\alpha=0\}$$
! 61: $BF1MM$K(B,
! 62: $$GF(q)=\{\alpha \in K \mid \alpha^{q}-\alpha=0\}$$
! 63: $n|n'$ $B$h$j(B $(q-1)|(q'-1)$ $B$,8@$($k$+$i(B, $x^q-x|x^{q'}-x.$
! 64: $B$h$C$F(B, $\alpha \in GF(q) \Rightarrow \alpha \in GF(q').$
! 65: \qed
! 66:
! 67: \begin{co}
! 68: $GF(p)$ $B$NBe?tE*JDJq(B $\Omega$ $B$r0l$DDj$a$l$P(B, $GF(q) \subset \Omega$
! 69: $B$O(B, $\Omega$ $B$K$*$1$k(B $x^q-x$ $B$N:G>.J,2rBN$H$7$F0l0U$KDj$^$k(B.
! 70: \end{co}
! 71:
! 72: \begin{pr}
! 73: $GF(q)^{\times}$ $B$O0L?t(B $q-1$ $B$N=d2s72(B.
! 74: \end{pr}
! 75: \proof
! 76: $G=GF(q)^{\times}$ $B$OM-8B%"!<%Y%k72$h$j(B, $1 < n_i \in \Z$ ($i=1,\cdots,l$),
! 77: $n_i | n_j$ ($i<j$) $B$,B8:_$7$F(B,
! 78: $$G \simeq \bigoplus \Z/(n_i).$$
! 79: $l>1$ $B$H$9$l$P(B, $B>/$J$/$H$b(B $n_1^2$ $B8D(B
! 80: $B$N85$,(B $x^{n_1}-1=0$ $B$N:,$H$J$k$,(B, $B$3$l$OIT2DG=(B. $B$h$C$F(B
! 81: $$l=1,\quad G\simeq \Z/(n_1).$$ \qed
! 82:
! 83: \begin{pr}
! 84: $f$ $B$r(B $GF(q)$ $B>e4{Ls$H$9$k$H(B,
! 85: $$f | x^{q^n}-x \Leftrightarrow \deg(f) | n$$
! 86: \end{pr}
! 87: \proof
! 88: $GF(q)$ $B$NBe?tE*JDJq(B $\Omega$ $B$r0l$D8GDj$9$k(B.
! 89: $f$ $B$,(B $GF(q)$ $B>e4{Ls$H$9$k(B. $f$ $B$N(B $\Omega$ $B$K$*$1$k:,$r(B $\alpha$ $B$H$9$k(B.\\
! 90: \underline{$\Rightarrow$)}
! 91: \quad $f|x^{q^n}-x$ $B$H$9$k(B. $B$3$N$H$-(B $f(\alpha)=0$ $B$h$j(B $\alpha^{q^n}-\alpha=0.$
! 92: $B$h$C$F(B, $\alpha \in GF(q^n)\subset \Omega.$ $B$3$l$+$i(B
! 93: $GF(q)(\alpha)\subset GF(q^n).$ $B$f$($K(B
! 94: $$\deg(f)=[GF(q)(\alpha):GF(q)]|[GF(q^n):GF(q)]=n.$$\\
! 95: \underline{$\Leftarrow$)}
! 96: $\deg(f)|n$ $B$H$9$k(B. $GF(q)(\alpha)$, $GF(q^n)$ $B$O0l$D$NBN(B $\Omega$ $B$K4^$^$l$k(B
! 97: $B$+$i(B,
! 98: $GF(q)(\alpha) \subset GF(q^n)$
! 99: $B$3$l$h$j(B $\alpha^{q^n}-\alpha=0$. $f$ $B$O(B $\alpha$ $B$N:G>.B?9`<0$@$+$i(B
! 100: $$f|x^{q^n}-x.$$
! 101: \qed\\
! 102: $x^{q^n}-x$ $B$O=E:,$r;}$?$J$$$+$i(B, $B<!$,@.$jN)$D(B.
! 103:
! 104: \begin{co}
! 105: \label{irred_mod}
! 106: $F = \{ f | f : GF(q)$ $B>e4{Ls(B, $B%b%K%C%/$G(B $\deg(f)|n\}$
! 107: $B$H$*$1$P(B $x^{q^n}-x = \prod_{f\in F} f.$
! 108: \end{co}
! 109:
! 110: \section{$BL5J?J}J,2r(B}
! 111: $B0J2<$G=R$Y$k$5$^$6$^$J0x?tJ,2r%"%k%4%j%:%`$O(B, $BF~NO$,=EJ#0x;R$r$b$D$3$H(B
! 112: $B$r5v$5$J$$(B. $B$h$C$F(B, $B0J2<$K=R$Y$kL5J?J}J,2r$r9T$J$C$F$*$/I,MW$,$"$k(B.
! 113:
! 114: \begin{df}
! 115: $B=EJ#0x;R$r;}$?$J$$B?9`<0$r(B{\bf $BL5J?J}(B (squarefree)} $B$H$$$&(B.
! 116: $f \in K[x]$ $B$KBP$7(B,
! 117: $$f = \prod g_1^{n_i}$$$B$G3F(B $g_i$ $B$OL5J?J}$+$D8_$$$KAG$JB?9`(B
! 118: $B<0$G(B $n_1<n_2<\cdots$ $B$H$J$C$F$$$k;~(B, $B$3$N0x?tJ,2r$r(B $f$ $B$N(B {\bf $BL5J?J}(B
! 119: $BJ,2r(B} $B$H8F$V(B.
! 120: \end{df}
! 121:
! 122: $B$^$:(B, $BI8?t(B 0 $B$NBN(B $K$ $B$NL5J?J}J,2r%"%k%4%j%:%`$K$D$$$F=R$Y$k(B.
! 123:
! 124: \begin{lm} $K$ $B$rI8?t(B 0 $B$NBN$H$9$k(B.
! 125: $f \in K[x]$ $B$KBP$7(B, $f = \prod_i g_i^{n_i}$ $B$r(B $f$ $B$NL5J?J}J,2r$H(B
! 126: $B$9$k$H$-(B,
! 127: $$\GCD(f,f') = \prod_i g_i^{n_i-1}.$$
! 128: \end{lm}
! 129: \proof
! 130: $$f' = \prod_i g_i^{n_i-1}(\sum_i n_i g'_i \prod_{k\neq i}g_k)$$
! 131: $B$h$j(B
! 132: $$\GCD(f,f') = \prod_i g_i^{n_i-1} \GCD(\prod_k g_k,\sum_i n_i g'_i \prod_{k\neq i}g_k)$$
! 133: $K$ $B$NI8?t$,(B 0 $B$h$j(B $n_i \neq 0$, $g'_i \neq 0$ $B$@$+$i(B,
! 134: $$\GCD(\prod_k g_k,\sum_i n_i g'_i \prod_{k\neq i}g_k) = \prod_k \GCD(g_k,\sum_i n_i g'_i \prod_{k\neq i}g_k) = \prod_k \GCD(g_k,g'_k)$$
! 135: $B$3$3$G(B $g_k$ $B$,L5J?J}$h$j(B, $g_k$ $B$r4{LsJ,2r$7$F9M$($l$P(B $\GCD(g_k,g'_k)=1$.
! 136: $B$h$C$F(B, $$\GCD(f,f') = \prod_i g_i^{n_i-1}.$$ \qed
! 137:
! 138:
! 139: \begin{al}($BL5J?J}J,2r(B)
! 140: \label{sqfr}
! 141: \begin{tabbing}
! 142: Input : $f(x) \in K[x]$ ($K$ $B$OI8?t(B 0 $B$NBN(B)\\
! 143: Output : $f$ $B$NL5J?J}J,2r(B $f= g_1^{n_1}g_2^{n_2}\cdots$\\
! 144: \\
! 145: $F \leftarrow 1$\\
! 146: $flat \leftarrow f/\GCD(f,f'),\quad m \leftarrow 0,\quad counter \leftarrow 1$\\
! 147: while\= ( $flat \neq constant$ ) \{\\
! 148: {\rm(a)}\> while \= ( $flat | f$ ) \{\\
! 149: \>\>$f \leftarrow f/flat,\quad m \leftarrow m + 1$\\
! 150: \>\}\\
! 151: {\rm(b)}\> $flat_1 \leftarrow \GCD(flat,f)$\\
! 152: \>$g \leftarrow flat/flat_1,\quad flat \leftarrow flat_1$\\
! 153: {\rm(c)}\>$F \leftarrow F\cdot g^m, \quad counter \leftarrow counter+1$\\
! 154: \}\\
! 155: return $F$\\
! 156: \end{tabbing}
! 157: \end{al}
! 158: \begin{pr}
! 159: \label{valid_sqfr}
! 160: $B%"%k%4%j%:%`(B \ref{sqfr} $B$O(B $f$ $B$NL5J?J}J,2r$r=PNO$9$k(B.
! 161: \end{pr}
! 162: \proof (a) $B$K$*$$$F(B $counter = k$ $B$N;~(B,
! 163: \begin{center}
! 164: $f = g_k^{n_k-n_{k-1}}g_{k+1}^{n_{k+1}-n_{k-1}}\cdots$, \quad
! 165: $flat = g_k g_{k+1}\cdots$, \quad
! 166: $m = n_{k-1}\quad (n_0 = 0)$
! 167: \end{center}
! 168: $B$"$k$3$H$r5"G<K!$K$h$j<($9(B.
! 169: $k = 1$ $B$N;~$OJdBj$h$j@5$7$$(B. $k$ $B$^$G@5$7$$$H$9$k(B. $B2>Dj$h$j(B,
! 170: $flat^{n_k-n_{k-1}} | f\quad$ $B$+$D(B $flat^{n_k-n_{k-1}+1}{\not|} f$
! 171: $B$h$j(B(b) $B$K$*$$$F(B
! 172: $$m = n_{k-1}+(n_k-n_{k-1}) = n_k, \quad f = g_{k+1}^{n_{k+1}-n_k}\cdots$$
! 173: $B$H$J$k(B. $B$h$C$F(B, (c) $B$K$*$$$F$O(B $$flat = flat_1 = g_{k+1}\cdots$$
! 174: $B$H$J$j(B $k+1$ $B$G$b@5$7$$(B. $B$^$?(B (c) $B$K$*$$$F(B $g = g_k$, $m = n_k$ $B$H$J$C$F$$$k$+$i$3$N%"%k%4%j%:%`$O@5$7$/L5J?J}J,2r$r=PNO$9$k(B. \qed\\
! 175: $BI8?t(B $p>0$ $B$NBN(B $K$ $B>e$G$OHyJ,$7$F(B 0 $B$K$J$kB?9`<0$,B8:_$9$k$?$aCm0U$rMW$9$k(B.
! 176:
! 177: \begin{lm} $K$ $B$rI8?t(B $p>0$ $B$NM-8BBN$H$9$k(B. $K$ $B>e$N0lJQ?tB?9`<0(B $f$ $B$KBP$7(B,
! 178: $f'=0 \Leftrightarrow$ $B$"$kB?9`<0(B $g$ $B$,B8:_$7$F(B $f = g^p.$
! 179: \end{lm}
! 180:
! 181: \begin{lm} $K$ $B$rI8?t(B $p>0$ $B$NM-8BBN$H$9$k(B. $h$ $B$r(B, $f$ $B$N0x;R$N$&$A(B, $B=EJ#EY$,(B
! 182: $p$ $B$G3d$j@Z$l$k$b$N$N@Q$H$7(B, $g= f/h = \prod g_i^{n_i}$ $B$H$9$k(B. $B$3$N$H$-(B,
! 183: $$\GCD(f,f')=h\, \GCD(g,g')=h\prod g_i^{n_i-1}.$$
! 184: \end{lm}
! 185: \proof $h'=0$ $B$h$j(B $f'=g'h+gh'=g'h$. $B$h$C$F(B, $\GCD(f,f')=h\, \GCD(g,g').$
! 186: $$\GCD(g,g') = \prod_i g_i^{n_i-1} \GCD(\prod_k g_k,\sum_i n_i g'_i
! 187: \prod_{k\neq i}g_k)$$
! 188: $B2>Dj$K$h$j(B $n_i \neq 0$. $B$^$?(B $g_i$ $B$OL5J?J}$@$+$i(B,
! 189: $BA0JdBj$K$h$j(B $g'_i \neq 0$ $B$@$+$i(B,
! 190: $$\GCD(\prod_k g_k,\sum_i n_i g'_i \prod_{k\neq i}g_k) = \prod_k \GCD(g_k,\sum_i n_i g'_i \prod_{k\neq i}g_k) = \prod_k \GCD(g_k,g'_k)$$
! 191: $B$3$3$G(B $g_k$ $B$,L5J?J}$h$j(B, $g_k$ $B$r4{LsJ,2r$7$F9M$($l$P(B $\GCD(g_k,g'_k)=1$.
! 192: $B$h$C$F(B, $$\GCD(g,g') = \prod_i g_i^{n_i-1}.$$ \qed
! 193:
! 194: \begin{al}($BL5J?J}J,2r(B)
! 195: \label{sqfrmod}
! 196: \begin{tabbing}
! 197: Input : $f(x) \in K[x]$ ($K$ $B$OI8?t(B $p>0$ $B$NBN(B)\\
! 198: Output : $f$ $B$NL5J?J}J,2r(B $f= g_1^{n_1}g_2^{n_2}\cdots$\\
! 199: $F \leftarrow 1$\\
! 200: if \= $f'\neq 0$ \{\\
! 201: \> $flat \leftarrow f/\GCD(f,f'),\quad m \leftarrow 0,\quad counter \leftarrow 1$\\
! 202: \>while\= ( $flat \neq constant$ ) \{\\
! 203: {\rm(a)}\>\> while \= ( $flat | f$ ) \{\\
! 204: \>\>\>$f \leftarrow f/flat,\quad m \leftarrow m + 1$\\
! 205: \>\>\}\\
! 206: {\rm(b)}\>\> $flat_1 \leftarrow \GCD(flat,f)$\\
! 207: \>\>$g \leftarrow flat/flat_1,\quad flat \leftarrow flat_1$\\
! 208: {\rm(c)}\>\>$F \leftarrow F\cdot g^m, \quad counter \leftarrow counter+1$\\
! 209: \>\}\\
! 210: \}\\
! 211: if $f \neq constant$ \{\\
! 212: \> $g \leftarrow f^{1/p}$\\
! 213: \> $g = g_1^{n_1}g_2^{n_2}\cdots$ $B$HL5J?J}J,2r(B\\
! 214: \> $F = F\cdot g_1^{pn_1}g_2^{pn_2}\cdots$\\
! 215: \}\\
! 216: return $F$
! 217: \end{tabbing}
! 218: \end{al}
! 219: $B$3$N>l9g(B, $flat$ $B$,(B, $f$ $B$N=EJ#EY$,(B $p$ $B$G3d$j@Z$l$J$$0x;R$N@Q$H$J$k$+$i(B,
! 220: $flat$ $B$,Dj?t$H$J$C$?;~E@$G(B $f$ $B$N3F0x;R$N=EJ#EY$O(B $p$ $B$G3d$j@Z$l$k(B.
! 221: $B$h$C$F(B, $1/p$ $B>h$,7W;;$G$-(B, $B$=$NL5J?J}J,2r$r(B $p$ $B>h$9$l$P(B, $f$ $B$NL5J?J}(B
! 222: $BJ,2r$,7W;;$G$-$?$3$H$K$J$k(B.
! 223:
! 224: $B$3$3$G$O(B, $B78?t$rBN$H$7$?$,(B, UFD $B>e$G$O(B, $B$"$i$+$8$a(B $f$ $B$KBP$7(B
! 225: $cont(f)$$B$r7W;;$7(B, $B$=$l$G(B $f$ $B$r3d$C$F86;OE*B?9`<0$H$7$F$+$i9T$J$&(B. $B@0(B
! 226: $B?t>e$N>l9g$K$O(B, $B$3$NA`:n$OC1$K78?t$N(B GCD $B$r7W;;$9$k$3$H$r0UL#$9$k$,(B,
! 227: $BB?JQ?tB?9`<0$N>l9g(B, $BB?9`<0$N(B GCD $B$,I,MW$H$J$k(B. $B$5$i$K(B, $B78?t4D>e$G$NL5J?J}(B
! 228: $BJ,2r$bMW5a$5$l$F$$$k$J$i$P(B, $B$3$N%"%k%4%j%:%`$r:F5"E*$KMQ$$$kI,MW$,$"$k(B.
! 229:
! 230: $B$3$N%"%k%4%j%:%`$N(B Yun $B$K$h$k2~NI$bCN$i$l$F$$$k(B. $B$^$?(B, $B$3$NAGKQ$JJ}K!(B
! 231: $B$O(B, $B=EJ#EY$NBg$-$J0x;R$r$b$D>l9g$K$O(B, $B:G=i$N(BGCD $B7W;;$GB?Bg$J;~4V$rI,MW(B
! 232: $B$H$9$k>l9g$,B?$/(B, $B<BMQE*$KLdBj$,$"$k(B. $B$3$l$rHr$1$k$?$a(B, $B=EJ#EY:GBg$N0x(B
! 233: $B;R$+$i=g$KD>@\5a$a$F$$$/J}K!$,(B Wang-Trager
! 234: \cite{SQFR} $B$K$h$j9M0F$5$l$F$$$k(B. $B$3$NJ}K!$O(B, $B8e=R$9$k(B Hensel $B9=@.$H(B
! 235: $B$NAH9g$;$K$h$jBg$-$J8z2L$rH/4x$9$k(B. $B$3$l$K$D$$$F$O(B \ref{wangtrager} $B@a$G=R$Y$k(B.
! 236:
! 237:
! 238: \section{Berlekamp $B%"%k%4%j%:%`(B}
! 239:
! 240: $p$ $B$rAG?t$H$7(B, $q$ $B85BN(B $K=GF(q)$ ($q=p^n$) $B$r78?t$H$9$k0lJQ?tB?9`<0(B
! 241: $B4D(B$R = K[x]$ $B$K$*$1$k4{Ls0x;RJ,2r$r9M$($k(B.
! 242: $f(x) \in R$ $B$,L5J?J}$G$"$k$H$9$k(B. $f = \prod_{i=1}^{r}f_i$ $B$H4{LsJ,2r(B
! 243: $B$9$k$H(B, $BCf9q>jM>DjM}$K$h$j(B,
! 244: $$R/(f) \simeq \bigoplus R/(f_i).$$
! 245:
! 246: $R/(f), R/(f_i)$ $B>e$K<!$N(B$K$-$B=`F17?(B (Frobenius $B<LA|(B) $B$r9M$($k(B.
! 247: $$\pi : f \mapsto f^q \bmod f$$
! 248: $$\pi_i : f \mapsto f^q \bmod {f_i}$$
! 249: $B$9$k$H(B,
! 250: $$\Ker(\pi-I) \simeq \bigoplus \Ker(\pi_i-I)$$
! 251: $B$G$"$k(B. $B$3$3$G(B, $f_i$ $B$O4{Ls$h$j(B $R/f_i$ $B$OBN$G$"$k(B.
! 252: $B$^$?(B $x^q-x$ $B$O(B, $K$ $B$N$9$Y$F$N85$r:,$K$b$D$,(B, $BBN(B $R/f_i$ $B>e(B
! 253: $B$G9M$($l$P(B, $B:,$O$9$Y$F$3$l$G?T$/$5$l$F$$$k(B. $B$h$C$F(B
! 254: $\Ker(\pi_i-I) = K$.$B7k6I(B
! 255: $$\Ker(\pi-I) \simeq \bigoplus K$$
! 256: $B$9$J$o$A(B, $f$ $B$N4{LsB?9`<0$N8D?t$r(B $r$ $B$H$9$k$H(B, $\Ker(\pi-I)$
! 257: $B$O(B, $r$ $B8D$N(B $K$ $B$ND>OB$H$J$k(B. $B$5$i$K(B, $B$3$l$O<!$N$h$&$K8@$$BX$($i$l$k(B.
! 258:
! 259: \begin{pr}
! 260: \begin{enumerate}
! 261: \item $f|(g^q-g) \Rightarrow$ $B$"$k(B $(s_1,\cdots,s_r) \in K^r$ $B$,B8:_$7$F(B $f_i|(g-s_i)$
! 262:
! 263: \item $B$9$Y$F$N(B $(s_1,\cdots,s_r) \in K^r$ $B$KBP$7(B, $B$"$k(B $g$ $B$,B8:_$7$F(B $f|(g^q-g), f_i|(g-s_i)$
! 264: \end{enumerate}
! 265: \end{pr}
! 266: $g$ $B$O(B, $\deg(g)<\deg(f)$ $B$H$7$F$h$$$+$i(B, $g\in \Ker(\pi-I)$ $B$r$H$k$H(B,
! 267: $BE,Ev$J(B $s$ $B$KBP$7(B $\GCD(g-s,f)$ $B$O<+L@$G$J$$(B $f$ $B$N0x;R$rM?$($k(B.
! 268:
! 269: $B<!$N%"%k%4%j%:%`$OM-8BBN>e$N0lJQ?tB?9`<0$N0x?tJ,2r$r9T$&(B.
! 270:
! 271: \begin{al}(Berlekamp{\rm\cite{BERL}})
! 272: \begin{tabbing}
! 273: Input : $f(x) \in R$; $f$ $B$OL5J?J}(B\\
! 274: Output : $\{f_1,f_2,\cdots\}$ $f = f_1 f_2 \cdots$ $B$O(B $f$ $B$N4{LsJ,2r(B\\
! 275: $F = \{f\}$\\
! 276: $Q \leftarrow \pi$ $B$N9TNsI=8=(B\\
! 277: $\{e_1 = 1, e_2, \cdots, e_r\} \leftarrow \Ker(Q-I)$ $B$N(B $K$-$B4pDl(B\\
! 278: if ($r = 1$) then return $F$\\
! 279: $k \leftarrow 2$\\
! 280: do \=\{\\
! 281: \> $F_1 \leftarrow \emptyset$\\
! 282: \> while \= $F \neq \emptyset$ do \{\\
! 283: \>\> $g \leftarrow$ $F$ $B$N0l$D$N85(B \\
! 284: \>\> $F \leftarrow F \backslash \{g\}$\\
! 285: \>\> $F_g \leftarrow \{\GCD(g,e_k-s)(s \in GF(q))$ $B$N$&$A(B, $BDj?t$G$J$$$b$N(B\}\\
! 286: \>\> $g \leftarrow g/\prod_{h\in F_g} h$\\
! 287: \>\> $F_1 \leftarrow F_1 \cup F_g$ \\
! 288: \>\> if ( $g \neq 1$ ) $F_1 \leftarrow F_1 \cup \{g\}$\\
! 289: \>\> if \= ($|(F \cup F_1)| = r$) return $F \cup F_1$\\
! 290: \>\}\\
! 291: \> $k \leftarrow k+1$ \\
! 292: \> $F \leftarrow F_1$ \\
! 293: \}\\
! 294: return F
! 295: \end{tabbing}
! 296: \end{al}
! 297: $B4pDl$K$h$jA4$F$N4{Ls0x;R$,J,N%$G$-$k$3$H$O<!$NL?Bj$h$j$o$+$k(B.
! 298:
! 299: \begin{pr}
! 300: $\{e_1,\cdots,e_r\}$ $B$r(B $\Ker(\pi-I)$ $B$N(B$K$-$B4pDl$H$9$k$H(B
! 301: $B$9$Y$F$N(B $i\neq j$ $B$J$k(B $i,j$ $B$KBP$7(B, $B$"$k(B $k,s$ $B$,B8:_$7$F(B $f_i|(e_k-s), f_j{\not|}(e_k-s)$
! 302: \end{pr}
! 303: \proof
! 304: $B$3$N<gD%$,56$J$i$P(B
! 305: \begin{center}
! 306: $B$"$k(B $i,j$ $B$,B8:_$7$F(B, $B$9$Y$F$N(B $e_k, s$ $B$KBP$7(B ($(f_i|(e_k-s)\Rightarrow f_j|(e_k-s))$)
! 307: \end{center}
! 308: $B$H$J$k(B. $B$3$N;~(B, $B3F(B $k$ $B$KBP$7(B, $f_i|(e_k-s_k)$ $B$J$k(B $s_k$ $B$r$H$l$P(B,
! 309: $\{e_k\}$ $B$,4pDl$G$"$k$3$H$h$j(B
! 310: \begin{center}
! 311: $B$9$Y$F$N(B $g \in \Ker(\pi-I)$ $B$KBP$7(B, $B$"$k(B $s$ $B$,B8:_$7$F(B $f_i|(g-s), f_j|(g-s).$
! 312: \end{center}
! 313: $B$H$3$m$,(B, $\Ker(\pi-I)$ $B$NCf$K$O(B $f_i, f_j$ $B$rJ,N%$9$k$b$N$,$"$k$+$iL7=b(B. \qed
! 314:
! 315: $B0J>e=R$Y$?%"%k%4%j%:%`$O(B, $q$ $B$,>.$5$$;~$KMQ$$$i$l$k:G$b86;OE*$J7A$G$"(B
! 316: $B$k(B. $B$3$N%"%k%4%j%:%`$G$O(B, $B:G0-(B $q$ $B2s(B GCD $B$r7+$jJV$9I,MW$,@8$:$k(B. $B$7$+(B
! 317: $B$7(B, $B<B:]$K$O(B $\GCD(g,e-s)$ $B$,(B $1$ $B$^$?$O(B $g$ $B0J30$NCM$r<h$k$h$&$J(B $s$
! 318: $B$NCM$O8B$i$l$F$$$F(B, $B$=$NCM$O(B $s$ $B$N$"$kB?9`<0$N:,$H$J$C$F$$$k(B.
! 319:
! 320: \begin{pr}
! 321: $e \in \Ker(\pi-I)$ $B$KBP$7(B,
! 322: $$S=\{s \in GF(q) \mid \GCD(e-s,f) \neq 1\}$$
! 323: $B$H$*$/(B. $B$3$N$H$-(B $m(x)=\prod_{s\in S}(x-s)$
! 324: $B$H$*$1$P(B, $m(x)$ $B$O(B $e$ $B$N(B $R/(f)$ $B$K$*$1$k:G>.B?9`<0(B.
! 325: $B$9$J$o$A(B, $f|m(e)$ $B$H$J$k$h$&$J(B, $B:G>.<!?t$NB?9`<0(B.
! 326: \end{pr}
! 327: \proof
! 328: $f$ $B$N3F0x;R(B $f_i$ $B$KBP$7(B $e \equiv s_i \bmod f_i$ $B$H$J$k$h$&$J(B
! 329: $s_i$ $B$,B8:_$9$k(B. $B$3$N$H$-(B $s_i \in S$ $B$G(B
! 330: $$f_i | (e-s_i) | m(e).$$
! 331: $f$ $B$O(B $BL5J?J}$h$j(B $f | m(e).$
! 332: $B5U$K(B, $M(x)$ $B$r(B, $e$ $B$N(B $R/(f)$ $B$K$*$1$k:G>.B?9`<0$H$9$k(B.
! 333: $B$b$7(B $\deg(M)<\deg(m)$ $B$J$i$P(B, $B$"$k(B $s\in S$ $B$,B8:_$7$F(B
! 334: $$m=(x-s)q+r, \quad r \in GF(q) \backslash \{0\}$$
! 335: $B$H=q$1$k(B. $B$3$N;~(B, $f$ $B$N0x;R(B $f_i$ $B$,B8:_$7$F(B, $f_i |(e-s)$
! 336: $B$H$J$k$+$i(B, $f_i | r$. $B$3$l$OL7=b(B. \qed
! 337:
! 338: $e$ $B$N:G>.B?9`<0$O(B, $e^k$ $B$,(B $\{1,e,e^2,\cdots,e^{k-1}\}$ $B$G(B
! 339: $BD%$i$l$F$$$k$+H]$+$r(B $k=1$ $B$+$i=g$KD4$Y$k$3$H$K$h$j7hDj$G$-$k(B.
! 340:
! 341: $B:G>.B?9`<0(B $m(x)$ $B$rMQ$$$l$P(B, $m$ $B$N:,$r5a$a$5$($9$l$P(B, $B$=$l$i$K(B
! 342: $BBP$7$N$_(B GCD $B$r<B9T$9$l$P$h$$$3$H$K$J$k(B.
! 343:
! 344: \section{Cantor-Zassenhaus $B%"%k%4%j%:%`(B}
! 345: $BA0@a$G=R$Y$?(B Berlekamp $B%"%k%4%j%:%`$*$h$S:G>.B?9`<0$rMQ$$$k2~NI$K$h$C$F(B
! 346: $q$ $B$,>.$5$$>l9g$K$O==J,8zN($h$/0x?tJ,2r$G$-$k(B. $B$7$+$7(B, $q$ $B$,Bg$-$$(B
! 347: $B>l9g$K$O0J2<$G=R$Y$k$h$&$J3NN(E*%"%k%4%j%:%`$rMQ$$$J$1$l$P(B, $B8zN($h$$(B
! 348: $B0x?tJ,2r$OFq$7$$(B.
! 349: $B0J2<(B, $BA0@a$HF1MM$N5-9f$rMQ$$$k(B.
! 350:
! 351: \begin{pr}
! 352: $BI8?t(B $p$ $B$,4q?t$H$9$k(B. $e \in \Ker(\pi-I)$ $B$H$9$l$P(B,
! 353: $$\GCD(e^{(q-1)/2}-1,f) \neq 1, f$$
! 354: $B$H$J$k3NN($O(B, $k$ $B$r(B $f$ $B$N4{Ls0x;R$N8D?t$H$9$k$H$-(B
! 355: $$1-({{q-1}\over{2q}})^k-({{q+1}\over{2q}})^k.$$
! 356: \end{pr}
! 357: \proof
! 358: $f_i$ ($i=1,\cdots,k$) $B$r(B $f$ $B$N4{Ls0x;R$H$7(B,
! 359: $e \equiv s_i \bmod f_i$ ($s_i \in GF(q)$) $B$H$9$k(B.
! 360: $$e^{(q-1)/2} \equiv s_i^{(q-1)/2} \equiv 0, \pm 1 \bmod f_i$$
! 361: $B$h$j(B,
! 362: \begin{center}
! 363: $\GCD(e^{(q-1)/2}-1,f) = f \Leftrightarrow$ $B$9$Y$F$N(B $i$ $B$KBP$7(B $s_i^{(q-1)/2} \equiv 1 \bmod f_i$
! 364: \end{center}
! 365: \begin{center}
! 366: $\GCD(e^{(q-1)/2}-1,f) = 1 \Leftrightarrow$ $B$9$Y$F$N(B $i$ $B$KBP$7(B $s_i^{(q-1)/2} \equiv 0, -1 \bmod f_i$
! 367: \end{center}
! 368: $s \in GF(q)$ $B$H$9$k;~(B, $s^{(q-1)/2} \equiv 1$ $B$J$k85$O(B $(q-1)/2$ $B8D(B,
! 369: $s^{(q-1)/2} \equiv 0, -1$ $B$J$k85$O(B $(q+1)/2$ $B8D(B.
! 370: $B$h$C$F(B, $\GCD(e^{(q-1)/2}-1,f) = f$, $\GCD(e^{(q-1)/2}-1,f) = 1$ $B$J$k3NN((B
! 371: $B$O$=$l$>$l(B
! 372: $$({{q-1}\over{2q}})^k,\quad ({{q+1}\over{2q}})^k$$
! 373: $B$H$J$k(B. \qed
! 374:
! 375: $BI8?t(B 2 $B$N>l9g$r07$&$?$a$K(B, $GF(2^n)$ $B>e$NB?9`<0(B $f$ $B$N(B trace $\Tr(f)$ $B$r(B
! 376: $BDj5A$9$k(B.
! 377: \begin{df}
! 378: $GF(2^n)$ $B$K$*$$$F(B, $\Tr(x) \in GF(2^n)[x]$ $B$r(B
! 379: $$\Tr(x) = \sum_{i=0}^{n-1}x^{2^i}$$
! 380: $B$HDj5A$9$k(B.
! 381: \end{df}
! 382:
! 383: \begin{lm}
! 384: $x^{2^n}-x=\Tr(x)(\Tr(x)+1).$
! 385: \end{lm}
! 386:
! 387: \begin{co}
! 388: \begin{enumerate}
! 389: \item $a \in GF(2^n) \Rightarrow \Tr(a) \in GF(2)$
! 390: \item $|\{ s \in GF(2^n) \mid \Tr(s)=0\}| = |\{ s \in GF(2^n) \mid \Tr(s)=1 \}| = 2^{n-1}$
! 391: \end{enumerate}
! 392: \end{co}
! 393:
! 394: \begin{pr}
! 395: $BI8?t(B $p=2$ $B$H$9$k(B. $e \in \Ker(\pi-I)$ $B$H$9$l$P(B,
! 396: $$\GCD(\Tr(e),f) \neq 1, f$$
! 397: $B$H$J$k3NN($O(B, $k$ $B$r(B $f$ $B$N4{Ls0x;R$N8D?t$H$9$k$H$-(B
! 398: $1-1/2^{k-1}.$
! 399: \end{pr}
! 400: \proof
! 401: $f_i$ ($i=1,\cdots,k$) $B$r(B $f$ $B$N4{Ls0x;R$H$7(B,
! 402: $e \equiv s_i \bmod f_i$ ($s_i \in GF(q)$) $B$H$9$k(B.
! 403: $$\Tr(e) \equiv \Tr(s_i) \equiv 0, 1 \bmod f_i$$
! 404: $B$h$j(B,
! 405: \begin{center}
! 406: $\GCD(\Tr(e),f) = f \Leftrightarrow$ $B$9$Y$F$N(B $i$ $B$KBP$7(B $\Tr(s_i) \equiv 0 \bmod f_i$
! 407: \end{center}
! 408: \begin{center}
! 409: $\GCD(\Tr(e),f) = 1 \Leftrightarrow$ $B$9$Y$F$N(B $i$ $B$KBP$7(B $\Tr(s_i) \equiv 1 \bmod f_i$
! 410: \end{center}
! 411: $s \in GF(q)$ $B$H$9$k;~(B, $\Tr(s) \equiv 0, 1$ $B$J$k85$O$=$l$>$l(B $q/2$ $B8D(B.
! 412: $B$h$C$F(B, $\GCD(\Tr(e),f) = f$, $\GCD(\Tr(e),f) = 1$ $B$J$k3NN((B
! 413: $B$O$=$l$>$l(B $1/2^k$ $B8D$H$J$k(B. \qed\\
! 414: $B$3$l$i$r$b$H$K(B, $B<!$N$h$&$J%"%k%4%j%:%`$rF@$k(B.
! 415:
! 416: \begin{al}(Cantor-Zassenhaus{\rm\cite{CZ}})
! 417: \begin{tabbing}
! 418: Input : $f(x) \in GF(q)[x]$, $q=p^n$, $f$ $B$OL5J?J}(B\\
! 419: Output: $\{f_1,f_2,\cdots\}$ $f = f_1 f_2 \cdots$ $B$O(B $f$ $B$N4{LsJ,2r(B\\
! 420: $F = \{f\}$\\
! 421: $Q \leftarrow \pi$ $B$N9TNsI=8=(B\\
! 422: $\{e_1 = 1, e_2, \cdots, e_r\} \leftarrow \Ker(Q-I)$ $B$N(B $K$-$B4pDl(B\\
! 423: if ($r = 1$) then return $F$\\
! 424: while\= ($|F| < r$) do \{\\
! 425: \> $g \leftarrow F$ $B$N85(B, \quad $F \leftarrow F \backslash \{g\}$\\
! 426: \> $(c_1,\cdots,c_r) \leftarrow$ $BMp?t%Y%/%H%k(B ($c_i \in GF(q)$)\\
! 427: \> $e \leftarrow \sum c_ie_i$ \\
! 428: \> if \= $p=2$\\
! 429: \>\> $E \leftarrow \Tr(e)$\\
! 430: \>else\\
! 431: \>\> $E \leftarrow e^{(q-1)/2}-1$\\
! 432: \> $h \leftarrow \GCD(g,E)$\\
! 433: \> if $h \neq 1,g$\\
! 434: \>\> $F \leftarrow F \cup \{h,g/h\}$\\
! 435: \}\\
! 436: return F
! 437: \end{tabbing}
! 438: \end{al}
! 439:
! 440: \section{DDF (distinct degree factorization)}
! 441: $BM-8BBN>e$NB?9`<0$KBP$7$F$O(B, GCD $B$N$_$K$h$k(B DDF (distinct degree
! 442: factorization;$B<!?tJL0x;RJ,2r(B) $B$H$h$P$l$kM=HwE*$JJ,2r$,2DG=$G$"$k(B. DDF
! 443: $B$GF@$i$l$k3F0x;R$O(B, $B$=$l$>$lF10l<!?t$N4{Ls0x;R$N@Q$+$i$J$k(B. $B$3$l$K$h$j(B,
! 444: $B3F<!?t$N4{Ls0x;R$,(B 1 $B$D$N>l9g$K$O(B GCD $B$N$_$K$h$j4{Ls0x;R$,F@$i$l$k(B.
! 445: $B$^$?(B, $BJ,2r@.J,$N4{Ls0x;R$,F10l<!?t$G$"$k$3$H$rMxMQ$7$F(B, $BFC<l$J<jK!(B
! 446: $B$K$h$j4{LsJ,2r$r$9$k$3$H$b2DG=$K$J$k(B.
! 447:
! 448: $B7O(B \ref{irred_mod}$B$h$j(B, $B<!$N%"%k%4%j%:%`$,F@$i$l$k(B.
! 449:
! 450: \begin{al}
! 451: \begin{tabbing}
! 452: \\
! 453: Input : $f(x) \in GF(q)[x]$, $f$ $B$OL5J?J}(B\\
! 454: Output : $f(x) = \prod f_i$, $f_i$ $B$O(B $f$ $B$N(B $i$ $B<!4{Ls0x;R$N@Q(B\\
! 455: $w \leftarrow x$,\quad $i \leftarrow 1$\\
! 456: while\= ($i \le \deg(f)/2$) do \{\\
! 457: \> $w \leftarrow w^q \bmod f$\\
! 458: \> $f_i \leftarrow \GCD(f,w-x)$\\
! 459: \> if \= $f_i \neq 1$ \{\\
! 460: \>\> $f \leftarrow f/f_i$\\
! 461: \>\> $w \leftarrow w \bmod f$\\
! 462: \>\> $E \leftarrow e^{(q-1)/2}-1$\\
! 463: \>\}\\
! 464: \}\\
! 465: while ( $i < \deg(f)$ )\\
! 466: \> $f_i \leftarrow 1$\\
! 467: $f_{\deg(f)} \leftarrow f$\\
! 468: return $\prod f_i$
! 469: \end{tabbing}
! 470: \end{al}
! 471: $i$ $B2sL\$K$*$$$F$O(B, $i$ $B$N??$NLs?t$r<!?t$K;}$D0x;R$O4{$K=|$+$l$F(B
! 472: $B$$$k$?$a(B, $i$ $B<!$N0x;R$N$_$,<h$j=P$;$k(B. $B$^$?(B, $i \ge \deg(f)/2$
! 473: $B$H$J$C$?;~E@$G(B, $f$ $B$,4{Ls$J(B $\deg(f)$ $B<!0x;R$G$"$k$3$H$OL@$i$+$G$"$k(B.
! 474:
! 475: $B$3$N%"%k%4%j%:%`$K$*$$$F(B, $w^q \bmod f$ $B$N7W;;$r7+$jJV$9I,MW$,$"$k(B.
! 476: $B$7$+$7(B, $B0lHL$K(B
! 477: $$g = \sum_{i=0}^m a_ix^i \Rightarrow g^q \bmod f = \sum_{i=0}^m a_ix^{iq} \bmod f$$
! 478: $B$h$j(B,
! 479: $w_0 = x^q \bmod f$
! 480: $B$N7W;;7k2L$+$i(B
! 481: $w_i = w_0^i \bmod f = w_{i-1}w_0 \bmod f$
! 482: $B$N7W;;$r(B $i=1,\cdots,\deg(f)-1$ $B$KBP$7$F9T$C$F$*$1$P(B, $w^q \bmod f$ $B$N(B
! 483: $B7W;;$O8zN($h$/7W;;$G$-$k(B.
! 484:
! 485: \section{$B<!?tJL0x;R$NJ,2r(B}
! 486: $f$ $B$OL5J?J}$G(B, $d$ $B<!$N4{Ls0x;R$N@Q$G$"$k$H$9$k(B. $f$ $B$O$b$A$m$s(B Berlekamp
! 487: $B%"%k%4%j%:%`$K$h$j4{LsJ,2r$G$-$k$,(B, $B4^$^$l$k4{Ls0x;R$N<!?t$,A4$FEy$7$$(B
! 488: $B$3$H$rMxMQ$7$FJ,2r$r9T$&$3$H$r9M$($k(B.
! 489:
! 490: \begin{pr}
! 491: $q=p^n$ $B$G(B $p$ $B$,4qAG?t$H$9$k(B. $f=f_1f_2$ $B$G(B$f_1$, $f_2$ $B$,(B $f$ $B$N(B 2
! 492: $B$D$N(B $d$ $B<!4{Ls0x;R$H$9$k(B. $GF(q)$ $B>e$N(B $B9b!9(B $2d-1$ $B<!<0(B $g$ $B$r%i%s%@%`$KA*(B
! 493: $B$V$H$-(B,
! 494: $\GCD(g^{(q^d-1)/2}-1,f)=f_1$ $B$^$?$O(B $f_2$
! 495: $B$H$J$k3NN($O(B $1-1/(2q^d)$.
! 496: \end{pr}
! 497: \proof
! 498: $f_1$, $f_2$ $B$,(B $d$ $B<!4{Ls$h$j(B,
! 499: $$GF(q)[x]/(f_1) \simeq GF(q)[x]/(f_2) \simeq GF(q^d).$$
! 500: $B$h$C$F(B, $BG$0U$N(B $g \in GF(q)[x]$ $B$KBP$7(B,
! 501: $$s_1=(g \bmod f_1)^{(q^d-1)/2} = 0, \pm 1,\quad s_2=(g \bmod f_2)^{(q^d-1)/2} = 0, \pm 1.$$
! 502: $GF(q)$ $B$N85$N$&$A(B $(q^d-1)/2$ $B>h$7$F(B 1 $B$K$J$k$b$N$O(B $(q^d-1)/2$ $B8D(B,
! 503: $B$=$&$G$J$$$b$N$O(B $(q^d+1)/2$ $B8D$"$k(B.
! 504: $\GCD(g^{(q^d-1)/2}-1,f)=f_1$ $B$^$?$O(B $f_2$ $B$H$J$k$N$O(B, $s_1$, $s_2$ $B$N(B
! 505: $B0lJ}$N$_$,(B 1 $B$K$J$k>l9g$G$"$k(B.
! 506: $B$3$3$G(B, $BCf9q>jM>DjM}$K$h$j(B,
! 507: $$GF(q)[x]/(f_1f_2) \simeq GF(q)[x]/(f_1)\bigoplus GF(q)[x]/(f_2)
! 508: \simeq GF(q^d)\bigoplus GF(q^d)$$$B$@$+$i(B, $BG$0U$N(B $(a_1,a_2) \in
! 509: GF(q^d)\bigoplus GF(q^d)$ $B$N85$KBP$7(B, $BB?9`<0$NAH$KBP$7(B, $a_1 = g
! 510: \equiv g \bmod f_1$, $a_2 = g \equiv g \bmod f_2$ $B$J$k(B$2d-1$ $B<!0J2<$N(B
! 511: $BB?9`<0(B $g$ $B$,0l0UE*$KBP1~$9$k(B.
! 512: $B$h$C$F(B, $2d-1$ $B0J2<$NB?9`<0(B $q^{2d}$ $B8D$N$&$A(B,
! 513: $\GCD(g^{(q^d-1)/2}-1,f)=f_1$ $B$^$?$O(B $f_2$ $B$H$J$k$N$O(B,
! 514: $$2(q^d-1)/2\cdot (q^d+1)/2 = (q^{2d}-1)/2$$
! 515: $B8D$G$"$j(B, $B3NN($O(B $1-1/(2q^{2d}).$ \qed
! 516:
! 517: \begin{pr}
! 518: $q=2^n$ $B$H$9$k(B. $f=f_1f_2$ $B$G(B$f_1$, $f_2$ $B$,(B $f$ $B$N(B 2
! 519: $B$D$N(B $d$ $B<!4{Ls0x;R$H$7(B,
! 520: $$\Tr(x) = \sum_{i=0}^{nd-1}x^{2^i}$$
! 521: $B$H$9$k(B. $GF(q)$ $B>e$N(B $B9b!9(B $2d-1$
! 522: $B<!<0(B $g$ $B$r%i%s%@%`$KA*$V$H$-(B,
! 523: $\GCD(\Tr(x),f)=f_1$ $B$^$?$O(B $f_2$
! 524: $B$H$J$k3NN($O(B $1/2$.
! 525: \end{pr}
! 526: \proof
! 527: $f_1$, $f_2$ $B$,(B $d$ $B<!4{Ls$h$j(B,
! 528: $$GF(q)[x]/(f_1) \simeq GF(q)[x]/(f_2) \simeq GF(2^{nd}).$$
! 529: $B$h$C$F(B, $BG$0U$N(B $g \in GF(q)[x]$ $B$KBP$7(B,
! 530: $$s_1=\Tr(g \bmod f_1) = 0,1,\quad s_2=\Tr(g \bmod f_2) = 0,1.$$
! 531: $GF(2^{nd})$ $B$N85$N$&$A(B $\Tr$ $B$NCM$,(B 0, 1 $B$K$J$k$b$N$O(B $B$=$l$>$l(B $2^{nd-1}$ $B8D(B
! 532: $B$:$D$"$k(B. \\
! 533: $\GCD(\Tr(x),f)=f_1$ $B$^$?$O(B $f_2$ $B$H$J$k$N$O(B, $s_1$, $s_2$ $B$N(B
! 534: $B0lJ}$N$_$,(B 0 $B$K$J$k>l9g$G$"$k(B.
! 535: $B$3$3$G(B, $BCf9q>jM>DjM}$K$h$j(B,
! 536: $$GF(q)[x]/(f_1f_2) \simeq GF(q)[x]/(f_1)\bigoplus GF(q)[x]/(f_2)
! 537: \simeq GF(2^{nd})\bigoplus GF(2^{nd})$$$B$@$+$i(B, $BG$0U$N(B $(a_1,a_2) \in
! 538: GF(2^{nd})\bigoplus GF(2^{nd})$ $B$N85$KBP$7(B, $BB?9`<0$NAH$KBP$7(B, $a_1 = g
! 539: \equiv g \bmod f_1$, $a_2 = g \equiv g \bmod f_2$ $B$J$k(B$2d-1$ $B<!0J2<$N(B
! 540: $BB?9`<0(B $g$ $B$,0l0UE*$KBP1~$9$k(B.
! 541: $B$h$C$F(B, $2d-1$ $B0J2<$NB?9`<0(B $2^{2nd}$ $B8D$N$&$A(B,
! 542: $\GCD(\Tr(x),f)=f_1$ $B$^$?$O(B $f_2$ $B$H$J$k$N$O(B,
! 543: $2 \cdot (2^{nd-1})^2 = 2^{2nd-1}$
! 544: $B8D$G$"$j(B, $B3NN($O(B $1/2.$ \qed\\
! 545: $B$3$l$i$NL?Bj$O(B, $B%i%s%@%`$KA*$s$@(B $g$ $B$K$h$j(B, $f$ $B$N(B 2 $B$D$N0x;R$,3NN((B
! 546: 1/2 $B0J>e$GJ,N%$G$-$k$3$H$r0UL#$7$F$$$k(B. $B$3$l$K$h$j(B, $B0J2<$N$h$&$J(B,
! 547: Cantor-Zassenhaus $B%"%k%4%j%:%`$NJQ7AHG$,E,MQ$G$-$k(B.
! 548:
! 549: \begin{al}
! 550: \begin{tabbing}
! 551: \\
! 552: Input : $f(x) \in GF(q)[x]$, $q=p^n$, $f$ $B$OL5J?J}$G(B $d$ $B<!4{Ls0x;R$N@Q(B\\
! 553: Output : $f(x) = \prod f_i$, $f$ $B$N(B $B4{Ls0x;RJ,2r(B\\
! 554: $r \leftarrow \deg(f)/d,\quad F \leftarrow \{f\}$\\
! 555: while\= ($|F| < r$) do \{\\
! 556: \> $h \leftarrow F$ $B$N(B $\deg(h)>d$ $B$J$k85(B,\quad $F \leftarrow F \backslash \{h\}$\\
! 557: \> $g \leftarrow 2d-1$ $B<!$N%i%s%@%`$JB?9`<0(B\\
! 558: \> if \= $p=2$\\
! 559: \>\>$G \leftarrow \sum_{j=0}^{rd-1}g^{2^i}$\\
! 560: \> else\\
! 561: \>\> $G \leftarrow g^{(q^d-1)/2}-1$\\
! 562: \> $z \leftarrow \GCD(h,G)$\\
! 563: \> if $z \neq 1,h$ \\
! 564: \>\> $F \leftarrow F \cup \{z,h/z\}$\\
! 565: \}\\
! 566: return $F$\\
! 567: \end{tabbing}
! 568: \end{al}
! 569:
! 570: \section{$B@0?t78?t0lJQ?tB?9`<0$N0x?tJ,2r(B}
! 571: $B7W;;5!Be?t%7%9%F%`$K$*$$$FMQ$$$i$l$F$$$k0x?tJ,2r%"%k%4%j%:%`$O(B,
! 572: $B2?$i$+$N=`F17?$K$h$jB?9`<0$r$h$j07$$$d$9$$6u4V$K<LA|$7(B, $B$=$N(B
! 573: $B6u4V$G(B, $BB?9`<0$NA|$r0x?tJ,2r$7(B, $B$J$s$i$+$NJ}K!$K$h$j$=$NJ,2r$5$l$?(B
! 574: $BA|$+$i$b$H$N6u4V$K$*$1$k0x;R$r9=@.$9$k(B, $B$H$$$&J}K!$K$h$k$b$N$,B?$$(B.
! 575: $BFC$K(B, $BFsJQ?t0J>e$NB?9`<0$N0x?tJ,2r$O0lJQ?tB?9`<0$K5"Ce$5$l$k$J$I(B,
! 576: $B0lJQ?tB?9`<0$N0x?tJ,2r$O(B, $B0x?tJ,2r%"%k%4%j%:%`$K$*$$$F=EMW$J0LCV$r(B
! 577: $B@j$a$k(B. $B$3$3$G$O(B, $B$b$C$H$bIaDL$KMQ$$$i$l$F$$$k(B Zassenhaus $B$K$h$k(B
! 578: $B%"%k%4%j%:%`$K$D$$$F=R$Y$k(B.
! 579:
! 580: $BL5J?J}$J(B $f \in \Z[x]$ $B$N0x?tJ,2r%"%k%4%j%:%`$O(B, $BM-8BBN>e$N0x?tJ,2r(B,
! 581: Hensel $B9=@.(B, $B;n$73d$j$N;0$D$NItJ,$+$i$J$k(B.
! 582:
! 583: \begin{pr}(Hensel)
! 584: $f \in \Z[x], p \in \N$ $B$OAG?t$G(B,
! 585: $$f \equiv \prod f_{1i} \bmod p,\quad f_{1i} \in GF(p)[x], \quad \deg(f) = \deg(\prod_i f_{1i})$$
! 586: $f_{1i}$ $B$O(B $GF(p)$ $B>e$G8_$$(B
! 587: $B$KAG$H$9$k(B. $B$3$N;~(B, $BG$0U$N(B $k$ $B$KBP$7(B, $f_{ki} \in \Z/(p^k)[x]$ $B$,B8:_(B
! 588: $B$7$F(B,
! 589: $$f \equiv \prod_i f_{ki} \bmod {p^k},\quad f_{1i} \equiv f_{ki} \bmod p, \quad \deg(f_{1i}) = \deg(f_{ki}).$$
! 590: \end{pr}
! 591: \proof
! 592: $k$ $B$K4X$9$k5"G<K!$G<($9(B. $k$ $B$,(B 1 $B$N;~$O@5$7$$(B. $k$ $B$^$G@5$7$$$H$9$k(B.
! 593: $$f_{(k+1)i}=f_{ki}+p^k h_i$$
! 594: $B$J$k7A$r2>Dj$9$k$H(B,
! 595: $$\prod_i f_{(k+1)i} \equiv \prod_i f_{ki} + p^k\sum_i h_i\prod_{j\neq i}f_{kj} \bmod {p^{k+1}}$$
! 596: $B0lJ}(B, $f \equiv \prod_i f_{ki} \bmod {p^k}$ $B$h$j(B,
! 597: $$f = \prod_i f_{ki} + p^k h \bmod {p^{k+1}}$$
! 598: $B$H=q$1$k(B.
! 599: $B$h$C$F(B,
! 600: $$h \equiv \sum_i h_i\prod_{j\neq i}f_{kj} \equiv \sum_i h_i\prod_{j\neq i}f_{1j} \bmod p$$
! 601: $B$H$J$k$h$&$K(B, $h_i \in GF(p)[x], \deg(h_i)\le \deg(f_{1i})$ $B$r7h$a$k$3$H$,$G$-$k$3$H(B
! 602: $B$r<($;$P$h$$(B. $B$3$l$O(B, $BL?Bj(B \ref{exteuc} $B$K$h$j8@$($k(B. \qed
! 603:
! 604: \begin{pr}
! 605: $f \in \Z[x], p \in \N$ $B$OAG?t(B,
! 606: $$f \equiv g_0 h_0 \bmod p, \quad g_0, h_0 \in GF(p)[x],\quad \deg(f) = \deg(g_0 h_0),\quad \GCD(g_0,h_0) = 1$$
! 607: $B$H$9$k(B. $B$3$N;~(B,
! 608: $f \equiv gh \equiv g'h' \bmod {p^k}$ $B$+$D(B $g \equiv g' \equiv g_0 \bmod p,$
! 609: $\deg(g) = \deg(g') = \deg(g_0), \quad \deg(h) = \deg(h') = \deg(h_0),\quad
! 610: \lc(g) \equiv \lc(g') \bmod {p^k}$
! 611: $B$J$i$P(B, $$g \equiv g' \bmod {p^k}, \quad h \equiv h' \bmod {p^k}.$$
! 612: \end{pr}
! 613: \proof
! 614: $k$ $B$K4X$9$k5"G<K!$G<($9(B. $k$ $B$^$G@5$7$$$H$9$k(B. $k+1$ $B$N$H$-(B, $B5"G<K!$N(B
! 615: $B2>Dj$K$h$j(B,
! 616: $$g' - g = p^k r,\quad h' - h = p^k s$$
! 617: $B$H=q$1$k(B. $B0lJ}(B,
! 618: $gh \equiv g'h' \bmod {p^{k+1}}$ $B$+$i(B $r h_0 + s g_0 \equiv 0 \bmod p$
! 619: $B$,@.$jN)$D(B. $B$b$7(B $s \equiv 0 \bmod p$ $B$J$i$P(B $r h_0 \equiv 0 \bmod p$
! 620: $B$h$j(B $k+1$ $B$G@5$7$$(B. $B$b$7(B $s {\not\equiv} 0$ $B$J$i$P(B $g_0 | r$. $B$3$3$G(B,
! 621: $\lc(g) \equiv \lc(g') \bmod {p^{k+1}}$ $B$h$j(B,
! 622: $\deg(r \bmod p) < \deg(g_0).$ $B$h$C$F(B $r \equiv 0 \bmod p$ $B$H$J$j(B,
! 623: $B$3$N>l9g$b(B $k+1$ $B$G@5$7$$(B. \qed
! 624:
! 625: \begin{df}
! 626: $f = \sum_{i=0}^n a_i x^i \in C[x]$
! 627: $B$KBP$7(B, $f$ $B$N%N%k%`(B $\parallel f \parallel_1$, $\parallel f \parallel_2$ $B$r(B
! 628: $B$=$l$>$l(B,
! 629: $$\parallel f \parallel_1 = \sum_{i=0}^n |a_i|, \quad
! 630: \parallel f \parallel_2 = \sqrt{\sum_{i=0}^n |a_i|^2}$$
! 631: ($|a|$ $B$O(B $a$ $B$N@dBPCM(B) $B$GDj5A$9$k(B.
! 632: \end{df}
! 633:
! 634: \begin{pr}(Landau-Mignotte\cite{MIG})
! 635: $f = \sum_{i=0}^n a_i x^i \in \Z[x], g = \sum_{i=0}^m b_i x^i \in \Z[x]$
! 636: $B$H$9$k(B. $B$3$N;~(B $g|f$ $B$J$i$P(B,
! 637: $\parallel g\parallel_1 \le |b_m/a_n|2^m \parallel f\parallel_2$
! 638: \end{pr}
! 639:
! 640: \begin{co}
! 641: \label{mig}
! 642: $f, g \in \Z[x]$, $g|f$ $B$J$i$P(B,
! 643: $\parallel \lc(f)/\lc(g)\cdot g\parallel_1 \le 2^{\deg(g)} \parallel f\parallel_2$
! 644: \end{co}
! 645:
! 646: \begin{pr}
! 647: $f \in \Z[x]$ $B$,L5J?J}$J$i$P(B, $BM-8B8D$NAG?t(B $p$ $B$r=|$$$F(B
! 648: $\deg(f \bmod p) = \deg(f)$ $B$+$D(B $f \bmod p$ $B$OL5J?J}(B.
! 649: \end{pr}
! 650: $B>ZL@$O(B, $f$ $B$NL5J?J}@-$,(B, $f$ $B$H(B $f'$ $B$N=*7k<0$,(B 0 $B$G$J$$$3$H$HF1CM$G(B
! 651: $B$"$k$3$H$+$iL@$i$+(B.\\
! 652: $B0J>e$K$h$j(B $\Z[x]$ $B$K$*$1$k0x?tJ,2r$O<!$N$h$&$K9T$J$o$l$k(B.
! 653:
! 654: \begin{al}(Zassenhaus{\rm \cite{ZASS}})
! 655: \label{zassenhaus}
! 656: \begin{tabbing}
! 657: Input : $f(x) \in \Z[x]$; $f$ $B$OL5J?J}(B\\
! 658: Output : $\{f_1,f_2,\cdots\}$ $f = f_1 f_2 \cdots$ $B$O(B $f$ $B$N4{LsJ,2r(B
! 659: \\
! 660: $p \leftarrow \deg(f) = \deg(f \bmod p)$ $B$+$D(B $f \bmod p$ $B$,L5J?J}$H$J$k$h$&$J(B $p$\\
! 661: $a \leftarrow f$ $B$N<g78?t(B\\
! 662: $F_1\leftarrow f/a \bmod p$ $B$N(B $GF(p)$ $B>e$N%b%K%C%/$J4{Ls0x;RA4BN(B ($BM-8BBN>e$N0x?tJ,2r(B)\\
! 663: if $|F_1| = 1$ then return $\{f\}$\\
! 664: $F_1 = \{ f_{11},\cdots,f_{1m}\}$ $B$H$9$k(B. \\
! 665: $k \leftarrow p^k > \parallel f\parallel_2\cdot 2^{\deg(f)+1}$ $B$J$k@0?t(B\\
! 666: $f \equiv \prod_i f_{1i} \bmod p$ $B$+$i(B $f \equiv \prod_i f_{ki} \bmod {p^k}$ $B$J$k(B $F_k=\{f_{k1},\cdots,f_{km}\} $ $B$r(B\\
! 667: Hensel $B9=@.$G5a$a$k(B\\
! 668: $l \leftarrow 1$\\
! 669: $F \leftarrow \emptyset$\\
! 670: while \= ( $2l \le m$ ) \{\\
! 671: (a)\> $S \leftarrow S \subset F_k$, $|S|=l$ $B$J$k?7$7$$ItJ,=89g(B\\
! 672: \> if \= $S$ $B$,B8:_$7$J$$(B then $l \leftarrow l+1$\\
! 673: \> else \= \{\\
! 674: \>\> $g \leftarrow a\cdots \prod_{s\in S}s$\\
! 675: (b)\>\> $g \leftarrow g$ $B$N3F78?t$K(B $p^k$ $B$N@0?tG\$r2C$($F@dBPCM$,(B $p^k/2$ $B0J2<$H$7$?$b$N(B\\
! 676: \> if $g|af$ \{\\
! 677: \>\> $g\leftarrow \pp(g)$ (primitive part),\quad $f \leftarrow f/g$,\quad
! 678: $F_k \leftarrow F_k \backslash S$\\
! 679: \> \}\\
! 680: \}\\
! 681: if ($f \neq 1$) then $F \leftarrow F \cup \{f\}$\\
! 682: return $F$
! 683: \end{tabbing}
! 684: \end{al}
! 685: \begin{pr}
! 686: $B%"%k%4%j%:%`(B \ref{zassenhaus} $B$O(B $f$ $B$N4{Ls0x;RJ,2r$r=PNO$9$k(B.
! 687: \end{pr}
! 688: \proof
! 689: (a) $B$K$*$$$F(B, $S$ $B$,??$N0x;R(B $G$ $B$NK!(B $p$ $B$G$N0x;R$+$i(B Hensel $B9=@.$K(B
! 690: $B$h$j9=@.$5$l$?K!(B $p^k$ $B$G$N0x;R$H$9$k(B. $B$9$k$H(B, $BK!(B $p^k$ $B$G$N0l0U@-(B
! 691: $B$K$h$j(B, (b) $B$K$*$$$F(B
! 692: $$a/\lc(G)\cdot G \equiv g \bmod p^k.$$
! 693: $B$3$3$G(B, $B7O(B \ref{mig} $B$*$h$S(B $k$ $B$N$H$jJ}$K$h$j(B,
! 694: $$\parallel a/\lc(G)\cdot G\parallel_1 \le 2^{\deg(G)}\parallel f\parallel_2
! 695: \le 2^{\deg(f)}\parallel f\parallel_2 < p^k/2.$$
! 696: $B$^$?(B, $\parallel g \parallel_1\le p^k/2$ $B$h$j(B
! 697: $$\parallel g-a/\lc(G)\cdot G\parallel_1
! 698: \le \parallel g \parallel_1+\parallel a/\lc(G)\cdot G\parallel_1 < 2\cdot p^k/2=p^k.$$
! 699: $B0J>e$K$h$j(B, $a/\lc(G)\cdot G = g$. $B%"%k%4%j%:%`(B \ref{zassenhaus} $B$G$O(B,
! 700: $BK!(B $p$ $B$G$N0x;R$N8D?t$,>.$5$$=g$K;n$7$F$$$k$?$a(B, $B3d$j@Z$l$?;~E@$G(B
! 701: $B4{Ls@-$,@.$jN)$D(B. \qed
! 702:
! 703: $B$3$N%"%k%4%j%:%`$G$O(B,
! 704: \begin{center}
! 705: $g$ $B$,(B $f$ $B$N0x;R$J$i$P(B, $\lc(f)/\lc(g)\cdot g$ $B$O(B $\lc(f)f$ $B$N0x;R(B
! 706: \end{center}
! 707: $B$H$$$&4JC1$J;v<B$,;H$o$l$F$$$k(B. $B$=$7$F(B, $BM=$a8uJd$N<g78?t$r(B $\lc(f)$ $B$K(B
! 708: $B$7$F$*$1$P(B, $B$b$7??$N0x;R$J$i$P(B, $B>e5-$NM}M3$K$h$jI,$:$=$l$O(B $\lc(f)f$ $B$r(B
! 709: $B3d$j@Z$k$N$G$"$k(B.
! 710:
! 711: $B$5$F(B, $B<B:]$K$3$N%"%k%4%j%:%`$r7W;;5!>e$G<B8=$9$k>l9g(B, $B8zN(8~>e$N$?$a(B
! 712: $B$KCm0U$9$kE@$O?tB?$/$"$k(B. $B$=$l$i$N$$$/$D$+$r=R$Y$k(B.
! 713:
! 714: \begin{enumerate}
! 715: \item $p$ $B$NA*Br(B
! 716:
! 717: $f \bmod p$ $B$,L5J?J}$G$5$($"$l$P(B, $B%"%k%4%j%:%`$O?J9T$9$k$,(B, $BM-8BBN>e$G(B
! 718: $B$N0x?tJ,2r$N=PNO$9$k(B $\bmod p$ $B$G$N0x;R$N8D?t$O(B $p$ $B$K$h$j0lHL$K0[$J$k(B.
! 719: $BFC$K(B, $B$"$k(B $p$ $B$KBP$7(B $f \bmod p$ $B$,4{Ls$J$i$P(B $f$ $B<+?H4{Ls$HH=Dj$G$-(B
! 720: $B$k$,(B, $BB>$N(B $f \bmod p$ $B$,4{Ls$G$J$$(B $p$ $B$rA*$V$3$H$K$h$C$FL5BL$J(B
! 721: Hensel $B9=@.$r$9$k>l9g$b$"$k(B. $B$3$N$?$a(B, $BDL>o$O$$$/$D$+$N(B $p$ $B$rA*$s$GM-(B
! 722: $B8BBN>e$G$N0x?tJ,2r$rJ#?t2s5/F0$7(B, $B:G$b0x;R$N8D?t$,>/$J$$(B$p$ $B$rA*$V(B.
! 723:
! 724: \item Hensel $B9=@.(B
! 725:
! 726: $B$3$3$G=R$Y$?(B Hensel $B9=@.$O(B linear lifting $B$H8F$P$l$k$b$N$G(B, $p$ $B$NQQ$,(B
! 727: 1 $B<!$N%*!<%@$G$7$+A}$($J$$(B. $BFC$K(B $p$ $B$,>.$5$$>l9g(B, $BL\E*$NI>2ACM$KE~C#(B
! 728: $B$9$k$N$KB?$/$NCJ?t$rI,MW$H$9$k(B. $B$3$N$?$a(B, $p$ $B$NQQ$r(B 2 $B<!$N%*!<%@$G>e(B
! 729: $B$2$F$$$/(B quadratic lifting $B$H$$$&%"%k%4%j%:%`$,9M0F$5$l$F$$$k(B. $B$?$@$7(B
! 730: $B$3$l$O(B, $\sum_i a_i \prod_{k\neq i}f_k = 1$ $B$K$*$1$k(B $a_i$ $B$bF1;~$K(B
! 731: Hensel $B9=@.$7$J$1$l$P$J$i$J$$$?$a(B, $p^k$ $B$,%^%7%s@0?tDxEY$N$&$A$O(B
! 732: quadratic lifting $B$7(B, $B%^%7%s@0?t$r1[$($?$"$?$j$G(B linear lifting $B$K@ZBX(B
! 733: $B$($k$H$$$&$3$H$,9T$J$o$l$k(B.
! 734:
! 735: \item $B;n$73d$j(B
! 736:
! 737: $B$3$NItJ,$N7W;;NL$O:G0-$G(B $2^{\deg(f)}$ $B$N%*!<%@$H$J$k(B. $B$3$l$O(B, $B0x;R$N8uJd(B
! 738: $B$N$"$i$f$kAH9g$;$r$H$C$F;n$73d$j$r9T$J$C$F$$$k$+$i$G$"$k(B. $B$3$l$rHr$1$k(B
! 739: $BB?9`<0;~4V7W;;NL%"%k%4%j%:%`$O(B Lenstra $BEy$K$h$j(B lattice $B%"%k%4%j%:%`$H(B
! 740: $B$7$FDs0F$5$l$F$$$k$,(B, $B$"$/$^$GA26a7W;;NL$K$*$1$k8zN(2=$G$"$j(B, $B$3$3$G$O(B
! 741: $B=R$Y$J$$(B. $B<B:]$K$O(B, $B$3$N;n$73d$j$,;H$o$l$k$?$a(B, $B0l2s$N;n$73d$j$r>/$7$G(B
! 742: $B$b9bB.$K$9$k$3$H$O=EMW$G$"$k(B. $B$3$l$O(B, $B;n$73d$j$NA0=hM}$H$7$F(B,
! 743: \begin{center}
! 744: $g|f$ $B$J$i$P(B, $B@0?t(B $a$ $B$KBP$7(B $g(a) | f(a)$
! 745: \end{center}
! 746: $B$rMxMQ$7$F(B,
! 747: \begin{itemize}
! 748: \item $BDj?t9`$I$&$7$N;n$73d$j(B ($g|f$ $B$J$i$P(B $g(0) | f(0)$)
! 749: \item $B78?t$NOB$I$&$7$N;n$73d$j(B ($g|f$ $B$J$i$P(B $g(1) | f(1)$)
! 750: \end{itemize}
! 751: $B$J$I$K$h$kA0=hM}$,9M0F$5$l$F$*$j(B, $B$=$l$>$l8z2L$rH/4x$7$F$$$k(B.
! 752: \end{enumerate}
! 753:
! 754:
! 755: \section{$BB?JQ?tB?9`<0$N0x?tJ,2r(B, GCD, $BL5J?J}J,2r(B}
! 756: \subsection{$B0lHL2=$5$l$?(B Hensel $B9=@.(B}
! 757: 2 $BJQ?t0J>e$NB?9`<0(B ($B0J2<(B, $BB?JQ?tB?9`<0$H8F$V(B) $B$N>l9g(B, $B0x?tJ,2r(B, $BL5J?J}(B
! 758: $BJ,2r(B, GCD $B$OJ#;($+$D:F5"E*$K7k$SIU$$$F$$$F(B, $B$=$NA4BNA|$rGD0.$9$k$N$OMF(B
! 759: $B0W$G$O$J$$(B. $BNc$($P(B, $BB?JQ?tB?9`<0(B $f$ $B$NL5J?J}J,2r$O(B, $B86M}E*$K$O(B 1 $BJQ?t(B
! 760: $B$N>l9g$HA4$/F1MM$K7W;;$G$-$k$,(B, $B$"$k<gJQ?t$r8GDj$7$?;~(B, 1 $BJQ?t$N;~$K$O(B
! 761: $BC1$J$k@0?t$G$"$C$?(B $cont(f)$ $B$,(B, $BB?JQ?t$N>l9g$K$O(B 1 $BJQ?t>/$J$$B?9`<0$H(B
! 762: $B$J$j(B, $cont(f)$ $B$NL5J?J}J,2r$,I,MW$H$J$j(B, $B$^$?(B, $cont(f)$ $B<+?H$r5a$a$k(B
! 763: $B:]$K(B, $B$d$O$j(B 1 $BJQ?t>/$J$$B?9`<0$N(B GCD $B$r<B9T$9$kI,MW$,$"$k(B. $B$3$N;v>p$O(B
! 764: $B0x?tJ,2r$K$D$$$F$bF1$8$G$"$k(B. $BB?9`<0$N(B GCD $B$K$D$$$F$O(B Euclid $B$N8_=|K!(B
! 765: $B$*$h$S$=$N2~NIHG$G$"$k(B PRS $BK!$rMQ$$$l$P86M}E*$K2DG=$G$O$"$k$,(B, $B$3$NJ}(B
! 766: $BK!$O(B, GCD $B$,(B 1 $B$N>l9g$K:G$b;~4V$,$+$+$j(B, $B$+$D<B:]$K8=$l$k$[$H$s$I$N>l(B
! 767: $B9g$O(B GCD $B$,(B 1 $B$G$"$k$3$H$r9M$($k$H(B, $B%5%V%"%k%4%j%:%`$H$7$F(B PRS $B$rMQ$$(B
! 768: $B$k$3$H$OHr$1$?$$(B. $B$3$l$KBe$o$k$b$N$H$7$F(B, $B0lHL2=$5$l$?(B Hensel $B9=@.$,$"(B
! 769: $B$k(B. $B$3$NJ}K!$O(B, 1 $BJQ?tB?9`<0$N0x?tJ,2r$HF1MM(B, $B$"$k=`F17?$K$h$kA|$+$i0x(B
! 770: $B;R$N(B $B!V%?%M!W$r5a$a(B, $B$=$l$+$i(B Hensel $B9=@.$K$h$j0x;R$N8uJd$r5a$a$k$b$N(B
! 771: $B$G$"$k(B. $B$7$+$b(B, $B$3$NJ}K!$O(B, $B!V%?%M!W$r5a$a$5$($9$l$P$=$N8e$N7W;;$O(B
! 772: $BF10l$G$"$k$?$a(B, $B0x?tJ,2r$K8B$i$:(B, GCD, $BL5J?J}J,2r$K$b1~MQ$G$-$k(B.
! 773:
! 774: $B0J2<$G$O(B,
! 775: $$R = \Z[x_1,\cdots,x_n],\quad I = (x_2-a_2,\cdots,x_n-a_n)$$
! 776: ($x_i-a_i$$B$G@8@.$5$l$k(B $R$ $B$N%$%G%"%k(B) $B$H$9$k(B. $I$ $B$KBP$7(B
! 777: $\phi_I : R \rightarrow \Z[x_1]$ $B$r(B
! 778: $$\phi_I(f) = f(x_1,a_2,\cdots,a_n)$$
! 779: $B$GDj5A$9$k(B. $f \in R$ $B$KBP$7(B, $\lc(f)$ $B$O(B, $x_1$ $B$r<gJQ?t$H$_$?;~$N(B
! 780: $B<g78?t$rI=$9$H$9$k(B.
! 781:
! 782: \begin{pr}(Moses-Yun{\rm\cite{YUN}})
! 783: \label{yun}
! 784: $f \in R, p \in \Z$ $B$OAG?t(B,
! 785: $$f \equiv \prod_i f_{1i} \bmod {(p^l,I)},\quad f_{1i} \in \Z_{p^l}[x_1],\quad \deg(f) = \sum_i \deg(f_{1i})$$
! 786: $f_{1i}$ $B$O(B GF(p) $B>e8_$$$KAG(B, $\phi_I(\lc(f)) \neq 0 \bmod p$ $B$H$9$k(B. $B$3$N;~(B, $BG$0U(B
! 787: $B$N(B $k$ $B$KBP$7(B, $f_{ki} \in \Z_{p^l}[x_1,\cdots,x_n]$ $B$,B8:_$7$F(B,
! 788: $f \equiv \prod f_{ki} \bmod {(p^l,I^k)}$ $B$+$D(B $f_{ki} \equiv f_{1i} \bmod
! 789: {(p^l,I)},\quad \deg(f_{ki}) = \deg(f_{1i}).$
! 790: \end{pr}
! 791: \proof
! 792: $k$ $B$K4X$9$k5"G<K!$G<($9(B. $k$ $B$,(B 1 $B$N;~$O@5$7$$(B. $k$ $B$^$G@5$7$$$H$9$k(B.
! 793: $$f_{(k+1)i}=f_{ki}+h_i\quad (h_i \in (p^l,I^k))$$
! 794: $B$J$k7A$r2>Dj$9$k$H(B,
! 795: $$\prod_i f_{(k+1)i} \equiv \prod_i f_{ki} + \sum_i h_i\prod_{j\neq i}f_{kj}
! 796: \bmod {(p^l,I^{k+1})}$$
! 797: $B0lJ}(B, $f \equiv \prod_i f_{ki} \bmod {(p^l,I^k)}$ $B$h$j(B,
! 798: $$f = \prod_i f_{ki} + h\quad (h \in (p^l,I^k))$$
! 799: $B$H=q$1$k(B. $B$h$C$F(B,
! 800: $$h \equiv \sum_i h_i\prod_{j\neq i}f_{kj} \equiv \sum_i h_i\prod_{j\neq i}f_{1j} \bmod {(p^l,I^{k+1})}$$
! 801: $B$H$J$k$h$&$K(B,
! 802: $h_i \in (p^l,I^k), \deg(h_i)\le \deg(f_{1i})$ $B$r7h$a$k$3$H$,$G$-$k$3$H(B
! 803: $B$r<($;$P$h$$(B. \\
! 804: $$h = \sum_{\alpha}h_{\alpha}(x_1)\prod_{j\ge 2}(x_j-a_j)^{\alpha_j} \bmod {I^{k+1}}$$
! 805: $$h_i = \sum_{\alpha}h_{i \alpha}(x_1)\prod_{j\ge 2}(x_j-a_j)^{\alpha_j} \bmod {I^{k+1}}$$
! 806: $B$H=q$/$H(B, $B3F78?t$KBP$7$F(B\\
! 807: $$h_{\alpha} \equiv \sum_i h_{i \alpha}\prod_{j\neq i}f_{1j} \bmod {p^l}$$
! 808: $B$H$J$k$h$&$K(B $h_{i \alpha}$ $B$rA*$Y$l$P$h$$$,(B, $B$3$l$O(B, $B<!$NL?Bj$K$h$j<!?t$N(B
! 809: $B>r7o$r9~$a$F2DG=$G$"$k(B. \qed
! 810:
! 811: \begin{pr}
! 812: $f_i \in \Z[x]$, $p$ $B$OAG?t(B, $p {\not|}\lc(f_i)$, $f_i
! 813: \bmod p$ $B$O8_$$$KAG$H$9$k(B. $B$3$N;~(B, $BG$0U$N(B $k$, $BG$0U(B
! 814: $B$N(B $c \in \Z[x]$$B$KBP$7(B, $c_i \in \Z[x]$ $B$,B8:_$7$F(B,
! 815: $$\sum_i c_i \prod_{j\neq i}f_j \equiv c \bmod {p^k},\quad \deg(c_i) < \deg(f_i) (i \ge 2).$$ $B$5$i$K(B, $\deg(c) < \sum_i \deg(f_i)$ $B$J$i$P(B, $\deg(c_1) < \deg(f_1)$
! 816: $B$+$D(B, $B$3$N$h$&$J(B $c_i$ $B$O(B $p^k$ $B$rK!$H$7$F0l0UE*(B.
! 817: \end{pr}
! 818: \proof
! 819: $\bmod p$ $B$K$*$1$k>r7o$+$i(B, $e_{1i} \in GF(p)[x]$ $B$,B8:_$7$F(B,
! 820: $\sum_i e_{1i} f_i \equiv 1 \bmod p.$
! 821: $B$3$l$r:F5"E*$KMQ$$$k$H(B, $BG$0U$N(B $k$ $B$KBP$7$F(B $e_{ki} \in \Z_{p^k}[x]$ $B$,B8:_$7$F(B
! 822: $\sum_i e_{ki} f_i \equiv 1 \bmod {p^k}.$
! 823: $B3F(B $f_i$ $B$N<g78?t$,(B $p$ $B$G3d$j@Z$l$J$$$3$H$+$i(B, $p^k$ $B$rK!$H$9(B
! 824: $B$kB?9`<0=|;;$,2DG=$H$J$k$+$i(B, $B$3$N<0$NN>JU$K(B $c$ $B$r3]$1$F(B, $i \ge 2$
! 825: $B$KBP$7(B, $c\cdot e_{ki}$ $B$r(B $f_i$ $B$G3d$C$?M>$j$r(B $c_i$ $B$H$7(B, $B;D$j$r(B
! 826: $\prod_{j\neq 1}f_j$ $B$N78?t$K$^$H$a$l$P$h$$(B. $B$3$3$G(B, $\deg(c) < \sum_i
! 827: \deg(f_i)$$B$J$i$P(B, $\deg(c_1)+\sum_{j\neq 1}\deg(f_i) < \sum_i \deg(f_i)$
! 828: $B$h$j(B$\deg(c_1) < \deg(f_1)$ $B$G(B, $B0l0U@-$O(B, $k = 1$ $B$K$*$1$k0l0U@-$+$i5"G<(B
! 829: $BK!$G>ZL@$G$-$k(B. \qed
! 830:
! 831: \begin{pr}
! 832: {\rm $BL?Bj(B \ref{yun}} $B$K$*$$$F(B, $B<g78?t$,(B $(p^l,I^k)$ $B$rK!$H$7$FEy$7$$(B
! 833: $f_{ki}$ $B$O(B $(p^l,I^k)$ $B$rK!$H$7$F0l0UE*$G$"$k(B.
! 834: \end{pr}
! 835: $B>ZL@$O(B, $BA0Fs$D$NL?Bj$rMQ$$$l$P(B, $B0lJQ?t$N>l9g$HF1MM$K$G$-$k(B.
! 836:
! 837: \begin{pr}(Gel'fond{\rm\cite{GEL}})
! 838: $f \in \C[x_1,\cdots,x_n]$ $B$KBP$7(B, $B3FJQ?t$KBP$9$k<!?t$r(B $d_i$ $B$H$9$k$H(B
! 839: $|f$ $B$N0x;R$N78?t(B$|$ $\le e^{d_1+\cdots+d_n}\cdot \max$($|f$ $B$N78?t(B$|$).
! 840: \end{pr}
! 841:
! 842: \begin{pr}
! 843: $f \in R$ $B$,L5J?J}$J$i$P(B, $BL58B$KB?$/$N(B $I$ $B$KBP$7(B
! 844: $\lc(\phi_I(f)) \neq 0$ $B$+$D(B $\phi_I(f)$ $B$OL5J?J}(B.
! 845: \end{pr}
! 846: $B>ZL@$O(B, $f$ $B$NL5J?J}@-$,(B, $f$ $B$H(B $f'$ $B$N(B $x_1$ $B$K4X$9$k=*7k<0$,(B 0 $B$G$J(B
! 847: $B$$$3$H$HF1CM$G$"$k$3$H$+$iL@$i$+(B.
! 848:
! 849: \subsection{$BB?JQ?tB?9`<0$N0x?tJ,2r(B}
! 850: $B0J>e$K$h$j(B, $R$ $B$K$*$1$k0x?tJ,2r$O<!$N$h$&$K9T$J$o$l$k(B.
! 851:
! 852: \begin{al}
! 853: \begin{tabbing}
! 854: \\
! 855: Input : $f(x) \in R$; $f$ $B$OL5J?J}$+$D(B $x_1$ $B$K$D$$$F86;OE*(B\\
! 856: Output : $\{f_1,f_2,\cdots\}$ $f = f_1 f_2 \cdots$ $B$O(B $f$ $B$N4{LsJ,2r(B\\
! 857: $a \leftarrow \deg(f) = \deg(f_a(x_1))$ $B$+$D(B $f_a(x_1)=f(x_1,a_2,\cdots,a_n)$ $B$,(B
! 858: $BL5J?J}$J(B\\
! 859: $a=(a_2,\cdots,a_n) \in \Z^{n-1}$\\
! 860: $F_1 \leftarrow \{f_{1i}\} \leftarrow f_a(x_1)$ $B$N(B $\Z$ $B>e$G$N4{LsJ,2r(B\\
! 861: if $|F_1| = 1$ then return $\{f\}$\\
! 862: $p \leftarrow f_a(x_1)$ $B$N4{LsJ,2r$GMQ$$$?(B $p$\\
! 863: $F_1 = \{f_{11},\cdots,f_{1m}\}$ $B$H$9$k(B\\
! 864:
! 865: $l \leftarrow 1$\\
! 866: $F \leftarrow \emptyset$\\
! 867: while \= ( $2l \le m$ ) \{\\
! 868: \> $S \leftarrow S \subset F_1$, $|S|=l$ $B$J$k?7$7$$ItJ,=89g(B\\
! 869: \> if \= $S$ $B$,B8:_$7$J$$(B then $l \leftarrow l+1$\\
! 870: \> else \= \{\\
! 871: \>\> $g_1 \leftarrow \prod_{s\in S}s$,\quad $h_1 \leftarrow \prod_{s\in F_1 \backslash S}s$\\
! 872: \>\> $g_1 \leftarrow \lc(f_a)/\lc(g_1)\cdot g_1$,\quad $\lc(g_1) \leftarrow \lc(f)$\\
! 873: \>\> $h_1 \leftarrow \lc(f_a)/\lc(h_1)\cdot h_1$,\quad $\lc(h_1) \leftarrow \lc(f)$\\
! 874: \>\> $B \leftarrow \lc(f)f$ $B$N(B Gel'fond bound\\
! 875: \>\> $l \leftarrow p^l > 2B$ $B$J$k@0?t(B $l$\\
! 876: \>\> $k \leftarrow f$ $B$N(B $x_2,\cdots,x_n$ $B$K4X$9$kA4<!?t(B $+1$\\
! 877: \>\> $\lc(f)f_a = g_1 h_1 \bmod {I}$ $B$+$i(B $\lc(f)f = g_k h_k \bmod {p^l,I^k}$ $B$J$k(B $g_k, h_k$ $B$r(B\\
! 878: \>\> Hensel $B9=@.$G5a$a$k(B.\\
! 879: \>\> $g \leftarrow g$ $B$N3F78?t$K(B $p^l$ $B$N@0?tG\$r2C$($F@dBPCM$,(B $p^l/2$ $B0J2<$H$7$?$b$N(B\\
! 880: \>\> if\= $g|\lc(f)f$ \{\\
! 881: \>\>\> $g\leftarrow \pp(g)$ (primitive part),\quad $f \leftarrow f/g$,\quad
! 882: $F_1 \leftarrow F_1 \backslash S$\\
! 883: \>\> \}\\
! 884: \> \}\\
! 885: \}\\
! 886: if ($f \neq 1$) then $F \leftarrow F \cup \{f\}$\\
! 887: return $F$
! 888: \end{tabbing}
! 889: \end{al}
! 890:
! 891: $B$3$N%"%k%4%j%:%`$r<B8=$9$k>l9g(B, $B0lJQ?t$N>l9g$H$O0[$J$kLdBj$,$$$/$D$+@8$:$k(B.
! 892:
! 893: \begin{enumerate}
! 894: \item {\bf $BHsNmBeF~LdBj(B}
! 895:
! 896: Hensel $B9=@.$N<j=g$r8+$k$H(B, $x_i-a_i$ $B$K4X$9$kF1<!@.J,$r<h$j=P$9A`:n$,(B
! 897: $BI,MW$K$J$k$3$H$,$o$+$k(B. $a_i$ $B$,A4$F(B 0 $B$J$i$P(B, $B:F5"I=8=$5$l$?B?9`<0$N(B
! 898: $B$$$/$D$+$N9`$N<h$j=P$7$K2a$.$J$$$,(B, 0 $B$G$J$$(B $a_i$ $B$,$"$k>l9g(B, $B$"$i$+$8$a(B
! 899: $BJ?9T0\F0$K$h$j(B $a_i$ $B$r(B 0 $B$H$9$k$+(B, $BHyJ,(B, $BBeF~$NA`:n$rMQ$$$F(B, $BI,MW$J(B
! 900: $B78?t$r7W;;$9$kI,MW$,$"$k(B. $B85$NB?9`<0$,AB$G$bJ?9T0\F0$r9T$J$&$HL)$JB?9`<0(B
! 901: $B$H$J$k$?$a(B, $a_i$ $B$N$&$A(B 0 $B$r$J$k$Y$/B?$/A*$S$?$$$,(B, $a_i$ $B$KBP$9$k(B
! 902: $B>r7o$rK~$?$9$?$a$K$d$`$J$/(B 0 $B$G$J$$(B $a_i$ $B$rMQ$$$k$3$H$,$"$jF@$k(B.
! 903: \item {\bf $B<g78?tLdBj(B}
! 904:
! 905: $B<g78?t$,(B 1 $B$G$J$$>l9g$r07$($k$h$&(B, 1 $BJQ?t$N>l9g$HF1MM$K(B, $B0x;R$N8uJd$N(B
! 906: $B<g78?t$rM?$($i$l$?B?9`<0$N<g78?t$HEy$7$/$7$F$"$k(B. $B$3$l$K$h$j(B, Hensel
! 907: $B9=@.$N:]$K(B, $BITI,MW$J9`$NA}2C$r2!$($i$l$k$,(B, $B<g78?t$,Bg$-$JB?9`<0$N>l9g(B
! 908: $BI,MW$J(B Hensel $B9=@.$NCJ?t$NA}2C$r>7$/(B. $B$3$N$?$a(B, $B$"$i$+$8$a0x;R$N8uJd$K(B
! 909: $BBP1~$9$k<g78?t$r2?$i$+$NJ}K!$K$h$j7h$a$F$7$^$&J}K!$,(B Wang \cite{WANG} $B$K(B
! 910: $B$h$jDs0F$5$l$F$$$k(B.
! 911: \item {\bf $B%K%;0x;R$NLdBj(B}
! 912:
! 913: $B$3$3$G=R$Y$?%"%k%4%j%:%`$K$*$$$F$O(B, 2 $B$D$N0x;R$r(B Hensel $B9=@.$9$k$H$$$&(B
! 914: $B<j=g$K$7$F$"$k(B. $B$3$l$O(B,
! 915: \begin{itemize}
! 916: \item $BB?$/$N0x;R$rF1;~$K(B Hensel $B9=@.$9$k>l9g(B, $B<g78?t$r%b%K%C%/$N$^$^(B
! 917: $B9T$J$&$3$H$O(B, $BITI,MW$J9`$NA}2C$r>7$-(B, $BA4$F$N0x;R$N<g78?t$rM?$($i$l$?(B
! 918: $BB?9`<0$N<g78?t$K9g$o$;$k$3$H$O(B, Hensel $B9=@.$NCJ?t$NA}2C$K$D$J$,$k(B.
! 919: \item $B8uJd$,??$N0x;R$N%$%a!<%8$G$"$k$3$H$r4|BT$7$F$$$k(B. $B??$N0x;R$N(B
! 920: $B>l9g(B, $B<!?t$NI>2A$GF@$i$l$kCJ?t$h$jA0$K8uJd$,0BDj$9$k$N$G(B, $B$=$N;~E@(B
! 921: $B$G;n$73d$j$r$7$F(B Hensel $B9=@.$r@Z$j>e$2$k$3$H$b$G$-$k(B.
! 922: \end{itemize}
! 923: $B$J$I$NM}M3$K$h$k(B. $B%K%;0x;R$K$h$j(B Hensel $B9=@.$r9T$J$C$?>l9g(B, $BI>2A$G(B
! 924: $BF@$i$l$kCJ?t$^$G(B Hensel $B9=@.$,?J9T$7(B, $B5pBg$J8uJd$r@8@.$7$F$7$^$&(B.
! 925: $B$3$l$O(B, $BBg$-$JL5BL$H$J$k$?$a(B, $B3FJQ?t$N<!?t$r>o$K%A%'%C%/$7$F(B,
! 926: $B8uJd$N$I$l$+$NJQ?t$K4X$9$k<!?t$,M?$($i$l$?B?9`<0$N<!?t$r1[$($?;~E@$G(B
! 927: Hensel $B9=@.$rCfCG$9$k$J$I$NA`:n$,I,MW$H$J$k(B.
! 928: \end{enumerate}
! 929: $B$3$3$G=R$Y$?J}K!$O(B, EZ $BK!$H8F$P$l(B, $n$ $BJQ?t$r(B $B0lJQ?t$KMn$7$F8uJd$r7W;;(B
! 930: $B$9$k$b$N$G$"$C$?(B. $B$7$+$7(B, $B0lEY$K0lJQ?t$KMn$9$3$H$OHsNmBeF~LdBj$d(B, $B%K%;(B
! 931: $B0x;R$N=P8=$N3NN($rBg$-$9$k(B. $B$3$N$?$a(B, $BJQ?t$N8D?t$r0l$D$:$DMn$7$F$$$/(B
! 932: EEZ$BK!(B \cite{WANG} $B$,9M0F$5$l$?(B. $B$3$NJ}K!$K$h$l$P(B, $BHsNmBeF~LdBj$b(B, $B0lJQ(B
! 933: $B?t$:$D$KBP$9$k$b$N$K$J$k$?$a9`$N?t$,;X?tE*$KA}2C$9$k$3$H$O$J$/(B, $BJQ?t$r(B
! 934: $B0l$DA}$d$7$F(B Hensel $B9=@.$r9T$J$&:](B, $B%K%;0x;R$O<!Bh$KGS=|$5$l$F$$$/$?$a(B,
! 935: $B%K%;0x;R$KBP$7$F6/$$%"%k%4%j%:%`$H$J$k(B.
! 936:
! 937: \subsection{$BB?JQ?tB?9`<0$NL5J?J}J,2r5Z$S(B GCD}
! 938: \label{wangtrager}
! 939: $B0lHL2=$5$l$?(B Hensel $B9=@.$O(B, $BB?JQ?tB?9`<0$NL5J?J}J,2r(B, GCD $B$K$b1~MQ$G$-(B
! 940: $B$k(B. $B$3$N$H$-LdBj$H$J$k$N$O(B, Hensel $B9=@.$N=PH/E@$H$J$k0x;R(B ($BL?Bj(B
! 941: \ref{yun} $B$N(B$f_{1i}$) $B$,(B, $BK!(B $p$ $B$G8_$$$KAG$G$"$k$H$$$&>r7o$G$"$k(B.
! 942: $\GCD(g,h)$ $B$N7W;;$K$*$$$F$O(B, $f_{1i}$ $B$H$7$F(B
! 943: $$\{\GCD(\phi_I(g),\phi_I(h)),\phi_I(g)/\GCD(\phi_I(g),\phi_I(h))\}$$
! 944: $B$r$H$l$l$P<+A3$G$"$k$,(B, $B0lHL$K$3$l$i$,K!(B $p$ $B$G8_$$$KAG$G$"$k$3$H$O4|BT$G(B
! 945: $B$-$J$$(B. $B$7$+$7(B, $g$ $B$N4{Ls0x;R$rA4$F4^$`L5J?J}0x;R(B $g_s = g/\GCD(g,g')$
! 946: $B$r5a$a$k:]$KI,MW$J(B $g_1=\GCD(g,g')$ $B$O(B,
! 947: $$\GCD(g_1,g'/g_1) = 1$$$B$h$j(B, $g'$ $B$N0x;R$H$7$F(B, $B0lHL2=$5$l$?(B Hensel $B9=(B
! 948: $B@.$G7W;;$G$"$k(B. $B$^$?(B, $B0lHL$K(B, $g$ $B$,(B $BL5J?J}$J$i$P2DG=$G$"$k(B. $B$h$C$F(B
! 949: $\GCD(g_s,h)$ $B$O(B $B0lHL2=$5$l$?(B Hensel $B9=@.$G7W;;$G$-(B, $\GCD(g,h)$ $B$N4{Ls(B
! 950: $B0x;R$rA4$F4^$`L5J?J}$JB?9`<0$H$J$j(B, $B$3$l$rMQ$$$F(B $\GCD(g,h)$ $B$r5a$a$k$3(B
! 951: $B$H$,$G$-$k(B. $B$^$?(B, $g_s$ $B$5$(5a$^$l$P(B, $g$ $B$NL5J?J}J,2r<+?H$b0lHL2=$5(B
! 952: $B$l$?(B Hensel $B9=@.$G5a$a$k$3$H$,$G$-$k(B.
! 953:
! 954: $B$7$+$7(B, $BL5J?J}J,2r$K$*$$$F(B, $g$ $B$,=EJ#EY$NBg$-$$0x;R$r4^$s$G$$$k$H$-(B,
! 955: $g_s$ $B$N7W;;$KB?$/$N;~4V$,$+$+$k(B. $B$3$l$rHr$1$k$?$a(B, $B=EJ#EY$N:G$b9b$$(B
! 956: $B0x;R$+$i5a$a$F$$$/J}K!$,9M0F$5$l$?(B. $B$3$l$O(B, $B<!$NL?Bj$K4p$E$/(B.
! 957:
! 958: \begin{pr}
! 959: $f \in K[x]$ $B$KBP$7(B,
! 960: $f = hg^e \quad (h,g \in K[x]),\quad \GCD(h,g)=1$ $B$+$D(B $g$ $B$,L5J?J}(B
! 961: $B$J$i$P(B $g|(d/dx)^{e-1}f$ $B$G(B
! 962: $$\GCD(g,((d/dx)^{e-1}f)/g) = 1$$
! 963: \end{pr}
! 964: \proof
! 965: $e = 1$ $B$N$H$-L@$i$+(B. $e\ge 2$ $B$N$H$-(B,
! 966: $(d/dx)^{e-1}(g^e) \equiv e!gg'^{e-1} \bmod{g^2}$
! 967: $B$,$$$($k(B. $B$h$C$F(B,
! 968: $(d/dx)^{e-1}f \equiv h(d/dx)^{e-1}(g^e) \equiv e!hgg'^{e-1} \bmod{g^2}$
! 969: $B$H$J$j(B, $g|(d/dx)^{e-1}f$. $B$5$i$K(B,
! 970: $((d/dx)^{e-1}f)/g \equiv e!hg'^{e-1} \bmod{g}$
! 971: $B$G(B, $\GCD(g,h) = 1$, $\GCD(g,g')=1$ $B$h$j(B
! 972: $\GCD(g,((d/dx)^{e-1}f)/g) = 1.$ \qed
! 973:
! 974: \cite{SQFR} $B$N%"%k%4%j%:%`$O(B, $BB?JQ?t$N>l9g(B, $B$^$:(B, $BBeF~$K$h$j0lJQ?t$KMn$7$?(B
! 975: $BB?9`<0$rL5J?J}J,2r$9$k(B. $BF@$i$l$?L5J?J}J,2r$N(B, $B=EJ#EY$N:G$b9b$$0x;R(B $g_0$ $B$H(B,
! 976: $f$ $B$N(B $e-1$ $B2sHyJ,$+$i(B, $B0lHL2=$5$l$?(B Hensel $B9=@.$K$h$j(B $f$ $B$N(B, $B=EJ#EY(B
! 977: $B$N:G$b9b$$0x;R(B $g$ $B$rI|85$9$k$N$G$"$k(B. $B$=$7$F(B, $B$3$N(B Hensel $B9=@.$,<:GT$7$?(B
! 978: $B>l9g$K$O(B, $BBeF~$7$?CM$,BEEv$J$b$N$G$O$J$+$C$?$H$7$F(B, $BCM$r<h$jD>$9(B.
! 979: $BBEEv$JCM$,B8:_$9$k$3$H$O(B, $BL5J?J}$JB?JQ?tB?9`<0$KBP$9$kBEEv$JBeF~CM$NB8:_(B
! 980: $B$HF1MM$K8@$($k(B.
! 981: $B$3$NJ}K!$N$h$$E@$O(B,
! 982: \begin{itemize}
! 983: \item
! 984: ($B=EJ#EY(B -1) $B$@$1B?9`<0$N<!?t$,Mn$;$k(B
! 985: \item
! 986: $BL5J?J}0x;R$rD>@\5a$a$k$3$H$,$G$-$k$?$a(B, $f$ $B$N4{Ls0x;R$9$Y$F$N@Q$r5a(B
! 987: $B$a$k>l9g$KHf3S$7$F7W;;$N<j4V$r8:$i$9$3$H$,$G$-$k(B
! 988: \item
! 989: $BA4BN$KBP$7$FBEEv$G$J$$BeF~$G$b(B, $B=EJ#EY:GBg$N0x;R$K$O1F6A$,$J$$>l9g$,$"$k(B.
! 990: \item
! 991: $B$"$kB?9`<0$NQQ$K$J$C$F$$$k>l9g$K9bB.$KJ,2r$G$-$k(B.
! 992: \end{itemize}
! 993: $B$J$I$,$"$k(B. $B$5$i$K(B, $B$3$NJ}K!$O(B, $B0lJQ?tB?9`<0$NL5J?J}J,2r$K$b1~MQ$G$-$k(B.
! 994: $B$9$J$o$A(B, $B0lJQ?tB?9`<0$KBP$7$F$O(B, $BK!(B $p$ $B$G$NL5J?J}J,2r$rMQ$$$F@0?t>e(B
! 995: $B$NL5J?J}0x;R$r(B, $B=EJ#EY:GBg$N0x;R$+$iI|85$7$F$$$/(B. $B$3$N:](B, $BI|85J}K!$H$7$F(B
! 996: $B$O(B, \cite{SQFR} $B$G$OCf9q>jM>DjM}$K$h$kJ}K!$rDs0F$7$F$$$k$,(B, Hensel $B9=@.(B
! 997: $B$K$h$k$b$N$b2DG=$G$"$k(B.
! 998:
! 999: $B0J>e(B, $B0lHL2=$5$l$?(B Hensel $B9=@.$N1~MQ$K$D$$$F=R$Y$?$,(B, $B$3$l$i$r7W;;5!>e(B
! 1000: $B$K%$%s%W%j%a%s%H$9$k$3$H$O$+$J$j$NBg;E;v$H$J$k(B. $B$3$l$O(B, $B:G=i$K=R$Y$?$h$&(B
! 1001: $B$K(B, $B0x?tJ,2r(B, GCD, $BL5J?J}J,2r$,:F5"E*$K7k9g$7(B, $B$+$D$=$l$i$OMM!9$KIUBS>u67(B
! 1002: $B$N0[$J$k(B Hensel $B9=@.$K$h$j7W;;$5$l$J$1$l$P$J$i$J$$(B. $B$5$i$K(B, $B$3$l$i$r(B
! 1003: $B8zN($h$/7W;;$9$k$?$a$N<o!9$N9)IW$rF~$l$l$P(B, $B%W%m%0%i%`$OAjEv$KBg$-$J$b$N(B
! 1004: $B$H$J$j(B, $BEvA3(B debug $B$b:$Fq$J$b$N$K$J$k(B.
! 1005:
! 1006: \section{$BBe?tBN>e$N0x?tJ,2r(B}
! 1007: $B$3$N@a$G$O(B, $K$ $B$r(B $Q$ $B$NM-8B<!3HBgBN$H$7(B, $K[x]$ $B$K$*$1$k0x?tJ,2r$r9M(B
! 1008: $B$($k(B. $B$3$3$G=R$Y$k$N$O(B, Trager \cite{TRAGER} $B$K$h$k(B, $B%N%k%`$rMQ$$$kJ}(B
! 1009: $BK!$G$"$k(B. $K=\Q(\alpha)$ $B$H$$$&C13HBg$KBP$7$F$O(B, $B$3$NB>$K(B, Hensel $B9=@.(B
! 1010: $B$rMQ$$$kJ}K!$,$$$/$D$+Ds0F$5$l$F$$$k$,$3$3$G$O=R$Y$J$$(B. Trager $B$NJ}K!(B
! 1011: $B$O(B, $K(\alpha)$ $B>e$G$N0x?tJ,2r$r(B, $K$ $B>e$N0x?tJ,2r$K5"Ce$5$;$k$b$N$G(B,
! 1012: $\Q$ $B>e$N0x?tJ,2r$5$(40Hw$7$F$$$l$P(B, $K=\Q(\alpha_1,\cdots,\alpha_r)$ $B>e(B
! 1013: $B$G$N0x?tJ,2r$,2DG=$K$J$k(B.
! 1014:
! 1015: $B0J2<(B, $K$ $B$r(B, $B$=$N>e$GB?9`<00x?tJ,2r$,2DG=$JBN(B, $g \in K[t]$ $B$r(B $\deg(g) = m$
! 1016: $B$J$k4{LsB?9`<0(B, $\alpha$ $B$r(B $g$ $B$N0l$D$N:,$H$9$k(B.
! 1017: $K(\alpha)=K[\alpha]=K[t]/(g)$ $B$G$"$k(B. $L\supset K$ $B$r(B $g$ $B$N:G>.J,2r(B
! 1018: $BBN$H$9$k(B. $\alpha_1=\alpha,\alpha_2,\cdots,\alpha_m$ $B$r(B $g$ $B$NAj0[$J$k(B
! 1019: $B:,$H$9$k$H(B, $L=K(\alpha_1,\cdots,\alpha_m)$ $B$H$+$1$k(B.
! 1020:
! 1021: \begin{df}
! 1022: $f\in K(\alpha)[x]$ $B$KBP$7(B, $\Norm(f)$ $B$r(B
! 1023: $$\Norm(f) = \prod_i f(x,\alpha_i)$$
! 1024: $B$GDj5A$9$k(B. $L/K$ $B$N(B $\Norm$ $B$N@-<A(B
! 1025: $B$K$h$j(B, $\Norm(f) \in K[x]$. $B$^$?(B, $$\Norm(f) = \res_t(f(x,t),g(t)).$$
! 1026: \end{df}
! 1027:
! 1028: \begin{pr}
! 1029: $f\in K(\alpha)[x]$ $B$,4{Ls$J$i$P(B, $B$"$k4{LsB?9`<0(B $h \in K[x]$
! 1030: $B$,B8:_$7$F(B, $$\Norm(f) = h^l.$$
! 1031: \end{pr}
! 1032: \proof
! 1033: $\Norm(f) = ab,\quad a,b \in K[x],\quad \GCD(a,b)=1$ $B$H=q$1$?$H$9$k(B. $f
! 1034: | \Norm(f)$ $B$G(B, $f$ $B$O(B $K(\alpha)$ $B>e4{Ls$h$j(B, $f|a$ $B$H$7$F$h$$(B. $B$3$N(B
! 1035: $B;~(B $$\Norm(f)|\Norm(a) = a^m.$$$B$h$C$F(B $\GCD(\Norm(f),b) = 1$ $B$H$J$j(B,
! 1036: $b|\Norm(f)$ $B$@$+$i(B, $b=1$. $B$h$C$F(B, $\Norm(f)$ $B$O(B 2 $B$D0J>e$N0[$J$k4{Ls0x(B
! 1037: $B;R$r4^$_F@$J$$(B. \qed
! 1038:
! 1039: \begin{co}
! 1040: $f\in K(\alpha)[x]$ $B$,L5J?J}$H$9$k;~(B, $\Norm(f)$ $B$,L5J?J}$J$i$P(B,
! 1041: $\Norm(f) = \prod f_i$
! 1042: $B$r(B $K[x]$ $B$K$*$1$k4{LsJ,2r$H$9$k$H$-(B,
! 1043: $f = \prod \GCD(f,f_i)$
! 1044: $B$O(B $f$ $B$N(B $K(\alpha)[x]$ $B$K$*$1$k4{LsJ,2r$rM?$($k(B.
! 1045: \end{co}
! 1046: \proof $h$ $B$r(B $f$ $B$N(B $K(\alpha)[x]$ $B$K$*$1$k4{Ls0x;R$H$9$k(B.
! 1047: $h$ $B$O$"$k(B $f_i$ $B$r3d$j@Z$k(B.
! 1048: $\Norm(h)$ $B$O(B $K[x]$ $B$N4{LsB?9`<0$NQQ$G(B, $\Norm(h)$ $B$OL5J?J}$J(B
! 1049: $\Norm(f)$ $B$r3d$j@Z$k$+$i(B, $\Norm(h)$ $B<+?H$,(B $\Norm(f)$ $B$N4{Ls0x;R(B.
! 1050: $\Norm(h)$ $B$O(B $\Norm(f_i)$ $B$N0x;R$G$b$"$k$+$i(B,
! 1051: $f_i = \Norm(h).$
! 1052: $B:#(B, $h$ $B$H0[$J$k0x;R(B $h_1$ $B$,(B $f_i$ $B$r3d$l$P(B,
! 1053: $BF1MM$K(B $f_i = \Norm(h_1)$. $hh_1|f$ $B$h$j(B
! 1054: $$\Norm(hh_1)={f_i}^2|\Norm(f).$$
! 1055: $B$3$l$O(B $\Norm(f)$ $B$,L5J?J}$G$"$k$3$H$KH?$9$k(B. $B$h$C$F(B $f_i$ $B$O(B $f$ $B$N$?$@0l$D$N(B
! 1056: $B4{Ls0x;R$r4^$`(B. \qed
! 1057:
! 1058: $B0J>e$K$h$j(B, $\Norm(f)$ $B$,L5J?J}$N$H$-$K$O(B, GCD $B$K$h$j(B $f$ $B$N4{Ls0x;R$,(B
! 1059: $K[x]$ $B$K$*$1$k4{LsJ,2r$K$h$jF@$i$l$k$3$H$,$o$+$C$?(B. $\Norm(f)$$B$,L5J?J}(B
! 1060: $B$G$J$$>l9g$K$b(B, $BE,Ev$JJQ?tJQ49$K$h$jL5J?J}2=$G$-$k$3$H$,<!$NL?Bj$h$j(B
! 1061: $B$o$+$k(B.
! 1062:
! 1063: \begin{pr}
! 1064: $f\in K(\alpha)[x]$ $B$,L5J?J}$J$i$P(B, $\Norm(f(x-s\alpha))$ $B$,L5J?J}$H(B
! 1065: $B$J$i$J$$(B $s \in K$ $B$OM-8B8D(B.
! 1066: \end{pr}
! 1067: \proof $f$ $B$N:,$r(B $\beta_1,\cdots,\beta_m$ $B$H$9$k$H(B, $B2>Dj$h$j$3$l(B
! 1068: $B$i$OAj0[$J$k(B. $B$9$k$H(B, $f(x-s\alpha_i)$ $B$N:,$O(B,
! 1069: $$\beta_1+s\alpha_i,\cdots,\beta_m+s\alpha_i$$
! 1070: $B$H$J$k(B. $B$3$l$h$j(B $\Norm(f(x-s\alpha))$ $B$,L5J?J}$G$J$$$N$O(B,
! 1071: $B$"$k(B $i, j, k, l$ $B$KBP$7$F(B,
! 1072: $$\beta_j+s\alpha_i = \beta_k+s\alpha_l$$
! 1073: $B$N>l9g$K8B$k(B.
! 1074: $B$3$N$h$&$J>r7o$rK~$?$9(B $s$ $B$OM-8B8D$7$+$J$$(B. \qed
! 1075:
! 1076: $B0J>e$K$h$j(B, $B<!$N%"%k%4%j%:%`$,F@$i$l$k(B.
! 1077:
! 1078: \begin{al}
! 1079: \label{trager}
! 1080: \begin{tabbing}
! 1081: \\
! 1082: Input : $BL5J?J}$J(B $f(x,\alpha)\in K(\alpha)[x]$, $s \in \Z$\\
! 1083: Output : $f$ $B$N(B $K(\alpha)$ $B>e$N4{Ls0x;R(B $\{f_1,\cdots,f_r\}$\\
! 1084: again:\\
! 1085: $r \leftarrow \res_t(f(x-st,t),g(t))$\\
! 1086: if \= ( $r$ $B$,L5J?J}$G$J$$(B ) then\\
! 1087: \> $s \leftarrow s+1$; goto again\\
! 1088: $r(x) = \prod r_i(x)$ : $r$ $B$N(B $K$ $B>e$G$N4{LsJ,2r(B\\
! 1089: $z \leftarrow f$\\
! 1090: for each $i$ do \{\\
! 1091: \> $f_i \leftarrow \GCD(h(x+s\alpha),z(x,\alpha))$\\
! 1092: \> $t \leftarrow z/f_i$\\
! 1093: \}
! 1094: \end{tabbing}
! 1095: \end{al}
! 1096: $B$3$N%"%k%4%j%:%`$K$*$$$F(B, $B%\%H%k%M%C%/$H$J$jF@$kItJ,$,?tB?$/$"$k(B.
! 1097: \begin{enumerate}
! 1098: \item $B=*7k<0$N7W;;(B
! 1099:
! 1100: $B=*7k<0$N7W;;$O(B, $BItJ,=*7k<0(B, $B9TNs<0$N(B modular $B1i;;$J$I$rAH$_9g$o$;$F9T$J(B
! 1101: $B$&$,(B, $B<B:]$N7W;;;~4V$rH?1G$9$k7W;;NL$,M?$($i$l$F$$$J$$$?$a(B, $B%"%k%4%j%:(B
! 1102: $B%`$NA*Br$,:$Fq$G$"$k(B. $B$^$?(B, $B$$$:$l$K$7$F$b(B, $B=*7k<0$N7W;;$O0lHL$K;~4V$,(B
! 1103: $B$+$+$j(B, $B$7$+$b$=$N=*7k<0$,L5J?J}$G$J$1$l$P<N$F$i$l$k$?$a(B, $B$=$N%3%9%H$N(B
! 1104: $BBg$-$5$OLdBj$G$"$k(B.
! 1105:
! 1106: \item $K$ $B>e$G$N4{LsJ,2r(B
! 1107:
! 1108: $K$ $B$,$^$?$"$k3HBgBN$K$J$C$F$$$k>l9g$K$O$3$N%"%k%4%j%:%`$,:F5"E*$K(B
! 1109: $BMQ$$$i$l$k$3$H$K$J$k(B. $B$3$N:](B, $B%N%k%`$r$H$k$3$H$O(B, $B<!?t$,3HBg<!?tG\(B
! 1110: $B$5$l$k$?$a(B, $B0x?tJ,2r$9$Y$-B?9`<0$N<!?t$,5^B.$KA}Bg$9$k(B. $B:G=*E*$K(B
! 1111: $\Q$ $B>e$N0x?tJ,2r$r9T$J$&$3$H$K$J$k$,(B, $\Q$ $B>e$N0x?tJ,2r<+BN$N%3%9%H(B
! 1112: $B$NLdBj$,$"$k(B.
! 1113:
! 1114: \item $K(\alpha)$ $B>e$G$N(B GCD $B7W;;(B
! 1115:
! 1116: $B0lHL$K(B, $B3HBgBN>e$G$N(B GCD $B$N7W;;$O(B, $B@0?t>e$G$N$=$l$KHf3S$7$F6K$a$F:$Fq(B
! 1117: $B$G$"$k(B. $BFC$K(B, Euclid $B8_=|K!$rMQ$$$k>l9g(B, $BCf4V<0KDD%$O(B, $BDj5AB?9`<0(B $g$
! 1118: $B$,Bg$-$$>l9g(B, $B6K$a$F7c$7$$(B. $B$3$l$r$5$1$k$?$a$$$/$D$+$N(B modular $B7W;;K!(B
! 1119: $B$,Ds0F$5$l$F$$$k(B.
! 1120: \end{enumerate}
! 1121:
! 1122: $B$3$NCf$G(B, 2 $B$*$h$S(B 3 $B$O;_$`$rF@$J$$LdBj$G$"$k$,(B, 1 $B$K4X$7$F$O(B, $BL5J?J}(B
! 1123: $B$G$J$$%N%k%`$rMxMQ$9$k$3$H$K$h$j(B, $B$"$kDxEY2sHr$G$-$k(B.
! 1124:
! 1125: \begin{pr}
! 1126: $f \in K(\alpha)[x]$ $B$,L5J?J}(B,
! 1127: $$\Norm(f) = \prod_i {f_i}^{n_i}$$
! 1128: ($f_i \in K[x]$ $B$O4{Ls(B, $n_i$ $B$O(B 1 $B$H$O8B$i$J$$(B) $B$H$9$k$H(B,
! 1129: $\GCD(f,f_i)$ $B$O(B $f$ $B$NDj?t$G$J$$0x;R$G(B,
! 1130: $$f = \prod \GCD(f,f_i).$$
! 1131: $BFC$K(B, $\Norm(f)$ $B$N=EJ#EY(B 1 $B$N0x;R(B $f_i$ $B$KBP$7$F$O(B, $\GCD(f,f_i)$
! 1132: $B$O4{Ls(B.
! 1133: \end{pr}
! 1134: \proof
! 1135: $h$ $B$r(B $f$ $B$NG$0U$N4{Ls0x;R$H$9$k$H(B, $B$"$k(B $f_i$ $B$,B8:_$7$F(B $h|f_i$ $B$h$j(B
! 1136: $h | \prod \GCD(f,f_i).$
! 1137: $f$ $B$OL5J?J}$h$j(B
! 1138: $f | \prod \GCD(f,f_i).$
! 1139: $\GCD(f,f_i)$ $B$O8_$$$KAG$h$j(B,
! 1140: $f = \prod \GCD(f,f_i).$
! 1141: $B$5$F(B, $f$ $B$N(B
! 1142: $B4{Ls0x;R$N%N%k%`$O$"$k4{LsB?9`<0$NQQ$h$j(B, $BG$0U$N(B $f_i$ $B$KBP$7$F(B,
! 1143: $B$=$NE,Ev$JQQ$O(B $f$ $B$N4{Ls0x;R$N%N%k%`$H$J$C$F$$$k(B. $B$h$C$F(B, $f_i$ $B$O(B
! 1144: $B$"$k(B $f$ $B$N4{Ls0x;R$r4^$`$N$G(B, $\GCD(f,f_i)$ $B$ODj?t$G$J$$(B.
! 1145: $BFC$K(B, $f_i$ $B$,(B $\Norm(f)$ $B$N=EJ#EY(B 1 $B$N0x;R$J$i$P(B, $B$=$l<+?H(B $f$ $B$N$"$k(B
! 1146: $B4{Ls0x;R(B $h$ $B$N%N%k%`$H$J$k(B. $B$3$l$O(B, $BA0$N7O$HF1MM$K$7$F(B, $f_i$ $B$O(B
! 1147: $h$ $B0J30$N0x;R$r4^$^$J$$(B \qed
! 1148:
! 1149: $B$3$NL?Bj$K$h$j(B, $B%N%k%`(B ($B=*7k<0(B) $B$,(B, $BFs$D0J>e$N4{Ls0x;R$r;}$F$P(B, $B$=$NJ,(B
! 1150: $B2r$O(B, $f$ $B$N<+L@$G$J$$0x?tJ,2r$rM?$($k$3$H$,$o$+$k(B. $B$b$7(B, $B%N%k%`$,L5J?(B
! 1151: $BJ}$G$J$1$l$P(B, $B$3$3$G@8@.$7$?0x;R$KBP$7(B, $s$ $B$r<h$jD>$7$F$3$N%"%k%4%j%:(B
! 1152: $B%`$r:F5"E*$KE,MQ$9$k$3$H$K$J$k$,(B, $BLdBj$N%5%$%:$O>.$5$/$J$C$F$$$k(B. $BFC$K(B,
! 1153: $B%N%k%`<+BN$,L5J?J}$G$J$/$F$b=EJ#EY$,(B 1 $B$N0x;R$KBP$7$F$O(B, GCD $B$,4{Ls0x(B
! 1154: $B;R$G$"$k$3$H$,J]>Z$5$l$F$$$k(B. $B$^$?(B, $B%N%k%`$,L5J?J}$G$J$$>l9g$K$b(B, $K$
! 1155: $B>e$G$N0x?tJ,2r$NA0$K(B, $BL5J?J}J,2r$K$h$j%N%k%`$rJ,2r$G$-$k$?$a(B, $K$ $B>e$N(B
! 1156: $B0x?tJ,2r$N7W;;;~4V$bC;=L$G$-$k(B. $B$3$N2~NI$r:N$jF~$l$?%"%k%4%j%:%`$r<!$K(B
! 1157: $B<($9(B.
! 1158:
! 1159: \begin{al}
! 1160: \label{modtrager}
! 1161: \begin{tabbing}
! 1162: \\
! 1163: Input : $BL5J?J}$J(B $f(x,\alpha)\in K(\alpha)[x]$, $s \in \Z$\\
! 1164: Output : $f$ $B$N(B $K(\alpha)$ $B>e$N4{Ls0x;R(B $\{f_1,\cdots,f_r\}$\\
! 1165: $r \leftarrow \res_t(f(x-st,t),g(t))$\\
! 1166: $r(x) = \prod r_i(x)^{m_i}$ : $r$ $B$N(B $K$ $B>e$G$N4{LsJ,2r(B\\
! 1167: $z \leftarrow f$\\
! 1168: for \= each $i$ do \{\\
! 1169: \> $g_i \leftarrow \GCD(r_i(x+s\alpha),z(x,\alpha))$\\
! 1170: \> if $m_i = 1$ then $g_i$ $B$O4{Ls(B\\
! 1171: \> else $(g_i,s+1)$ $B$K$3$N%"%k%4%j%:%`$rE,MQ(B\\
! 1172: \> $t \leftarrow z/g_i$\\
! 1173: \}
! 1174: \end{tabbing}
! 1175: \end{al}
! 1176:
! 1177: \begin{ex}
! 1178: \cite{ABBOTT}
! 1179: \begin{eqnarray*}
! 1180: f(x) &=& x^{16}-136x^{14}+6476x^{12}-141912x^{10}+1513334x^8-7453176x^6+13950764x^4\\
! 1181: & & -5596840x^2+46225
! 1182: \end{eqnarray*}
! 1183: $f(x)$ $B$O(B $\alpha = \sqrt{2}+\sqrt{3}+\sqrt{5}+\sqrt{7}$ $B$N(B $\Q$ $B>e$N(B
! 1184: $B:G>.B?9`<0$G$"$k(B. $\Q(\alpha)/\Q$ $B$O%,%m%"3HBg$G$"$j(B, $f(x)$ $B$O(B
! 1185: $\Q(\alpha)$$B>e0l<!<0$N@Q$KJ,2r$9$k(B. $B$3$N0x?tJ,2r$r%"%k%4%j%:%`(B
! 1186: \ref{trager} $B$G5a$a$k>l9g(B, $F(x)=\Norm(f(x-s\alpha))$ $B$,L5J?J}$H$J$k(B
! 1187: $s\in \Z$ $B$r8+$D$1$F(B $F(x)$ $B$rM-M}?tBN>e$G0x?tJ,2r$9$kI,MW$,$"$k$,(B, $B$3(B
! 1188: $B$N$h$&$J(B $F(x)$ $B$O(B, $BA4$F$NAG?t(B $p$ $B$KBP$70l<!$^$?$OFs<!<0$KJ,2r$7$F$7$^$&(B.
! 1189: $BNc$($P(B $BFs<!0x;R$N@Q(B128 $B8D$KJ,2r$7$?>l9g(B, $BM-M}?tBN>e$N0l$D$N4{Ls0x;R(B
! 1190: (16 $B<!(B) $B$O(B, 128 $B8D$+$i(B 8 $B8D$rA*$s$GF@$i$l$k$3$H$K$J$k$,(B, $B$3$l$OL@$i$+(B
! 1191: $B$KAH9g$;GzH/$r5/$3$7$F$$$F7W;;IT2DG=$G$"$k(B. $B0lJ}$G(B, $BNc$($P(B $s=-1$ $B$N>l(B
! 1192: $B9g(B $F(x)$ $B$OL5J?J}$K$J$i$J$$$,(B, 16 $B8D$N0[$J$k4{Ls0x;R$,L5J?J}J,2r(B
! 1193: $B$*$h$S$=$l$KB3$/4{Ls0x;RJ,2r$K$h$jMF0W$KF@$i$l$k(B.
! 1194: \begin{eqnarray*}
! 1195: F(x) &=& x^{16} (x^2-28)^8 (x^2-20)^8 (x^2-8)^8 (x^2-12)^8\\
! 1196: & & \cdot (x^4-64x^2+64)^4 (x^4-40x^2+16)^4\\
! 1197: & & \cdot (x^4-80x^2+256)^4 (x^4-56x^2+144)^4\\
! 1198: & & \cdot (x^4-72x^2+400)^4 (x^4-96x^2+64)^4\\
! 1199: & & \cdot (x^8-240x^6+12512x^4-203520x^2+891136)^2\\
! 1200: & & \cdot (x^8-192x^6+8576x^4-110592x^2+102400)^2\\
! 1201: & & \cdot (x^8-224x^6+11264x^4-143360x^2+409600)^2\\
! 1202: & & \cdot (x^8-160x^6+5632x^4-61440x^2+147456)^2\\
! 1203: & & \cdot (x^{16}-544x^{14}+103616x^{12}-9082368x^{10}+387413504x^8-7632052224x^6\\
! 1204: & & +57142329344x^4-91698626560x^2+3029401600)
! 1205: \end{eqnarray*}
! 1206: $B$3$l$i$N3F0x;R$+$i(B $f(x)$ $B$NA4$F$N0l<!0x;R$,F@$i$l$k(B.
! 1207: $B0lHL$K(B, $B:G>.J,2rBN$r5a$a$k$?$a$N0x?tJ,2r$J$I(B, $BB?9`<0$r(B, $B$=$N:,$rE:2C$7$?(B
! 1208: $BBN>e$G0x?tJ,2r$9$k>l9g$K(B
! 1209: $B%"%k%4%j%:%`(B \ref{modtrager} $B$,M-8z$H$J$k>l9g$,$"$k(B.
! 1210: \end{ex}
! 1211:
! 1212: \section{$B1~MQ(B --- $BM-M}4X?t$NITDj@QJ,(B}
! 1213: $BBe?tBN>e$N(B GCD $B$rMQ$$$F(B, $BM-M}4X?t$NITDj@QJ,$r(B, $B@QJ,5-9f$r4^$^$J$$7A(B
! 1214: $B$GI=<($9$kJ}K!$K$D$$$F=R$Y$k(B.
! 1215:
! 1216: $B0lHL$K(B, $BM-M}4X?t(B $f(x)=n(x)/d(x)$ ($n,d \in \Q[x]$) $B$NITDj@QJ,$O(B,
! 1217: $f$ $B$NItJ,J,?tJ,2r$K$h$j7W;;$G$-$k(B. $B$7$+$7(B, $B$=$N$?$a$KJ,Jl(B $d$ $B$r(B
! 1218: 1 $B<!0x;R$N@Q$KJ,2r$9$k$K$O(B $d$ $B$N:G>.J,2rBN$r5a$a$k$3$H$,I,MW$H$J$k(B.
! 1219:
! 1220: $B$^$?(B, $BITDj@QJ,<+BN$K(B, $d$ $B$NJ,2r$K$h$j8=$l$?Be?tE*?t$,8=$l$k$H$O(B
! 1221: $B8B$i$J$$(B.
! 1222: \begin{ex}
! 1223: $f=d'/d$ $B$J$i$P(B $\displaystyle \int f dx = \log d.$
! 1224: \end{ex}
! 1225: $B$3$N$3$H$+$i(B, $B:G>.$NBe?tE*?t$NE:2C$GITDj@QJ,$rI=<($9$k$3$H$r9M$($k(B.
! 1226:
! 1227: \subsection{$BM-M}ItJ,$N7W;;(B}
! 1228:
! 1229: $f=n/d$, $n,d \in \Q[x]$ $B$H$9$k(B. $B$b$7(B $\deg(n)\ge \deg(d)$ $B$J$i$P(B,
! 1230: $$n = qd+r, \quad q,d \in \Q[x], \deg(r) < \deg(d)$$
! 1231: $B$K$h$j(B, $f=q+r/d$ $B$H=q$1$k(B. $B$3$N$H$-(B $\int f dx = \int q dx + \int r/d dx$
! 1232: $B$G(B, $BB?9`<0$NITDj@QJ,$O<+L@$@$+$i(B, $B$"$i$+$8$a(B $\deg(n) < \deg(d)$ $B$H$7$F$h$$(B.
! 1233:
! 1234: \begin{pr}
! 1235: $\deg(n)<\deg(d)$ $B$H$9$k(B. $d_r = \GCD(d,d')$, $d_l = d/d_r$ $B$H$*$/$H(B,
! 1236: $\deg(n_r)<\deg(d_r)$, $\deg(n_l)<\deg(d_l)$ $B$J$k(B $n_r, n_l \in \Q[x]$ $B$,0l0U(B
! 1237: $BE*$KB8:_$7$F(B,
! 1238: $$\int {n\over d} dx = {{n_r}\over {d_r}} + \int {{n_l}\over{d_l}} dx$$
! 1239: \end{pr}
! 1240: \proof
! 1241: $d=\prod_i d_i^i$ $B$J$kL5J?J}J,2r$KBP1~$7$F(B,
! 1242: $${n\over d} = \sum_i \sum_j {{n_{ij}}\over{d_i^j}}\quad (\deg(r_{ij}) < \deg(d_i))$$
! 1243: $B$J$kItJ,J,?tJ,2r$,L?Bj(B \ref{parfrac} $B$K$h$jB8:_$9$k(B.
! 1244: $d_r=\prod_i d_i^{i-1}$, $d_l=\prod_i d_i$ $B$G$"$k(B.
! 1245: $d_i$ $B$OL5J?J}$@$+$i(B, $\GCD(d_i,d_i')=1.$
! 1246: $B$h$C$F(B, $B3F(B $n_{ij}$ $B$KBP$7(B, $s_{ij}, t_{ij} \in \Q[x]$
! 1247: ($\deg(s_{ij})< \deg(d_i)-1$, $\deg(t_{ij})< \deg(d_i)$) $B$,B8:_$7$F(B,
! 1248: $$s_{ij}d_i+t_{ij}d_i'=n_{ij}.$$
! 1249: $B$3$l$rMQ$$$F(B, $j>1$ $B$N$H$-(B
! 1250: $$\int {{n_{ij}}\over{d_i^j}} dx = \int {{s_{ij}}\over {d_i^{j-1}}}dx
! 1251: + \int {{t_{ij}d_i'}\over {d_i^j}}dx$$
! 1252: $B$3$3$G(B, $$({1\over {1-j}}\cdot {1\over{d^{j-1}}})'={{d_i'}\over {d_i^j}}$$
! 1253: $B$h$j(B,
! 1254: $$\int {{t_{ij}d_i'}\over {d_i^j}}dx= {1\over {1-j}}\cdot {1\over{d_i^{j-1}}}\cdot t_{ij} -
! 1255: \int {1\over {1-j}}\cdot {1\over{d_i^{j-1}}} t_{ij}' dx.$$
! 1256: $B$h$C$F(B
! 1257: $$\int {{n_{ij}}\over{d_i^j}} dx = {t_{ij}\over {(1-j)d_i^{j-1}}}
! 1258: +\int {{s_{ij}+{{t_{ij}'}\over{j-1}}}\over {d_i^{j-1}}} dx$$
! 1259: $\deg({s_{ij}+{{t_{ij}'}\over{j-1}}}) < \deg(d_i)-1$ $B$h$j(B,
! 1260: $B$3$N@QJ,$NBh(B 2 $B9`$r(B $\int {{n_{i,j-1}}\over{d_i^{j-1}}}dx$ $B$K2C$($F$b(B,
! 1261: $BJ,;R$N<!?t$OA}Bg$7$J$$(B. $B$h$C$F(B, $B$3$NA`:n$r(B $j>1$ $B$J$k9`$KBP$7$F7+$jJV$9(B
! 1262: $B$3$H$K$h$j(B,
! 1263: $$\int {n\over d}dx = \sum_i\sum_{j>1}{t_{ij}\over {(1-j)d_i^{j-1}}}
! 1264: +\sum_i \int {{u_i}\over {d_i}} dx \quad (\deg(u_i)<\deg(d_i))$$
! 1265: $B$J$k7A$KJQ7A$G$-$k(B. $BBh(B 1 $B9`(B, $BBh(B 2 $B9`$NHd@QJ,4X?t$r$^$H$a$F(B
! 1266: $B$=$l$>$l(B ${{n_r}\over {d_r}}$, ${{n_l}\over{d_l}}$ $B$H$*$1$P<!?t$N(B
! 1267: $B>r7o$rK~$?$9(B. $B0l0U@-$OL@$i$+(B. \qed
! 1268:
! 1269: $B$3$NL?Bj$GJ]>Z$5$l$?(B $n_r$, $n_l$ $B$O(B, $BL$Dj78?tK!$G7hDj$9$k$3$H$,$G$-$k(B.
! 1270:
! 1271: \begin{al}
! 1272: \begin{tabbing}
! 1273: \\
! 1274: Input: $f(x)=n(x)/d(x)\in \Q(x)$, $\deg(n)<\deg(d)$\\
! 1275: Output: $\displaystyle \int f(x)dx = {{n_r(x)}\over{d_r(x)}}+\int {{n_l(x)}\over{d_l(x)}}dx$, $d_l$ $B$OL5J?J}$G(B $n_r, d_r, n_l, d_l \in \Q[x]$ $B$J$kJ,2r(B\\
! 1276: $B$?$@$7(B $\deg(n_r)<\deg(d_r)$, $\deg(n_l)<\deg(d_l)$\\
! 1277: $d_r \leftarrow \GCD(d,d')$, \quad $d_l \leftarrow d/d_r$\\
! 1278: $m_r \leftarrow \deg(d_r)$, \quad $m_l \leftarrow \deg(d_l)$\\
! 1279: $n_r \leftarrow \sum_{i=0}^{m_r-1}a_i x^i$, \quad $n_l \leftarrow \sum_{i=0}^{m_l-1}b_i x^i$\\
! 1280: $n=n_r'd_l-({{d_ld_r'}\over{d_r}})n_r+d_rn_l$ $B$+$i(B $a_i$, $b_i$$B$r5a$a$k(B\\
! 1281: return $\displaystyle \int f(x)dx =
! 1282: {{n_r(x)}\over{d_r(x)}}+\int {{n_l(x)}\over{d_l(x)}}dx$
! 1283: \end{tabbing}
! 1284: \end{al}
! 1285:
! 1286: \subsection{$BBP?tItJ,$N7W;;(B}
! 1287:
! 1288: $f(x)=n(x)/d(x)$, $\GCD(n,d)=1$, $\deg(n)<\deg(d)$ $B$G(B $d$ $B$OL5J?J}$H$9$k(B. $B$3$N$H$-(B
! 1289: $$\int f dx = \sum_i c_i\log r_i$$
! 1290: $B$H=q$1$k(B. $B0lHL$K(B $c_i \in \Q, r_i \in \Q[x]$ $B$H$O8B$i$:(B, $B2?$i$+$NBe?tE*?t$r4^$`(B
! 1291: $B2DG=@-$,$"$k$,(B, $B$3$NBe?t3HBg$r:G>.8B$K$9$k$h$&$JI=<($r5a$a$?$$(B.
! 1292:
! 1293: \begin{pr}(Rothstein)
! 1294:
! 1295: $K$ $B$rJ#AG?tBN(B $\C$ $B$NItJ,BN$H$7(B,
! 1296: $f(x)=n(x)/d(x)$, $n,d \in K[x]$, $\GCD(n,d)=1$, $\deg(n)<\deg(d)$ $B$G(B $d$ $B$OL5J?J}(B, $BL5J?J}$H$9$k(B. $B$3$N$H$-(B,
! 1297: $$n/d = \sum_{i=1}^n c_i v_i'/v_i$$
! 1298: $B$?$@$7(B $c_i \in \C$ $B$OAj0[$j(B, $v_i \in \C[x]$, $v_i$ $B$O%b%K%C%/(B, $BL5J?J}$G8_$$$KAG(B,
! 1299: $B$H=q$1$?$J$i$P(B, $c_i$ $B$O(B
! 1300: $$R(z)=\res_x(n-zd',d) \in K[z]$$
! 1301: $B$N:,$G(B,
! 1302: $$v_i=\GCD(n-c_id',d).$$
! 1303: \end{pr}
! 1304: \proof
! 1305: \underline{claim 1} $v=d.$
! 1306:
! 1307: $v=\prod_{i=1}^n$ $B$H$*$/$H(B,
! 1308: $$nv = d\sum_{i=1}^nc_iv_i'(v/v_i).$$
! 1309: $\GCD(n,d)=1$ $B$h$j(B $d|v.$ $B0lJ}$G(B, $v_i$|$B1&JU$h$j(B, $B$b$7(B $v{\not |}$
! 1310: $B$J$i$P(B $v_i|c_iv_i'(v/v_i)$ $B$H$J$k$,(B, $B$3$l$O(B $v_i$ $B$K4X$9$k>r7o$h$jIT2DG=(B.
! 1311: $B$h$C$F(B $v_i|d.$ $B7k6I(B $v|d$ $B$H$J$j(B $v=d.$ \qed\\
! 1312: \underline{claim 2} $v_i=\GCD(n-c_id',d).$
! 1313:
! 1314: claim 1 $B$h$j(B $n = \sum_{i=1}^n c_iv_i'(v/v_i).$
! 1315: $d'=\sum_{i=1}^n v_i'(v/v_i)$ $B$h$j(B,
! 1316: $$n-c_id'=\sum_{j\neq i} (c_j-c_i)v_j'(v/v_j).$$
! 1317: $B$3$l$+$i(B $v_i | n-c_id'$ $B$,$o$+$k(B. $B$h$C$F(B $v_i | \GCD(n-c_id',d).$
! 1318: $B0lJ}$G(B, $j\neq i$ $B$N$H$-(B,
! 1319: $$\GCD(n-c_id',v_j)=\GCD((c_j-c_i)v_j'(v/v_j),v_j)=1$$
! 1320: $B$h$j(B, $v_i=\GCD(n-c_id',d).$ \qed
! 1321:
! 1322: claim 2 $B$h$j(B, $c_i$ $B$,(B $R(z)$ $B$N:,$G$J$1$l$P$J$i$J$$$3$H$b$o$+$k(B. \\
! 1323: \underline{claim 3} $\{c_1,\cdots,c_n\} = R(z)$ $B$N:,A4BN(B
! 1324:
! 1325: $c$ $B$,(B $R(z)$ $B$N:,$J$i$P(B, $v_0=\GCD(n-cd',d)$ $B$O<+L@$G$J$$(B $d$ $B$N0x;R(B.
! 1326: $B$h$C$F(B $v_0$ $B$N4{Ls0x;R(B $g$ $B$r0l$D$H$l$P(B, $B$"$k(B $v_i$ $B$,B8:_$7$F(B $g|v_i.$
! 1327: $$g|(n-cd')=\sum_{j=1}^n (c_j-c)v_j'(v/v_j)$$
! 1328: $B$h$j(B, $g|(c_i-c)v_i'(v/v_i).$ $B$3$l$O(B $c_i=c$ $B$N$H$-$N$_2DG=(B. \qed
! 1329:
! 1330: \begin{co}
! 1331: $K$ $B$rJ#AG?tBN(B $C$ $B$NItJ,BN$H$7(B,
! 1332: $f(x)=n(x)/d(x)$, $n,d \in K[x]$, $\GCD(n,d)=1$, $\deg(n)<\deg(d)$ $B$G(B $d$ $B$OL5J?J}(B, $B%b%K%C%/$H$7(B,
! 1333: $$R(z)=\res_x(n-zd',d) \in K[z]$$
! 1334: $B$H$9$k(B.
! 1335: $K_R$ $B$r(B $R(z)$ $B$N:G>.J,2rBN$H$9$l$P(B,
! 1336: $K_R$ $B$,(B $\int n/d dx$ $B$rI=<($9$k$?$a$N:G>.$N(B $K$ $B$N3HBg(B.
! 1337: \end{co}
! 1338: \proof $F$ $B$r(B $K$ $B$N3HBgBN$H$7(B, $c_i \in F$, $v_i \in F[x]$ $B$K$h$k(B
! 1339: $n/d = \sum_i c_i v_i'/v_i$ $B$J$kI=<($r$H$k$H(B, $BBN$N3HBg$J$7$K(B, $BA0L?Bj$N(B
! 1340: $c_i$ $v_i$ $B$KBP$9$k>r7o$,K~$?$5$l$k$h$&$K$G$-$k(B. $B$3$N$H$-(B, $c_i$ $B$O(B
! 1341: $R(z)$ $B$N:,$G(B $c_i \in F$ $B$@$+$i(B, $K_R \subset F$. $K_R$ $B>e$G$3$NI=<((B
! 1342: $B$,$G$-$k$3$H$OA0L?Bj$GJ]>Z$5$l$F$$$k(B. \qed
! 1343:
! 1344:
! 1345:
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to factor.tex CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM / doc / compalg