Annotation of OpenXM/doc/compalg/factor.tex, Revision 1.2
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: $B$^$?(B, $BITDj@QJ,<+BN$K(B, $d$ $B$NJ,2r$K$h$j8=$l$?Be?tE*?t$,8=$l$k$H$O(B
1220: $B8B$i$J$$(B.
1221: \begin{ex}
1222: $f=d'/d$ $B$J$i$P(B $\displaystyle \int f dx = \log d.$
1223: \end{ex}
1224: $B$3$N$3$H$+$i(B, $B:G>.$NBe?tE*?t$NE:2C$GITDj@QJ,$rI=<($9$k$3$H$r9M$($k(B.
1225:
1226: \subsection{$BM-M}ItJ,$N7W;;(B}
1227:
1228: $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,
1229: $$n = qd+r, \quad q,d \in \Q[x], \deg(r) < \deg(d)$$
1230: $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$
1231: $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.
1232:
1233: \begin{pr}
1234: $\deg(n)<\deg(d)$ $B$H$9$k(B. $d_r = \GCD(d,d')$, $d_l = d/d_r$ $B$H$*$/$H(B,
1235: $\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
1236: $BE*$KB8:_$7$F(B,
1237: $$\int {n\over d} dx = {{n_r}\over {d_r}} + \int {{n_l}\over{d_l}} dx$$
1238: \end{pr}
1239: \proof
1240: $d=\prod_i d_i^i$ $B$J$kL5J?J}J,2r$KBP1~$7$F(B,
1241: $${n\over d} = \sum_i \sum_j {{n_{ij}}\over{d_i^j}}\quad (\deg(r_{ij}) < \deg(d_i))$$
1242: $B$J$kItJ,J,?tJ,2r$,L?Bj(B \ref{parfrac} $B$K$h$jB8:_$9$k(B.
1243: $d_r=\prod_i d_i^{i-1}$, $d_l=\prod_i d_i$ $B$G$"$k(B.
1244: $d_i$ $B$OL5J?J}$@$+$i(B, $\GCD(d_i,d_i')=1.$
1245: $B$h$C$F(B, $B3F(B $n_{ij}$ $B$KBP$7(B, $s_{ij}, t_{ij} \in \Q[x]$
1246: ($\deg(s_{ij})< \deg(d_i)-1$, $\deg(t_{ij})< \deg(d_i)$) $B$,B8:_$7$F(B,
1247: $$s_{ij}d_i+t_{ij}d_i'=n_{ij}.$$
1248: $B$3$l$rMQ$$$F(B, $j>1$ $B$N$H$-(B
1249: $$\int {{n_{ij}}\over{d_i^j}} dx = \int {{s_{ij}}\over {d_i^{j-1}}}dx
1250: + \int {{t_{ij}d_i'}\over {d_i^j}}dx$$
1251: $B$3$3$G(B, $$({1\over {1-j}}\cdot {1\over{d^{j-1}}})'={{d_i'}\over {d_i^j}}$$
1252: $B$h$j(B,
1253: $$\int {{t_{ij}d_i'}\over {d_i^j}}dx= {1\over {1-j}}\cdot {1\over{d_i^{j-1}}}\cdot t_{ij} -
1254: \int {1\over {1-j}}\cdot {1\over{d_i^{j-1}}} t_{ij}' dx.$$
1255: $B$h$C$F(B
1256: $$\int {{n_{ij}}\over{d_i^j}} dx = {t_{ij}\over {(1-j)d_i^{j-1}}}
1257: +\int {{s_{ij}+{{t_{ij}'}\over{j-1}}}\over {d_i^{j-1}}} dx$$
1258: $\deg({s_{ij}+{{t_{ij}'}\over{j-1}}}) < \deg(d_i)-1$ $B$h$j(B,
1259: $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,
1260: $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
1261: $B$3$H$K$h$j(B,
1262: $$\int {n\over d}dx = \sum_i\sum_{j>1}{t_{ij}\over {(1-j)d_i^{j-1}}}
1263: +\sum_i \int {{u_i}\over {d_i}} dx \quad (\deg(u_i)<\deg(d_i))$$
1264: $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
1265: $B$=$l$>$l(B ${{n_r}\over {d_r}}$, ${{n_l}\over{d_l}}$ $B$H$*$1$P<!?t$N(B
1266: $B>r7o$rK~$?$9(B. $B0l0U@-$OL@$i$+(B. \qed
1267:
1268: $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.
1269:
1270: \begin{al}
1271: \begin{tabbing}
1272: \\
1273: Input: $f(x)=n(x)/d(x)\in \Q(x)$, $\deg(n)<\deg(d)$\\
1274: 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\\
1275: $B$?$@$7(B $\deg(n_r)<\deg(d_r)$, $\deg(n_l)<\deg(d_l)$\\
1276: $d_r \leftarrow \GCD(d,d')$, \quad $d_l \leftarrow d/d_r$\\
1277: $m_r \leftarrow \deg(d_r)$, \quad $m_l \leftarrow \deg(d_l)$\\
1278: $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$\\
1279: $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\\
1280: return $\displaystyle \int f(x)dx =
1281: {{n_r(x)}\over{d_r(x)}}+\int {{n_l(x)}\over{d_l(x)}}dx$
1282: \end{tabbing}
1283: \end{al}
1284:
1285: \subsection{$BBP?tItJ,$N7W;;(B}
1286:
1287: $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
1288: $$\int f dx = \sum_i c_i\log r_i$$
1289: $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
1290: $B2DG=@-$,$"$k$,(B, $B$3$NBe?t3HBg$r:G>.8B$K$9$k$h$&$JI=<($r5a$a$?$$(B.
1291:
1.2 ! noro 1292: \begin{pr}(Rothstein{\rm\cite{DAV}})
1.1 noro 1293:
1294: $K$ $B$rJ#AG?tBN(B $\C$ $B$NItJ,BN$H$7(B,
1295: $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,
1296: $$n/d = \sum_{i=1}^n c_i v_i'/v_i$$
1.2 ! noro 1297: $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 1298: $B$H=q$1$?$J$i$P(B, $c_i$ $B$O(B
1299: $$R(z)=\res_x(n-zd',d) \in K[z]$$
1300: $B$N:,$G(B,
1301: $$v_i=\GCD(n-c_id',d).$$
1302: \end{pr}
1303: \proof
1304: \underline{claim 1} $v=d.$
1305:
1306: $v=\prod_{i=1}^n$ $B$H$*$/$H(B,
1307: $$nv = d\sum_{i=1}^nc_iv_i'(v/v_i).$$
1.2 ! noro 1308: $\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 1309: $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.
1310: $B$h$C$F(B $v_i|d.$ $B7k6I(B $v|d$ $B$H$J$j(B $v=d.$ \qed\\
1311: \underline{claim 2} $v_i=\GCD(n-c_id',d).$
1312:
1313: claim 1 $B$h$j(B $n = \sum_{i=1}^n c_iv_i'(v/v_i).$
1314: $d'=\sum_{i=1}^n v_i'(v/v_i)$ $B$h$j(B,
1315: $$n-c_id'=\sum_{j\neq i} (c_j-c_i)v_j'(v/v_j).$$
1316: $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).$
1317: $B0lJ}$G(B, $j\neq i$ $B$N$H$-(B,
1318: $$\GCD(n-c_id',v_j)=\GCD((c_j-c_i)v_j'(v/v_j),v_j)=1$$
1319: $B$h$j(B, $v_i=\GCD(n-c_id',d).$ \qed
1320:
1321: 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. \\
1322: \underline{claim 3} $\{c_1,\cdots,c_n\} = R(z)$ $B$N:,A4BN(B
1323:
1324: $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.
1325: $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.$
1326: $$g|(n-cd')=\sum_{j=1}^n (c_j-c)v_j'(v/v_j)$$
1327: $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
1328:
1329: \begin{co}
1.2 ! noro 1330: $K$ $B$rJ#AG?tBN(B $\C$ $B$NItJ,BN$H$7(B,
1.1 noro 1331: $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,
1332: $$R(z)=\res_x(n-zd',d) \in K[z]$$
1333: $B$H$9$k(B.
1334: $K_R$ $B$r(B $R(z)$ $B$N:G>.J,2rBN$H$9$l$P(B,
1335: $K_R$ $B$,(B $\int n/d dx$ $B$rI=<($9$k$?$a$N:G>.$N(B $K$ $B$N3HBg(B.
1336: \end{co}
1337: \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
1338: $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
1339: $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
1340: $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
1341: $B$,$G$-$k$3$H$OA0L?Bj$GJ]>Z$5$l$F$$$k(B. \qed
1342:
1343:
1344:
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>