Annotation of OpenXM/doc/compalg/factor.tex, Revision 1.4
1.4 ! noro 1: %$OpenXM: OpenXM/doc/compalg/factor.tex,v 1.3 2000/03/28 02:02:29 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}
198: Input : $f(x) \in K[x]$ ($K$ $B$OI8?t(B $p>0$ $B$NBN(B)\\
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: \> $g \leftarrow F$ $B$N85(B, \quad $F \leftarrow F \backslash \{g\}$\\
427: \> $(c_1,\cdots,c_r) \leftarrow$ $BMp?t%Y%/%H%k(B ($c_i \in GF(q)$)\\
428: \> $e \leftarrow \sum c_ie_i$ \\
429: \> if \= $p=2$\\
430: \>\> $E \leftarrow \Tr(e)$\\
431: \>else\\
432: \>\> $E \leftarrow e^{(q-1)/2}-1$\\
433: \> $h \leftarrow \GCD(g,E)$\\
434: \> if $h \neq 1,g$\\
435: \>\> $F \leftarrow F \cup \{h,g/h\}$\\
436: \}\\
437: return F
438: \end{tabbing}
439: \end{al}
440:
441: \section{DDF (distinct degree factorization)}
442: $BM-8BBN>e$NB?9`<0$KBP$7$F$O(B, GCD $B$N$_$K$h$k(B DDF (distinct degree
443: factorization;$B<!?tJL0x;RJ,2r(B) $B$H$h$P$l$kM=HwE*$JJ,2r$,2DG=$G$"$k(B. DDF
444: $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,
445: $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.
446: $B$^$?(B, $BJ,2r@.J,$N4{Ls0x;R$,F10l<!?t$G$"$k$3$H$rMxMQ$7$F(B, $BFC<l$J<jK!(B
447: $B$K$h$j4{LsJ,2r$r$9$k$3$H$b2DG=$K$J$k(B.
448:
449: $B7O(B \ref{irred_mod}$B$h$j(B, $B<!$N%"%k%4%j%:%`$,F@$i$l$k(B.
450:
451: \begin{al}
452: \begin{tabbing}
453: \\
454: Input : $f(x) \in GF(q)[x]$, $f$ $B$OL5J?J}(B\\
455: Output : $f(x) = \prod f_i$, $f_i$ $B$O(B $f$ $B$N(B $i$ $B<!4{Ls0x;R$N@Q(B\\
456: $w \leftarrow x$,\quad $i \leftarrow 1$\\
457: while\= ($i \le \deg(f)/2$) do \{\\
458: \> $w \leftarrow w^q \bmod f$\\
459: \> $f_i \leftarrow \GCD(f,w-x)$\\
460: \> if \= $f_i \neq 1$ \{\\
461: \>\> $f \leftarrow f/f_i$\\
462: \>\> $w \leftarrow w \bmod f$\\
463: \>\> $E \leftarrow e^{(q-1)/2}-1$\\
464: \>\}\\
465: \}\\
466: while ( $i < \deg(f)$ )\\
467: \> $f_i \leftarrow 1$\\
468: $f_{\deg(f)} \leftarrow f$\\
469: return $\prod f_i$
470: \end{tabbing}
471: \end{al}
472: $i$ $B2sL\$K$*$$$F$O(B, $i$ $B$N??$NLs?t$r<!?t$K;}$D0x;R$O4{$K=|$+$l$F(B
473: $B$$$k$?$a(B, $i$ $B<!$N0x;R$N$_$,<h$j=P$;$k(B. $B$^$?(B, $i \ge \deg(f)/2$
474: $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.
475:
476: $B$3$N%"%k%4%j%:%`$K$*$$$F(B, $w^q \bmod f$ $B$N7W;;$r7+$jJV$9I,MW$,$"$k(B.
477: $B$7$+$7(B, $B0lHL$K(B
478: $$g = \sum_{i=0}^m a_ix^i \Rightarrow g^q \bmod f = \sum_{i=0}^m a_ix^{iq} \bmod f$$
479: $B$h$j(B,
480: $w_0 = x^q \bmod f$
481: $B$N7W;;7k2L$+$i(B
482: $w_i = w_0^i \bmod f = w_{i-1}w_0 \bmod f$
483: $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
484: $B7W;;$O8zN($h$/7W;;$G$-$k(B.
485:
486: \section{$B<!?tJL0x;R$NJ,2r(B}
487: $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
488: $B%"%k%4%j%:%`$K$h$j4{LsJ,2r$G$-$k$,(B, $B4^$^$l$k4{Ls0x;R$N<!?t$,A4$FEy$7$$(B
489: $B$3$H$rMxMQ$7$FJ,2r$r9T$&$3$H$r9M$($k(B.
490:
491: \begin{pr}
492: $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
493: $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
494: $B$V$H$-(B,
495: $\GCD(g^{(q^d-1)/2}-1,f)=f_1$ $B$^$?$O(B $f_2$
1.4 ! noro 496: $B$H$J$k3NN($O(B $1/2-1/(2q^d)$.
1.1 noro 497: \end{pr}
498: \proof
499: $f_1$, $f_2$ $B$,(B $d$ $B<!4{Ls$h$j(B,
500: $$GF(q)[x]/(f_1) \simeq GF(q)[x]/(f_2) \simeq GF(q^d).$$
501: $B$h$C$F(B, $BG$0U$N(B $g \in GF(q)[x]$ $B$KBP$7(B,
502: $$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.$$
503: $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,
504: $B$=$&$G$J$$$b$N$O(B $(q^d+1)/2$ $B8D$"$k(B.
505: $\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
506: $B0lJ}$N$_$,(B 1 $B$K$J$k>l9g$G$"$k(B.
507: $B$3$3$G(B, $BCf9q>jM>DjM}$K$h$j(B,
508: $$GF(q)[x]/(f_1f_2) \simeq GF(q)[x]/(f_1)\bigoplus GF(q)[x]/(f_2)
509: \simeq GF(q^d)\bigoplus GF(q^d)$$$B$@$+$i(B, $BG$0U$N(B $(a_1,a_2) \in
510: GF(q^d)\bigoplus GF(q^d)$ $B$N85$KBP$7(B, $BB?9`<0$NAH$KBP$7(B, $a_1 = g
511: \equiv g \bmod f_1$, $a_2 = g \equiv g \bmod f_2$ $B$J$k(B$2d-1$ $B<!0J2<$N(B
512: $BB?9`<0(B $g$ $B$,0l0UE*$KBP1~$9$k(B.
513: $B$h$C$F(B, $2d-1$ $B0J2<$NB?9`<0(B $q^{2d}$ $B8D$N$&$A(B,
514: $\GCD(g^{(q^d-1)/2}-1,f)=f_1$ $B$^$?$O(B $f_2$ $B$H$J$k$N$O(B,
515: $$2(q^d-1)/2\cdot (q^d+1)/2 = (q^{2d}-1)/2$$
1.4 ! noro 516: $B8D$G$"$j(B, $B3NN($O(B $1/2-1/(2q^{2d}).$ \qed
1.1 noro 517:
518: \begin{pr}
519: $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
520: $B$D$N(B $d$ $B<!4{Ls0x;R$H$7(B,
521: $$\Tr(x) = \sum_{i=0}^{nd-1}x^{2^i}$$
522: $B$H$9$k(B. $GF(q)$ $B>e$N(B $B9b!9(B $2d-1$
523: $B<!<0(B $g$ $B$r%i%s%@%`$KA*$V$H$-(B,
524: $\GCD(\Tr(x),f)=f_1$ $B$^$?$O(B $f_2$
525: $B$H$J$k3NN($O(B $1/2$.
526: \end{pr}
527: \proof
528: $f_1$, $f_2$ $B$,(B $d$ $B<!4{Ls$h$j(B,
529: $$GF(q)[x]/(f_1) \simeq GF(q)[x]/(f_2) \simeq GF(2^{nd}).$$
530: $B$h$C$F(B, $BG$0U$N(B $g \in GF(q)[x]$ $B$KBP$7(B,
531: $$s_1=\Tr(g \bmod f_1) = 0,1,\quad s_2=\Tr(g \bmod f_2) = 0,1.$$
532: $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
533: $B$:$D$"$k(B. \\
534: $\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
535: $B0lJ}$N$_$,(B 0 $B$K$J$k>l9g$G$"$k(B.
536: $B$3$3$G(B, $BCf9q>jM>DjM}$K$h$j(B,
537: $$GF(q)[x]/(f_1f_2) \simeq GF(q)[x]/(f_1)\bigoplus GF(q)[x]/(f_2)
538: \simeq GF(2^{nd})\bigoplus GF(2^{nd})$$$B$@$+$i(B, $BG$0U$N(B $(a_1,a_2) \in
539: GF(2^{nd})\bigoplus GF(2^{nd})$ $B$N85$KBP$7(B, $BB?9`<0$NAH$KBP$7(B, $a_1 = g
540: \equiv g \bmod f_1$, $a_2 = g \equiv g \bmod f_2$ $B$J$k(B$2d-1$ $B<!0J2<$N(B
541: $BB?9`<0(B $g$ $B$,0l0UE*$KBP1~$9$k(B.
542: $B$h$C$F(B, $2d-1$ $B0J2<$NB?9`<0(B $2^{2nd}$ $B8D$N$&$A(B,
543: $\GCD(\Tr(x),f)=f_1$ $B$^$?$O(B $f_2$ $B$H$J$k$N$O(B,
544: $2 \cdot (2^{nd-1})^2 = 2^{2nd-1}$
545: $B8D$G$"$j(B, $B3NN($O(B $1/2.$ \qed\\
546: $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
547: 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,
548: Cantor-Zassenhaus $B%"%k%4%j%:%`$NJQ7AHG$,E,MQ$G$-$k(B.
549:
550: \begin{al}
551: \begin{tabbing}
552: \\
553: Input : $f(x) \in GF(q)[x]$, $q=p^n$, $f$ $B$OL5J?J}$G(B $d$ $B<!4{Ls0x;R$N@Q(B\\
554: Output : $f(x) = \prod f_i$, $f$ $B$N(B $B4{Ls0x;RJ,2r(B\\
555: $r \leftarrow \deg(f)/d,\quad F \leftarrow \{f\}$\\
556: while\= ($|F| < r$) do \{\\
557: \> $h \leftarrow F$ $B$N(B $\deg(h)>d$ $B$J$k85(B,\quad $F \leftarrow F \backslash \{h\}$\\
558: \> $g \leftarrow 2d-1$ $B<!$N%i%s%@%`$JB?9`<0(B\\
559: \> if \= $p=2$\\
560: \>\>$G \leftarrow \sum_{j=0}^{rd-1}g^{2^i}$\\
561: \> else\\
562: \>\> $G \leftarrow g^{(q^d-1)/2}-1$\\
563: \> $z \leftarrow \GCD(h,G)$\\
564: \> if $z \neq 1,h$ \\
565: \>\> $F \leftarrow F \cup \{z,h/z\}$\\
566: \}\\
567: return $F$\\
568: \end{tabbing}
569: \end{al}
570:
571: \section{$B@0?t78?t0lJQ?tB?9`<0$N0x?tJ,2r(B}
572: $B7W;;5!Be?t%7%9%F%`$K$*$$$FMQ$$$i$l$F$$$k0x?tJ,2r%"%k%4%j%:%`$O(B,
573: $B2?$i$+$N=`F17?$K$h$jB?9`<0$r$h$j07$$$d$9$$6u4V$K<LA|$7(B, $B$=$N(B
574: $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
575: $BA|$+$i$b$H$N6u4V$K$*$1$k0x;R$r9=@.$9$k(B, $B$H$$$&J}K!$K$h$k$b$N$,B?$$(B.
576: $BFC$K(B, $BFsJQ?t0J>e$NB?9`<0$N0x?tJ,2r$O0lJQ?tB?9`<0$K5"Ce$5$l$k$J$I(B,
577: $B0lJQ?tB?9`<0$N0x?tJ,2r$O(B, $B0x?tJ,2r%"%k%4%j%:%`$K$*$$$F=EMW$J0LCV$r(B
578: $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
579: $B%"%k%4%j%:%`$K$D$$$F=R$Y$k(B.
580:
581: $BL5J?J}$J(B $f \in \Z[x]$ $B$N0x?tJ,2r%"%k%4%j%:%`$O(B, $BM-8BBN>e$N0x?tJ,2r(B,
582: Hensel $B9=@.(B, $B;n$73d$j$N;0$D$NItJ,$+$i$J$k(B.
583:
584: \begin{pr}(Hensel)
585: $f \in \Z[x], p \in \N$ $B$OAG?t$G(B,
586: $$f \equiv \prod f_{1i} \bmod p,\quad f_{1i} \in GF(p)[x], \quad \deg(f) = \deg(\prod_i f_{1i})$$
587: $f_{1i}$ $B$O(B $GF(p)$ $B>e$G8_$$(B
588: $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
589: $B$7$F(B,
590: $$f \equiv \prod_i f_{ki} \bmod {p^k},\quad f_{1i} \equiv f_{ki} \bmod p, \quad \deg(f_{1i}) = \deg(f_{ki}).$$
591: \end{pr}
592: \proof
593: $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.
594: $$f_{(k+1)i}=f_{ki}+p^k h_i$$
595: $B$J$k7A$r2>Dj$9$k$H(B,
596: $$\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}}$$
597: $B0lJ}(B, $f \equiv \prod_i f_{ki} \bmod {p^k}$ $B$h$j(B,
598: $$f = \prod_i f_{ki} + p^k h \bmod {p^{k+1}}$$
599: $B$H=q$1$k(B.
600: $B$h$C$F(B,
601: $$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$$
602: $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
603: $B$r<($;$P$h$$(B. $B$3$l$O(B, $BL?Bj(B \ref{exteuc} $B$K$h$j8@$($k(B. \qed
604:
605: \begin{pr}
606: $f \in \Z[x], p \in \N$ $B$OAG?t(B,
607: $$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$$
608: $B$H$9$k(B. $B$3$N;~(B,
609: $f \equiv gh \equiv g'h' \bmod {p^k}$ $B$+$D(B $g \equiv g' \equiv g_0 \bmod p,$
610: $\deg(g) = \deg(g') = \deg(g_0), \quad \deg(h) = \deg(h') = \deg(h_0),\quad
611: \lc(g) \equiv \lc(g') \bmod {p^k}$
612: $B$J$i$P(B, $$g \equiv g' \bmod {p^k}, \quad h \equiv h' \bmod {p^k}.$$
613: \end{pr}
614: \proof
615: $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
616: $B2>Dj$K$h$j(B,
617: $$g' - g = p^k r,\quad h' - h = p^k s$$
618: $B$H=q$1$k(B. $B0lJ}(B,
619: $gh \equiv g'h' \bmod {p^{k+1}}$ $B$+$i(B $r h_0 + s g_0 \equiv 0 \bmod p$
620: $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$
621: $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,
622: $\lc(g) \equiv \lc(g') \bmod {p^{k+1}}$ $B$h$j(B,
623: $\deg(r \bmod p) < \deg(g_0).$ $B$h$C$F(B $r \equiv 0 \bmod p$ $B$H$J$j(B,
624: $B$3$N>l9g$b(B $k+1$ $B$G@5$7$$(B. \qed
625:
626: \begin{df}
627: $f = \sum_{i=0}^n a_i x^i \in C[x]$
628: $B$KBP$7(B, $f$ $B$N%N%k%`(B $\parallel f \parallel_1$, $\parallel f \parallel_2$ $B$r(B
629: $B$=$l$>$l(B,
630: $$\parallel f \parallel_1 = \sum_{i=0}^n |a_i|, \quad
631: \parallel f \parallel_2 = \sqrt{\sum_{i=0}^n |a_i|^2}$$
632: ($|a|$ $B$O(B $a$ $B$N@dBPCM(B) $B$GDj5A$9$k(B.
633: \end{df}
634:
635: \begin{pr}(Landau-Mignotte\cite{MIG})
636: $f = \sum_{i=0}^n a_i x^i \in \Z[x], g = \sum_{i=0}^m b_i x^i \in \Z[x]$
637: $B$H$9$k(B. $B$3$N;~(B $g|f$ $B$J$i$P(B,
638: $\parallel g\parallel_1 \le |b_m/a_n|2^m \parallel f\parallel_2$
639: \end{pr}
640:
641: \begin{co}
642: \label{mig}
643: $f, g \in \Z[x]$, $g|f$ $B$J$i$P(B,
644: $\parallel \lc(f)/\lc(g)\cdot g\parallel_1 \le 2^{\deg(g)} \parallel f\parallel_2$
645: \end{co}
646:
647: \begin{pr}
648: $f \in \Z[x]$ $B$,L5J?J}$J$i$P(B, $BM-8B8D$NAG?t(B $p$ $B$r=|$$$F(B
649: $\deg(f \bmod p) = \deg(f)$ $B$+$D(B $f \bmod p$ $B$OL5J?J}(B.
650: \end{pr}
651: $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
652: $B$"$k$3$H$+$iL@$i$+(B.\\
653: $B0J>e$K$h$j(B $\Z[x]$ $B$K$*$1$k0x?tJ,2r$O<!$N$h$&$K9T$J$o$l$k(B.
654:
655: \begin{al}(Zassenhaus{\rm \cite{ZASS}})
656: \label{zassenhaus}
657: \begin{tabbing}
658: Input : $f(x) \in \Z[x]$; $f$ $B$OL5J?J}(B\\
659: Output : $\{f_1,f_2,\cdots\}$ $f = f_1 f_2 \cdots$ $B$O(B $f$ $B$N4{LsJ,2r(B
660: \\
661: $p \leftarrow \deg(f) = \deg(f \bmod p)$ $B$+$D(B $f \bmod p$ $B$,L5J?J}$H$J$k$h$&$J(B $p$\\
662: $a \leftarrow f$ $B$N<g78?t(B\\
663: $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)\\
664: if $|F_1| = 1$ then return $\{f\}$\\
665: $F_1 = \{ f_{11},\cdots,f_{1m}\}$ $B$H$9$k(B. \\
666: $k \leftarrow p^k > \parallel f\parallel_2\cdot 2^{\deg(f)+1}$ $B$J$k@0?t(B\\
667: $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\\
668: Hensel $B9=@.$G5a$a$k(B\\
669: $l \leftarrow 1$\\
670: $F \leftarrow \emptyset$\\
671: while \= ( $2l \le m$ ) \{\\
672: (a)\> $S \leftarrow S \subset F_k$, $|S|=l$ $B$J$k?7$7$$ItJ,=89g(B\\
673: \> if \= $S$ $B$,B8:_$7$J$$(B then $l \leftarrow l+1$\\
674: \> else \= \{\\
675: \>\> $g \leftarrow a\cdots \prod_{s\in S}s$\\
676: (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\\
677: \> if $g|af$ \{\\
678: \>\> $g\leftarrow \pp(g)$ (primitive part),\quad $f \leftarrow f/g$,\quad
679: $F_k \leftarrow F_k \backslash S$\\
680: \> \}\\
681: \}\\
682: if ($f \neq 1$) then $F \leftarrow F \cup \{f\}$\\
683: return $F$
684: \end{tabbing}
685: \end{al}
686: \begin{pr}
687: $B%"%k%4%j%:%`(B \ref{zassenhaus} $B$O(B $f$ $B$N4{Ls0x;RJ,2r$r=PNO$9$k(B.
688: \end{pr}
689: \proof
690: (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
691: $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
692: $B$K$h$j(B, (b) $B$K$*$$$F(B
693: $$a/\lc(G)\cdot G \equiv g \bmod p^k.$$
694: $B$3$3$G(B, $B7O(B \ref{mig} $B$*$h$S(B $k$ $B$N$H$jJ}$K$h$j(B,
695: $$\parallel a/\lc(G)\cdot G\parallel_1 \le 2^{\deg(G)}\parallel f\parallel_2
696: \le 2^{\deg(f)}\parallel f\parallel_2 < p^k/2.$$
697: $B$^$?(B, $\parallel g \parallel_1\le p^k/2$ $B$h$j(B
698: $$\parallel g-a/\lc(G)\cdot G\parallel_1
699: \le \parallel g \parallel_1+\parallel a/\lc(G)\cdot G\parallel_1 < 2\cdot p^k/2=p^k.$$
700: $B0J>e$K$h$j(B, $a/\lc(G)\cdot G = g$. $B%"%k%4%j%:%`(B \ref{zassenhaus} $B$G$O(B,
701: $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
702: $B4{Ls@-$,@.$jN)$D(B. \qed
703:
704: $B$3$N%"%k%4%j%:%`$G$O(B,
705: \begin{center}
706: $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
707: \end{center}
708: $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
709: $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
710: $B3d$j@Z$k$N$G$"$k(B.
711:
712: $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
713: $B$KCm0U$9$kE@$O?tB?$/$"$k(B. $B$=$l$i$N$$$/$D$+$r=R$Y$k(B.
714:
715: \begin{enumerate}
716: \item $p$ $B$NA*Br(B
717:
718: $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
719: $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.
720: $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
721: $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
722: 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
723: $B8BBN>e$G$N0x?tJ,2r$rJ#?t2s5/F0$7(B, $B:G$b0x;R$N8D?t$,>/$J$$(B$p$ $B$rA*$V(B.
724:
725: \item Hensel $B9=@.(B
726:
727: $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
728: 1 $B<!$N%*!<%@$G$7$+A}$($J$$(B. $BFC$K(B $p$ $B$,>.$5$$>l9g(B, $BL\E*$NI>2ACM$KE~C#(B
729: $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
730: $B$2$F$$$/(B quadratic lifting $B$H$$$&%"%k%4%j%:%`$,9M0F$5$l$F$$$k(B. $B$?$@$7(B
731: $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
732: Hensel $B9=@.$7$J$1$l$P$J$i$J$$$?$a(B, $p^k$ $B$,%^%7%s@0?tDxEY$N$&$A$O(B
733: quadratic lifting $B$7(B, $B%^%7%s@0?t$r1[$($?$"$?$j$G(B linear lifting $B$K@ZBX(B
734: $B$($k$H$$$&$3$H$,9T$J$o$l$k(B.
735:
736: \item $B;n$73d$j(B
737:
738: $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
739: $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
740: $BB?9`<0;~4V7W;;NL%"%k%4%j%:%`$O(B Lenstra $BEy$K$h$j(B lattice $B%"%k%4%j%:%`$H(B
741: $B$7$FDs0F$5$l$F$$$k$,(B, $B$"$/$^$GA26a7W;;NL$K$*$1$k8zN(2=$G$"$j(B, $B$3$3$G$O(B
742: $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
743: $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,
744: \begin{center}
745: $g|f$ $B$J$i$P(B, $B@0?t(B $a$ $B$KBP$7(B $g(a) | f(a)$
746: \end{center}
747: $B$rMxMQ$7$F(B,
748: \begin{itemize}
749: \item $BDj?t9`$I$&$7$N;n$73d$j(B ($g|f$ $B$J$i$P(B $g(0) | f(0)$)
750: \item $B78?t$NOB$I$&$7$N;n$73d$j(B ($g|f$ $B$J$i$P(B $g(1) | f(1)$)
751: \end{itemize}
752: $B$J$I$K$h$kA0=hM}$,9M0F$5$l$F$*$j(B, $B$=$l$>$l8z2L$rH/4x$7$F$$$k(B.
753: \end{enumerate}
754:
755:
756: \section{$BB?JQ?tB?9`<0$N0x?tJ,2r(B, GCD, $BL5J?J}J,2r(B}
757: \subsection{$B0lHL2=$5$l$?(B Hensel $B9=@.(B}
758: 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
759: $BJ,2r(B, GCD $B$OJ#;($+$D:F5"E*$K7k$SIU$$$F$$$F(B, $B$=$NA4BNA|$rGD0.$9$k$N$OMF(B
760: $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
761: $B$N>l9g$HA4$/F1MM$K7W;;$G$-$k$,(B, $B$"$k<gJQ?t$r8GDj$7$?;~(B, 1 $BJQ?t$N;~$K$O(B
762: $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
763: $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
764: $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
765: $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
766: $B$*$h$S$=$N2~NIHG$G$"$k(B PRS $BK!$rMQ$$$l$P86M}E*$K2DG=$G$O$"$k$,(B, $B$3$NJ}(B
767: $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
768: $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
769: $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
770: $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
771: $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
772: $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
773: $BF10l$G$"$k$?$a(B, $B0x?tJ,2r$K8B$i$:(B, GCD, $BL5J?J}J,2r$K$b1~MQ$G$-$k(B.
774:
775: $B0J2<$G$O(B,
776: $$R = \Z[x_1,\cdots,x_n],\quad I = (x_2-a_2,\cdots,x_n-a_n)$$
777: ($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
778: $\phi_I : R \rightarrow \Z[x_1]$ $B$r(B
779: $$\phi_I(f) = f(x_1,a_2,\cdots,a_n)$$
780: $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
781: $B<g78?t$rI=$9$H$9$k(B.
782:
783: \begin{pr}(Moses-Yun{\rm\cite{YUN}})
784: \label{yun}
785: $f \in R, p \in \Z$ $B$OAG?t(B,
786: $$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})$$
787: $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
788: $B$N(B $k$ $B$KBP$7(B, $f_{ki} \in \Z_{p^l}[x_1,\cdots,x_n]$ $B$,B8:_$7$F(B,
789: $f \equiv \prod f_{ki} \bmod {(p^l,I^k)}$ $B$+$D(B $f_{ki} \equiv f_{1i} \bmod
790: {(p^l,I)},\quad \deg(f_{ki}) = \deg(f_{1i}).$
791: \end{pr}
792: \proof
793: $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.
794: $$f_{(k+1)i}=f_{ki}+h_i\quad (h_i \in (p^l,I^k))$$
795: $B$J$k7A$r2>Dj$9$k$H(B,
796: $$\prod_i f_{(k+1)i} \equiv \prod_i f_{ki} + \sum_i h_i\prod_{j\neq i}f_{kj}
797: \bmod {(p^l,I^{k+1})}$$
798: $B0lJ}(B, $f \equiv \prod_i f_{ki} \bmod {(p^l,I^k)}$ $B$h$j(B,
799: $$f = \prod_i f_{ki} + h\quad (h \in (p^l,I^k))$$
800: $B$H=q$1$k(B. $B$h$C$F(B,
801: $$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})}$$
802: $B$H$J$k$h$&$K(B,
803: $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
804: $B$r<($;$P$h$$(B. \\
805: $$h = \sum_{\alpha}h_{\alpha}(x_1)\prod_{j\ge 2}(x_j-a_j)^{\alpha_j} \bmod {I^{k+1}}$$
806: $$h_i = \sum_{\alpha}h_{i \alpha}(x_1)\prod_{j\ge 2}(x_j-a_j)^{\alpha_j} \bmod {I^{k+1}}$$
807: $B$H=q$/$H(B, $B3F78?t$KBP$7$F(B\\
808: $$h_{\alpha} \equiv \sum_i h_{i \alpha}\prod_{j\neq i}f_{1j} \bmod {p^l}$$
809: $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
810: $B>r7o$r9~$a$F2DG=$G$"$k(B. \qed
811:
812: \begin{pr}
813: $f_i \in \Z[x]$, $p$ $B$OAG?t(B, $p {\not|}\lc(f_i)$, $f_i
814: \bmod p$ $B$O8_$$$KAG$H$9$k(B. $B$3$N;~(B, $BG$0U$N(B $k$, $BG$0U(B
815: $B$N(B $c \in \Z[x]$$B$KBP$7(B, $c_i \in \Z[x]$ $B$,B8:_$7$F(B,
816: $$\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)$
817: $B$+$D(B, $B$3$N$h$&$J(B $c_i$ $B$O(B $p^k$ $B$rK!$H$7$F0l0UE*(B.
818: \end{pr}
819: \proof
820: $\bmod p$ $B$K$*$1$k>r7o$+$i(B, $e_{1i} \in GF(p)[x]$ $B$,B8:_$7$F(B,
821: $\sum_i e_{1i} f_i \equiv 1 \bmod p.$
822: $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
823: $\sum_i e_{ki} f_i \equiv 1 \bmod {p^k}.$
824: $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
825: $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$
826: $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
827: $\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
828: \deg(f_i)$$B$J$i$P(B, $\deg(c_1)+\sum_{j\neq 1}\deg(f_i) < \sum_i \deg(f_i)$
829: $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
830: $BK!$G>ZL@$G$-$k(B. \qed
831:
832: \begin{pr}
833: {\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
834: $f_{ki}$ $B$O(B $(p^l,I^k)$ $B$rK!$H$7$F0l0UE*$G$"$k(B.
835: \end{pr}
836: $B>ZL@$O(B, $BA0Fs$D$NL?Bj$rMQ$$$l$P(B, $B0lJQ?t$N>l9g$HF1MM$K$G$-$k(B.
837:
838: \begin{pr}(Gel'fond{\rm\cite{GEL}})
839: $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
840: $|f$ $B$N0x;R$N78?t(B$|$ $\le e^{d_1+\cdots+d_n}\cdot \max$($|f$ $B$N78?t(B$|$).
841: \end{pr}
842:
843: \begin{pr}
844: $f \in R$ $B$,L5J?J}$J$i$P(B, $BL58B$KB?$/$N(B $I$ $B$KBP$7(B
845: $\lc(\phi_I(f)) \neq 0$ $B$+$D(B $\phi_I(f)$ $B$OL5J?J}(B.
846: \end{pr}
847: $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
848: $B$$$3$H$HF1CM$G$"$k$3$H$+$iL@$i$+(B.
849:
850: \subsection{$BB?JQ?tB?9`<0$N0x?tJ,2r(B}
851: $B0J>e$K$h$j(B, $R$ $B$K$*$1$k0x?tJ,2r$O<!$N$h$&$K9T$J$o$l$k(B.
852:
853: \begin{al}
854: \begin{tabbing}
855: \\
856: Input : $f(x) \in R$; $f$ $B$OL5J?J}$+$D(B $x_1$ $B$K$D$$$F86;OE*(B\\
857: Output : $\{f_1,f_2,\cdots\}$ $f = f_1 f_2 \cdots$ $B$O(B $f$ $B$N4{LsJ,2r(B\\
858: $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
859: $BL5J?J}$J(B\\
860: $a=(a_2,\cdots,a_n) \in \Z^{n-1}$\\
861: $F_1 \leftarrow \{f_{1i}\} \leftarrow f_a(x_1)$ $B$N(B $\Z$ $B>e$G$N4{LsJ,2r(B\\
862: if $|F_1| = 1$ then return $\{f\}$\\
863: $p \leftarrow f_a(x_1)$ $B$N4{LsJ,2r$GMQ$$$?(B $p$\\
864: $F_1 = \{f_{11},\cdots,f_{1m}\}$ $B$H$9$k(B\\
865:
866: $l \leftarrow 1$\\
867: $F \leftarrow \emptyset$\\
868: while \= ( $2l \le m$ ) \{\\
869: \> $S \leftarrow S \subset F_1$, $|S|=l$ $B$J$k?7$7$$ItJ,=89g(B\\
870: \> if \= $S$ $B$,B8:_$7$J$$(B then $l \leftarrow l+1$\\
871: \> else \= \{\\
872: \>\> $g_1 \leftarrow \prod_{s\in S}s$,\quad $h_1 \leftarrow \prod_{s\in F_1 \backslash S}s$\\
873: \>\> $g_1 \leftarrow \lc(f_a)/\lc(g_1)\cdot g_1$,\quad $\lc(g_1) \leftarrow \lc(f)$\\
874: \>\> $h_1 \leftarrow \lc(f_a)/\lc(h_1)\cdot h_1$,\quad $\lc(h_1) \leftarrow \lc(f)$\\
875: \>\> $B \leftarrow \lc(f)f$ $B$N(B Gel'fond bound\\
876: \>\> $l \leftarrow p^l > 2B$ $B$J$k@0?t(B $l$\\
877: \>\> $k \leftarrow f$ $B$N(B $x_2,\cdots,x_n$ $B$K4X$9$kA4<!?t(B $+1$\\
878: \>\> $\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\\
879: \>\> Hensel $B9=@.$G5a$a$k(B.\\
880: \>\> $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\\
881: \>\> if\= $g|\lc(f)f$ \{\\
882: \>\>\> $g\leftarrow \pp(g)$ (primitive part),\quad $f \leftarrow f/g$,\quad
883: $F_1 \leftarrow F_1 \backslash S$\\
884: \>\> \}\\
885: \> \}\\
886: \}\\
887: if ($f \neq 1$) then $F \leftarrow F \cup \{f\}$\\
888: return $F$
889: \end{tabbing}
890: \end{al}
891:
892: $B$3$N%"%k%4%j%:%`$r<B8=$9$k>l9g(B, $B0lJQ?t$N>l9g$H$O0[$J$kLdBj$,$$$/$D$+@8$:$k(B.
893:
894: \begin{enumerate}
895: \item {\bf $BHsNmBeF~LdBj(B}
896:
897: 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
898: $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
899: $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
900: $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
901: $B78?t$r7W;;$9$kI,MW$,$"$k(B. $B85$NB?9`<0$,AB$G$bJ?9T0\F0$r9T$J$&$HL)$JB?9`<0(B
902: $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
903: $B>r7o$rK~$?$9$?$a$K$d$`$J$/(B 0 $B$G$J$$(B $a_i$ $B$rMQ$$$k$3$H$,$"$jF@$k(B.
904: \item {\bf $B<g78?tLdBj(B}
905:
906: $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
907: $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
908: $B9=@.$N:]$K(B, $BITI,MW$J9`$NA}2C$r2!$($i$l$k$,(B, $B<g78?t$,Bg$-$JB?9`<0$N>l9g(B
909: $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
910: $BBP1~$9$k<g78?t$r2?$i$+$NJ}K!$K$h$j7h$a$F$7$^$&J}K!$,(B Wang \cite{WANG} $B$K(B
911: $B$h$jDs0F$5$l$F$$$k(B.
912: \item {\bf $B%K%;0x;R$NLdBj(B}
913:
914: $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
915: $B<j=g$K$7$F$"$k(B. $B$3$l$O(B,
916: \begin{itemize}
917: \item $BB?$/$N0x;R$rF1;~$K(B Hensel $B9=@.$9$k>l9g(B, $B<g78?t$r%b%K%C%/$N$^$^(B
918: $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
919: $BB?9`<0$N<g78?t$K9g$o$;$k$3$H$O(B, Hensel $B9=@.$NCJ?t$NA}2C$K$D$J$,$k(B.
920: \item $B8uJd$,??$N0x;R$N%$%a!<%8$G$"$k$3$H$r4|BT$7$F$$$k(B. $B??$N0x;R$N(B
921: $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
922: $B$G;n$73d$j$r$7$F(B Hensel $B9=@.$r@Z$j>e$2$k$3$H$b$G$-$k(B.
923: \end{itemize}
924: $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
925: $BF@$i$l$kCJ?t$^$G(B Hensel $B9=@.$,?J9T$7(B, $B5pBg$J8uJd$r@8@.$7$F$7$^$&(B.
926: $B$3$l$O(B, $BBg$-$JL5BL$H$J$k$?$a(B, $B3FJQ?t$N<!?t$r>o$K%A%'%C%/$7$F(B,
927: $B8uJd$N$I$l$+$NJQ?t$K4X$9$k<!?t$,M?$($i$l$?B?9`<0$N<!?t$r1[$($?;~E@$G(B
928: Hensel $B9=@.$rCfCG$9$k$J$I$NA`:n$,I,MW$H$J$k(B.
929: \end{enumerate}
930: $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
931: $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
932: $B0x;R$N=P8=$N3NN($rBg$-$9$k(B. $B$3$N$?$a(B, $BJQ?t$N8D?t$r0l$D$:$DMn$7$F$$$/(B
933: 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
934: $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
935: $B0l$DA}$d$7$F(B Hensel $B9=@.$r9T$J$&:](B, $B%K%;0x;R$O<!Bh$KGS=|$5$l$F$$$/$?$a(B,
936: $B%K%;0x;R$KBP$7$F6/$$%"%k%4%j%:%`$H$J$k(B.
937:
938: \subsection{$BB?JQ?tB?9`<0$NL5J?J}J,2r5Z$S(B GCD}
939: \label{wangtrager}
940: $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
941: $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
942: \ref{yun} $B$N(B$f_{1i}$) $B$,(B, $BK!(B $p$ $B$G8_$$$KAG$G$"$k$H$$$&>r7o$G$"$k(B.
943: $\GCD(g,h)$ $B$N7W;;$K$*$$$F$O(B, $f_{1i}$ $B$H$7$F(B
944: $$\{\GCD(\phi_I(g),\phi_I(h)),\phi_I(g)/\GCD(\phi_I(g),\phi_I(h))\}$$
945: $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
946: $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')$
947: $B$r5a$a$k:]$KI,MW$J(B $g_1=\GCD(g,g')$ $B$O(B,
948: $$\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
949: $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
950: $\GCD(g_s,h)$ $B$O(B $B0lHL2=$5$l$?(B Hensel $B9=@.$G7W;;$G$-(B, $\GCD(g,h)$ $B$N4{Ls(B
951: $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
952: $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
953: $B$l$?(B Hensel $B9=@.$G5a$a$k$3$H$,$G$-$k(B.
954:
955: $B$7$+$7(B, $BL5J?J}J,2r$K$*$$$F(B, $g$ $B$,=EJ#EY$NBg$-$$0x;R$r4^$s$G$$$k$H$-(B,
956: $g_s$ $B$N7W;;$KB?$/$N;~4V$,$+$+$k(B. $B$3$l$rHr$1$k$?$a(B, $B=EJ#EY$N:G$b9b$$(B
957: $B0x;R$+$i5a$a$F$$$/J}K!$,9M0F$5$l$?(B. $B$3$l$O(B, $B<!$NL?Bj$K4p$E$/(B.
958:
959: \begin{pr}
960: $f \in K[x]$ $B$KBP$7(B,
961: $f = hg^e \quad (h,g \in K[x]),\quad \GCD(h,g)=1$ $B$+$D(B $g$ $B$,L5J?J}(B
962: $B$J$i$P(B $g|(d/dx)^{e-1}f$ $B$G(B
963: $$\GCD(g,((d/dx)^{e-1}f)/g) = 1$$
964: \end{pr}
965: \proof
966: $e = 1$ $B$N$H$-L@$i$+(B. $e\ge 2$ $B$N$H$-(B,
967: $(d/dx)^{e-1}(g^e) \equiv e!gg'^{e-1} \bmod{g^2}$
968: $B$,$$$($k(B. $B$h$C$F(B,
969: $(d/dx)^{e-1}f \equiv h(d/dx)^{e-1}(g^e) \equiv e!hgg'^{e-1} \bmod{g^2}$
970: $B$H$J$j(B, $g|(d/dx)^{e-1}f$. $B$5$i$K(B,
971: $((d/dx)^{e-1}f)/g \equiv e!hg'^{e-1} \bmod{g}$
972: $B$G(B, $\GCD(g,h) = 1$, $\GCD(g,g')=1$ $B$h$j(B
973: $\GCD(g,((d/dx)^{e-1}f)/g) = 1.$ \qed
974:
975: \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
976: $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,
977: $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
978: $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
979: $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.
980: $BBEEv$JCM$,B8:_$9$k$3$H$O(B, $BL5J?J}$JB?JQ?tB?9`<0$KBP$9$kBEEv$JBeF~CM$NB8:_(B
981: $B$HF1MM$K8@$($k(B.
982: $B$3$NJ}K!$N$h$$E@$O(B,
983: \begin{itemize}
984: \item
985: ($B=EJ#EY(B -1) $B$@$1B?9`<0$N<!?t$,Mn$;$k(B
986: \item
987: $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
988: $B$a$k>l9g$KHf3S$7$F7W;;$N<j4V$r8:$i$9$3$H$,$G$-$k(B
989: \item
990: $BA4BN$KBP$7$FBEEv$G$J$$BeF~$G$b(B, $B=EJ#EY:GBg$N0x;R$K$O1F6A$,$J$$>l9g$,$"$k(B.
991: \item
992: $B$"$kB?9`<0$NQQ$K$J$C$F$$$k>l9g$K9bB.$KJ,2r$G$-$k(B.
993: \end{itemize}
994: $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.
995: $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
996: $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
997: $B$O(B, \cite{SQFR} $B$G$OCf9q>jM>DjM}$K$h$kJ}K!$rDs0F$7$F$$$k$,(B, Hensel $B9=@.(B
998: $B$K$h$k$b$N$b2DG=$G$"$k(B.
999:
1000: $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
1001: $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
1002: $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
1003: $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
1004: $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
1005: $B$H$J$j(B, $BEvA3(B debug $B$b:$Fq$J$b$N$K$J$k(B.
1006:
1007: \section{$BBe?tBN>e$N0x?tJ,2r(B}
1008: $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
1009: $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
1010: $BK!$G$"$k(B. $K=\Q(\alpha)$ $B$H$$$&C13HBg$KBP$7$F$O(B, $B$3$NB>$K(B, Hensel $B9=@.(B
1011: $B$rMQ$$$kJ}K!$,$$$/$D$+Ds0F$5$l$F$$$k$,$3$3$G$O=R$Y$J$$(B. Trager $B$NJ}K!(B
1012: $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,
1013: $\Q$ $B>e$N0x?tJ,2r$5$(40Hw$7$F$$$l$P(B, $K=\Q(\alpha_1,\cdots,\alpha_r)$ $B>e(B
1014: $B$G$N0x?tJ,2r$,2DG=$K$J$k(B.
1015:
1016: $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$
1017: $B$J$k4{LsB?9`<0(B, $\alpha$ $B$r(B $g$ $B$N0l$D$N:,$H$9$k(B.
1018: $K(\alpha)=K[\alpha]=K[t]/(g)$ $B$G$"$k(B. $L\supset K$ $B$r(B $g$ $B$N:G>.J,2r(B
1019: $BBN$H$9$k(B. $\alpha_1=\alpha,\alpha_2,\cdots,\alpha_m$ $B$r(B $g$ $B$NAj0[$J$k(B
1020: $B:,$H$9$k$H(B, $L=K(\alpha_1,\cdots,\alpha_m)$ $B$H$+$1$k(B.
1021:
1022: \begin{df}
1023: $f\in K(\alpha)[x]$ $B$KBP$7(B, $\Norm(f)$ $B$r(B
1024: $$\Norm(f) = \prod_i f(x,\alpha_i)$$
1025: $B$GDj5A$9$k(B. $L/K$ $B$N(B $\Norm$ $B$N@-<A(B
1026: $B$K$h$j(B, $\Norm(f) \in K[x]$. $B$^$?(B, $$\Norm(f) = \res_t(f(x,t),g(t)).$$
1027: \end{df}
1028:
1029: \begin{pr}
1030: $f\in K(\alpha)[x]$ $B$,4{Ls$J$i$P(B, $B$"$k4{LsB?9`<0(B $h \in K[x]$
1031: $B$,B8:_$7$F(B, $$\Norm(f) = h^l.$$
1032: \end{pr}
1033: \proof
1034: $\Norm(f) = ab,\quad a,b \in K[x],\quad \GCD(a,b)=1$ $B$H=q$1$?$H$9$k(B. $f
1035: | \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
1036: $B;~(B $$\Norm(f)|\Norm(a) = a^m.$$$B$h$C$F(B $\GCD(\Norm(f),b) = 1$ $B$H$J$j(B,
1037: $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
1038: $B;R$r4^$_F@$J$$(B. \qed
1039:
1040: \begin{co}
1041: $f\in K(\alpha)[x]$ $B$,L5J?J}$H$9$k;~(B, $\Norm(f)$ $B$,L5J?J}$J$i$P(B,
1042: $\Norm(f) = \prod f_i$
1043: $B$r(B $K[x]$ $B$K$*$1$k4{LsJ,2r$H$9$k$H$-(B,
1044: $f = \prod \GCD(f,f_i)$
1045: $B$O(B $f$ $B$N(B $K(\alpha)[x]$ $B$K$*$1$k4{LsJ,2r$rM?$($k(B.
1046: \end{co}
1047: \proof $h$ $B$r(B $f$ $B$N(B $K(\alpha)[x]$ $B$K$*$1$k4{Ls0x;R$H$9$k(B.
1048: $h$ $B$O$"$k(B $f_i$ $B$r3d$j@Z$k(B.
1049: $\Norm(h)$ $B$O(B $K[x]$ $B$N4{LsB?9`<0$NQQ$G(B, $\Norm(h)$ $B$OL5J?J}$J(B
1050: $\Norm(f)$ $B$r3d$j@Z$k$+$i(B, $\Norm(h)$ $B<+?H$,(B $\Norm(f)$ $B$N4{Ls0x;R(B.
1051: $\Norm(h)$ $B$O(B $\Norm(f_i)$ $B$N0x;R$G$b$"$k$+$i(B,
1052: $f_i = \Norm(h).$
1053: $B:#(B, $h$ $B$H0[$J$k0x;R(B $h_1$ $B$,(B $f_i$ $B$r3d$l$P(B,
1054: $BF1MM$K(B $f_i = \Norm(h_1)$. $hh_1|f$ $B$h$j(B
1055: $$\Norm(hh_1)={f_i}^2|\Norm(f).$$
1056: $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
1057: $B4{Ls0x;R$r4^$`(B. \qed
1058:
1059: $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
1060: $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
1061: $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
1062: $B$o$+$k(B.
1063:
1064: \begin{pr}
1065: $f\in K(\alpha)[x]$ $B$,L5J?J}$J$i$P(B, $\Norm(f(x-s\alpha))$ $B$,L5J?J}$H(B
1066: $B$J$i$J$$(B $s \in K$ $B$OM-8B8D(B.
1067: \end{pr}
1068: \proof $f$ $B$N:,$r(B $\beta_1,\cdots,\beta_m$ $B$H$9$k$H(B, $B2>Dj$h$j$3$l(B
1069: $B$i$OAj0[$J$k(B. $B$9$k$H(B, $f(x-s\alpha_i)$ $B$N:,$O(B,
1070: $$\beta_1+s\alpha_i,\cdots,\beta_m+s\alpha_i$$
1071: $B$H$J$k(B. $B$3$l$h$j(B $\Norm(f(x-s\alpha))$ $B$,L5J?J}$G$J$$$N$O(B,
1072: $B$"$k(B $i, j, k, l$ $B$KBP$7$F(B,
1073: $$\beta_j+s\alpha_i = \beta_k+s\alpha_l$$
1074: $B$N>l9g$K8B$k(B.
1075: $B$3$N$h$&$J>r7o$rK~$?$9(B $s$ $B$OM-8B8D$7$+$J$$(B. \qed
1076:
1077: $B0J>e$K$h$j(B, $B<!$N%"%k%4%j%:%`$,F@$i$l$k(B.
1078:
1079: \begin{al}
1080: \label{trager}
1081: \begin{tabbing}
1082: \\
1083: Input : $BL5J?J}$J(B $f(x,\alpha)\in K(\alpha)[x]$, $s \in \Z$\\
1084: Output : $f$ $B$N(B $K(\alpha)$ $B>e$N4{Ls0x;R(B $\{f_1,\cdots,f_r\}$\\
1085: again:\\
1086: $r \leftarrow \res_t(f(x-st,t),g(t))$\\
1087: if \= ( $r$ $B$,L5J?J}$G$J$$(B ) then\\
1088: \> $s \leftarrow s+1$; goto again\\
1089: $r(x) = \prod r_i(x)$ : $r$ $B$N(B $K$ $B>e$G$N4{LsJ,2r(B\\
1090: $z \leftarrow f$\\
1091: for each $i$ do \{\\
1092: \> $f_i \leftarrow \GCD(h(x+s\alpha),z(x,\alpha))$\\
1093: \> $t \leftarrow z/f_i$\\
1094: \}
1095: \end{tabbing}
1096: \end{al}
1097: $B$3$N%"%k%4%j%:%`$K$*$$$F(B, $B%\%H%k%M%C%/$H$J$jF@$kItJ,$,?tB?$/$"$k(B.
1098: \begin{enumerate}
1099: \item $B=*7k<0$N7W;;(B
1100:
1101: $B=*7k<0$N7W;;$O(B, $BItJ,=*7k<0(B, $B9TNs<0$N(B modular $B1i;;$J$I$rAH$_9g$o$;$F9T$J(B
1102: $B$&$,(B, $B<B:]$N7W;;;~4V$rH?1G$9$k7W;;NL$,M?$($i$l$F$$$J$$$?$a(B, $B%"%k%4%j%:(B
1103: $B%`$NA*Br$,:$Fq$G$"$k(B. $B$^$?(B, $B$$$:$l$K$7$F$b(B, $B=*7k<0$N7W;;$O0lHL$K;~4V$,(B
1104: $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
1105: $BBg$-$5$OLdBj$G$"$k(B.
1106:
1107: \item $K$ $B>e$G$N4{LsJ,2r(B
1108:
1109: $K$ $B$,$^$?$"$k3HBgBN$K$J$C$F$$$k>l9g$K$O$3$N%"%k%4%j%:%`$,:F5"E*$K(B
1110: $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
1111: $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
1112: $\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
1113: $B$NLdBj$,$"$k(B.
1114:
1115: \item $K(\alpha)$ $B>e$G$N(B GCD $B7W;;(B
1116:
1117: $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
1118: $B$G$"$k(B. $BFC$K(B, Euclid $B8_=|K!$rMQ$$$k>l9g(B, $BCf4V<0KDD%$O(B, $BDj5AB?9`<0(B $g$
1119: $B$,Bg$-$$>l9g(B, $B6K$a$F7c$7$$(B. $B$3$l$r$5$1$k$?$a$$$/$D$+$N(B modular $B7W;;K!(B
1120: $B$,Ds0F$5$l$F$$$k(B.
1121: \end{enumerate}
1122:
1123: $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
1124: $B$G$J$$%N%k%`$rMxMQ$9$k$3$H$K$h$j(B, $B$"$kDxEY2sHr$G$-$k(B.
1125:
1126: \begin{pr}
1127: $f \in K(\alpha)[x]$ $B$,L5J?J}(B,
1128: $$\Norm(f) = \prod_i {f_i}^{n_i}$$
1129: ($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,
1130: $\GCD(f,f_i)$ $B$O(B $f$ $B$NDj?t$G$J$$0x;R$G(B,
1131: $$f = \prod \GCD(f,f_i).$$
1132: $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)$
1133: $B$O4{Ls(B.
1134: \end{pr}
1135: \proof
1136: $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
1137: $h | \prod \GCD(f,f_i).$
1138: $f$ $B$OL5J?J}$h$j(B
1139: $f | \prod \GCD(f,f_i).$
1140: $\GCD(f,f_i)$ $B$O8_$$$KAG$h$j(B,
1141: $f = \prod \GCD(f,f_i).$
1142: $B$5$F(B, $f$ $B$N(B
1143: $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,
1144: $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
1145: $B$"$k(B $f$ $B$N4{Ls0x;R$r4^$`$N$G(B, $\GCD(f,f_i)$ $B$ODj?t$G$J$$(B.
1146: $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
1147: $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
1148: $h$ $B0J30$N0x;R$r4^$^$J$$(B \qed
1149:
1150: $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
1151: $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
1152: $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
1153: $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,
1154: $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
1155: $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$
1156: $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
1157: $B0x?tJ,2r$N7W;;;~4V$bC;=L$G$-$k(B. $B$3$N2~NI$r:N$jF~$l$?%"%k%4%j%:%`$r<!$K(B
1158: $B<($9(B.
1159:
1160: \begin{al}
1161: \label{modtrager}
1162: \begin{tabbing}
1163: \\
1164: Input : $BL5J?J}$J(B $f(x,\alpha)\in K(\alpha)[x]$, $s \in \Z$\\
1165: Output : $f$ $B$N(B $K(\alpha)$ $B>e$N4{Ls0x;R(B $\{f_1,\cdots,f_r\}$\\
1166: $r \leftarrow \res_t(f(x-st,t),g(t))$\\
1167: $r(x) = \prod r_i(x)^{m_i}$ : $r$ $B$N(B $K$ $B>e$G$N4{LsJ,2r(B\\
1168: $z \leftarrow f$\\
1169: for \= each $i$ do \{\\
1170: \> $g_i \leftarrow \GCD(r_i(x+s\alpha),z(x,\alpha))$\\
1171: \> if $m_i = 1$ then $g_i$ $B$O4{Ls(B\\
1172: \> else $(g_i,s+1)$ $B$K$3$N%"%k%4%j%:%`$rE,MQ(B\\
1173: \> $t \leftarrow z/g_i$\\
1174: \}
1175: \end{tabbing}
1176: \end{al}
1177:
1178: \begin{ex}
1179: \cite{ABBOTT}
1180: \begin{eqnarray*}
1181: f(x) &=& x^{16}-136x^{14}+6476x^{12}-141912x^{10}+1513334x^8-7453176x^6+13950764x^4\\
1182: & & -5596840x^2+46225
1183: \end{eqnarray*}
1184: $f(x)$ $B$O(B $\alpha = \sqrt{2}+\sqrt{3}+\sqrt{5}+\sqrt{7}$ $B$N(B $\Q$ $B>e$N(B
1185: $B:G>.B?9`<0$G$"$k(B. $\Q(\alpha)/\Q$ $B$O%,%m%"3HBg$G$"$j(B, $f(x)$ $B$O(B
1186: $\Q(\alpha)$$B>e0l<!<0$N@Q$KJ,2r$9$k(B. $B$3$N0x?tJ,2r$r%"%k%4%j%:%`(B
1187: \ref{trager} $B$G5a$a$k>l9g(B, $F(x)=\Norm(f(x-s\alpha))$ $B$,L5J?J}$H$J$k(B
1188: $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
1189: $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.
1190: $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
1191: (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
1192: $B$KAH9g$;GzH/$r5/$3$7$F$$$F7W;;IT2DG=$G$"$k(B. $B0lJ}$G(B, $BNc$($P(B $s=-1$ $B$N>l(B
1193: $B9g(B $F(x)$ $B$OL5J?J}$K$J$i$J$$$,(B, 16 $B8D$N0[$J$k4{Ls0x;R$,L5J?J}J,2r(B
1194: $B$*$h$S$=$l$KB3$/4{Ls0x;RJ,2r$K$h$jMF0W$KF@$i$l$k(B.
1195: \begin{eqnarray*}
1196: F(x) &=& x^{16} (x^2-28)^8 (x^2-20)^8 (x^2-8)^8 (x^2-12)^8\\
1197: & & \cdot (x^4-64x^2+64)^4 (x^4-40x^2+16)^4\\
1198: & & \cdot (x^4-80x^2+256)^4 (x^4-56x^2+144)^4\\
1199: & & \cdot (x^4-72x^2+400)^4 (x^4-96x^2+64)^4\\
1200: & & \cdot (x^8-240x^6+12512x^4-203520x^2+891136)^2\\
1201: & & \cdot (x^8-192x^6+8576x^4-110592x^2+102400)^2\\
1202: & & \cdot (x^8-224x^6+11264x^4-143360x^2+409600)^2\\
1203: & & \cdot (x^8-160x^6+5632x^4-61440x^2+147456)^2\\
1204: & & \cdot (x^{16}-544x^{14}+103616x^{12}-9082368x^{10}+387413504x^8-7632052224x^6\\
1205: & & +57142329344x^4-91698626560x^2+3029401600)
1206: \end{eqnarray*}
1207: $B$3$l$i$N3F0x;R$+$i(B $f(x)$ $B$NA4$F$N0l<!0x;R$,F@$i$l$k(B.
1208: $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
1209: $BBN>e$G0x?tJ,2r$9$k>l9g$K(B
1210: $B%"%k%4%j%:%`(B \ref{modtrager} $B$,M-8z$H$J$k>l9g$,$"$k(B.
1211: \end{ex}
1212:
1213: \section{$B1~MQ(B --- $BM-M}4X?t$NITDj@QJ,(B}
1214: $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
1215: $B$GI=<($9$kJ}K!$K$D$$$F=R$Y$k(B.
1216:
1217: $B0lHL$K(B, $BM-M}4X?t(B $f(x)=n(x)/d(x)$ ($n,d \in \Q[x]$) $B$NITDj@QJ,$O(B,
1218: $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
1219: 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.
1220: $B$^$?(B, $BITDj@QJ,<+BN$K(B, $d$ $B$NJ,2r$K$h$j8=$l$?Be?tE*?t$,8=$l$k$H$O(B
1221: $B8B$i$J$$(B.
1222: \begin{ex}
1223: $f=d'/d$ $B$J$i$P(B $\displaystyle \int f dx = \log d.$
1224: \end{ex}
1225: $B$3$N$3$H$+$i(B, $B:G>.$NBe?tE*?t$NE:2C$GITDj@QJ,$rI=<($9$k$3$H$r9M$($k(B.
1226:
1227: \subsection{$BM-M}ItJ,$N7W;;(B}
1228:
1229: $f=n/d$, $n,d \in \Q[x]$ $B$H$9$k(B. $B$b$7(B $\deg(n)\ge \deg(d)$ $B$J$i$P(B,
1230: $$n = qd+r, \quad q,d \in \Q[x], \deg(r) < \deg(d)$$
1231: $B$K$h$j(B, $f=q+r/d$ $B$H=q$1$k(B. $B$3$N$H$-(B $\int f dx = \int q dx + \int r/d dx$
1232: $B$G(B, $BB?9`<0$NITDj@QJ,$O<+L@$@$+$i(B, $B$"$i$+$8$a(B $\deg(n) < \deg(d)$ $B$H$7$F$h$$(B.
1233:
1234: \begin{pr}
1235: $\deg(n)<\deg(d)$ $B$H$9$k(B. $d_r = \GCD(d,d')$, $d_l = d/d_r$ $B$H$*$/$H(B,
1236: $\deg(n_r)<\deg(d_r)$, $\deg(n_l)<\deg(d_l)$ $B$J$k(B $n_r, n_l \in \Q[x]$ $B$,0l0U(B
1237: $BE*$KB8:_$7$F(B,
1238: $$\int {n\over d} dx = {{n_r}\over {d_r}} + \int {{n_l}\over{d_l}} dx$$
1239: \end{pr}
1240: \proof
1241: $d=\prod_i d_i^i$ $B$J$kL5J?J}J,2r$KBP1~$7$F(B,
1242: $${n\over d} = \sum_i \sum_j {{n_{ij}}\over{d_i^j}}\quad (\deg(r_{ij}) < \deg(d_i))$$
1243: $B$J$kItJ,J,?tJ,2r$,L?Bj(B \ref{parfrac} $B$K$h$jB8:_$9$k(B.
1244: $d_r=\prod_i d_i^{i-1}$, $d_l=\prod_i d_i$ $B$G$"$k(B.
1245: $d_i$ $B$OL5J?J}$@$+$i(B, $\GCD(d_i,d_i')=1.$
1246: $B$h$C$F(B, $B3F(B $n_{ij}$ $B$KBP$7(B, $s_{ij}, t_{ij} \in \Q[x]$
1247: ($\deg(s_{ij})< \deg(d_i)-1$, $\deg(t_{ij})< \deg(d_i)$) $B$,B8:_$7$F(B,
1248: $$s_{ij}d_i+t_{ij}d_i'=n_{ij}.$$
1249: $B$3$l$rMQ$$$F(B, $j>1$ $B$N$H$-(B
1250: $$\int {{n_{ij}}\over{d_i^j}} dx = \int {{s_{ij}}\over {d_i^{j-1}}}dx
1251: + \int {{t_{ij}d_i'}\over {d_i^j}}dx$$
1252: $B$3$3$G(B, $$({1\over {1-j}}\cdot {1\over{d^{j-1}}})'={{d_i'}\over {d_i^j}}$$
1253: $B$h$j(B,
1254: $$\int {{t_{ij}d_i'}\over {d_i^j}}dx= {1\over {1-j}}\cdot {1\over{d_i^{j-1}}}\cdot t_{ij} -
1255: \int {1\over {1-j}}\cdot {1\over{d_i^{j-1}}} t_{ij}' dx.$$
1256: $B$h$C$F(B
1257: $$\int {{n_{ij}}\over{d_i^j}} dx = {t_{ij}\over {(1-j)d_i^{j-1}}}
1258: +\int {{s_{ij}+{{t_{ij}'}\over{j-1}}}\over {d_i^{j-1}}} dx$$
1259: $\deg({s_{ij}+{{t_{ij}'}\over{j-1}}}) < \deg(d_i)-1$ $B$h$j(B,
1260: $B$3$N@QJ,$NBh(B 2 $B9`$r(B $\int {{n_{i,j-1}}\over{d_i^{j-1}}}dx$ $B$K2C$($F$b(B,
1261: $BJ,;R$N<!?t$OA}Bg$7$J$$(B. $B$h$C$F(B, $B$3$NA`:n$r(B $j>1$ $B$J$k9`$KBP$7$F7+$jJV$9(B
1262: $B$3$H$K$h$j(B,
1263: $$\int {n\over d}dx = \sum_i\sum_{j>1}{t_{ij}\over {(1-j)d_i^{j-1}}}
1264: +\sum_i \int {{u_i}\over {d_i}} dx \quad (\deg(u_i)<\deg(d_i))$$
1265: $B$J$k7A$KJQ7A$G$-$k(B. $BBh(B 1 $B9`(B, $BBh(B 2 $B9`$NHd@QJ,4X?t$r$^$H$a$F(B
1266: $B$=$l$>$l(B ${{n_r}\over {d_r}}$, ${{n_l}\over{d_l}}$ $B$H$*$1$P<!?t$N(B
1267: $B>r7o$rK~$?$9(B. $B0l0U@-$OL@$i$+(B. \qed
1268:
1269: $B$3$NL?Bj$GJ]>Z$5$l$?(B $n_r$, $n_l$ $B$O(B, $BL$Dj78?tK!$G7hDj$9$k$3$H$,$G$-$k(B.
1270:
1271: \begin{al}
1272: \begin{tabbing}
1273: \\
1274: Input: $f(x)=n(x)/d(x)\in \Q(x)$, $\deg(n)<\deg(d)$\\
1275: Output: $\displaystyle \int f(x)dx = {{n_r(x)}\over{d_r(x)}}+\int {{n_l(x)}\over{d_l(x)}}dx$, $d_l$ $B$OL5J?J}$G(B $n_r, d_r, n_l, d_l \in \Q[x]$ $B$J$kJ,2r(B\\
1276: $B$?$@$7(B $\deg(n_r)<\deg(d_r)$, $\deg(n_l)<\deg(d_l)$\\
1277: $d_r \leftarrow \GCD(d,d')$, \quad $d_l \leftarrow d/d_r$\\
1278: $m_r \leftarrow \deg(d_r)$, \quad $m_l \leftarrow \deg(d_l)$\\
1279: $n_r \leftarrow \sum_{i=0}^{m_r-1}a_i x^i$, \quad $n_l \leftarrow \sum_{i=0}^{m_l-1}b_i x^i$\\
1280: $n=n_r'd_l-({{d_ld_r'}\over{d_r}})n_r+d_rn_l$ $B$+$i(B $a_i$, $b_i$$B$r5a$a$k(B\\
1281: return $\displaystyle \int f(x)dx =
1282: {{n_r(x)}\over{d_r(x)}}+\int {{n_l(x)}\over{d_l(x)}}dx$
1283: \end{tabbing}
1284: \end{al}
1285:
1286: \subsection{$BBP?tItJ,$N7W;;(B}
1287:
1288: $f(x)=n(x)/d(x)$, $\GCD(n,d)=1$, $\deg(n)<\deg(d)$ $B$G(B $d$ $B$OL5J?J}$H$9$k(B. $B$3$N$H$-(B
1289: $$\int f dx = \sum_i c_i\log r_i$$
1290: $B$H=q$1$k(B. $B0lHL$K(B $c_i \in \Q, r_i \in \Q[x]$ $B$H$O8B$i$:(B, $B2?$i$+$NBe?tE*?t$r4^$`(B
1291: $B2DG=@-$,$"$k$,(B, $B$3$NBe?t3HBg$r:G>.8B$K$9$k$h$&$JI=<($r5a$a$?$$(B.
1292:
1.2 noro 1293: \begin{pr}(Rothstein{\rm\cite{DAV}})
1.1 noro 1294:
1295: $K$ $B$rJ#AG?tBN(B $\C$ $B$NItJ,BN$H$7(B,
1296: $f(x)=n(x)/d(x)$, $n,d \in K[x]$, $\GCD(n,d)=1$, $\deg(n)<\deg(d)$ $B$G(B $d$ $B$OL5J?J}(B, $BL5J?J}$H$9$k(B. $B$3$N$H$-(B,
1297: $$n/d = \sum_{i=1}^n c_i v_i'/v_i$$
1.2 noro 1298: $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 1299: $B$H=q$1$?$J$i$P(B, $c_i$ $B$O(B
1300: $$R(z)=\res_x(n-zd',d) \in K[z]$$
1301: $B$N:,$G(B,
1302: $$v_i=\GCD(n-c_id',d).$$
1303: \end{pr}
1304: \proof
1305: \underline{claim 1} $v=d.$
1306:
1307: $v=\prod_{i=1}^n$ $B$H$*$/$H(B,
1308: $$nv = d\sum_{i=1}^nc_iv_i'(v/v_i).$$
1.2 noro 1309: $\GCD(n,d)=1$ $B$h$j(B $d|v.$ $B0lJ}$G(B, $v_i|$$B1&JU$h$j(B, $B$b$7(B $v_i{\not |}d$
1.1 noro 1310: $B$J$i$P(B $v_i|c_iv_i'(v/v_i)$ $B$H$J$k$,(B, $B$3$l$O(B $v_i$ $B$K4X$9$k>r7o$h$jIT2DG=(B.
1311: $B$h$C$F(B $v_i|d.$ $B7k6I(B $v|d$ $B$H$J$j(B $v=d.$ \qed\\
1312: \underline{claim 2} $v_i=\GCD(n-c_id',d).$
1313:
1314: claim 1 $B$h$j(B $n = \sum_{i=1}^n c_iv_i'(v/v_i).$
1315: $d'=\sum_{i=1}^n v_i'(v/v_i)$ $B$h$j(B,
1316: $$n-c_id'=\sum_{j\neq i} (c_j-c_i)v_j'(v/v_j).$$
1317: $B$3$l$+$i(B $v_i | n-c_id'$ $B$,$o$+$k(B. $B$h$C$F(B $v_i | \GCD(n-c_id',d).$
1318: $B0lJ}$G(B, $j\neq i$ $B$N$H$-(B,
1319: $$\GCD(n-c_id',v_j)=\GCD((c_j-c_i)v_j'(v/v_j),v_j)=1$$
1320: $B$h$j(B, $v_i=\GCD(n-c_id',d).$ \qed
1321:
1322: claim 2 $B$h$j(B, $c_i$ $B$,(B $R(z)$ $B$N:,$G$J$1$l$P$J$i$J$$$3$H$b$o$+$k(B. \\
1323: \underline{claim 3} $\{c_1,\cdots,c_n\} = R(z)$ $B$N:,A4BN(B
1324:
1325: $c$ $B$,(B $R(z)$ $B$N:,$J$i$P(B, $v_0=\GCD(n-cd',d)$ $B$O<+L@$G$J$$(B $d$ $B$N0x;R(B.
1326: $B$h$C$F(B $v_0$ $B$N4{Ls0x;R(B $g$ $B$r0l$D$H$l$P(B, $B$"$k(B $v_i$ $B$,B8:_$7$F(B $g|v_i.$
1327: $$g|(n-cd')=\sum_{j=1}^n (c_j-c)v_j'(v/v_j)$$
1328: $B$h$j(B, $g|(c_i-c)v_i'(v/v_i).$ $B$3$l$O(B $c_i=c$ $B$N$H$-$N$_2DG=(B. \qed
1329:
1330: \begin{co}
1.2 noro 1331: $K$ $B$rJ#AG?tBN(B $\C$ $B$NItJ,BN$H$7(B,
1.1 noro 1332: $f(x)=n(x)/d(x)$, $n,d \in K[x]$, $\GCD(n,d)=1$, $\deg(n)<\deg(d)$ $B$G(B $d$ $B$OL5J?J}(B, $B%b%K%C%/$H$7(B,
1333: $$R(z)=\res_x(n-zd',d) \in K[z]$$
1334: $B$H$9$k(B.
1335: $K_R$ $B$r(B $R(z)$ $B$N:G>.J,2rBN$H$9$l$P(B,
1336: $K_R$ $B$,(B $\int n/d dx$ $B$rI=<($9$k$?$a$N:G>.$N(B $K$ $B$N3HBg(B.
1337: \end{co}
1338: \proof $F$ $B$r(B $K$ $B$N3HBgBN$H$7(B, $c_i \in F$, $v_i \in F[x]$ $B$K$h$k(B
1339: $n/d = \sum_i c_i v_i'/v_i$ $B$J$kI=<($r$H$k$H(B, $BBN$N3HBg$J$7$K(B, $BA0L?Bj$N(B
1340: $c_i$ $v_i$ $B$KBP$9$k>r7o$,K~$?$5$l$k$h$&$K$G$-$k(B. $B$3$N$H$-(B, $c_i$ $B$O(B
1341: $R(z)$ $B$N:,$G(B $c_i \in F$ $B$@$+$i(B, $K_R \subset F$. $K_R$ $B>e$G$3$NI=<((B
1342: $B$,$G$-$k$3$H$OA0L?Bj$GJ]>Z$5$l$F$$$k(B. \qed
1343:
1344:
1345:
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>