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