Return to factor.tex CVS log

Up to [local] / OpenXM / doc / compalg

Updated the description of F_4.
Added references on the knapsack factorization algorithm.

%$OpenXM: OpenXM/doc/compalg/factor.tex,v 1.6 2001/02/27 08:07:24 noro Exp $
\chapter{$BB?9`<0$N0x?tJ,2r(B}

\section{$BM-8BBN(B}
$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, 
$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
$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
$B4X$9$k7W;;$N$h$&$K(B, $BM-8BBN$K$*$1$k7W;;$=$N$b$N$,BP>]$H$J$C$F$$$k>l9g$b(B
$B$"$k(B.
$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
$B7A$G=R$Y$k(B.

\begin{df}
$BM-8B8D$N85$+$i$J$kBN$rM-8BBN$H8F$V(B. 
$q$ $B8D$N85$+$i$J$kBN$r(B $GF(q)$ $B$H=q$/(B. 
\end{df}

\begin{pr}
$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)]$.
\end{pr}
\proof
$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, 
$GF(p) \subset GF(q)$ $B$h$j(B $GF(q)/GF(p)$ $B$OM-8B<!Be?t3HBg(B. $B$=$N3HBg<!?t$r(B
$n$ $B$H$*$1$P(B, $\{w_1,\cdots,w_n\} \subset GF(q)$ $B$J$k(B $GF(p)$ $B>e@~7A(B
$BFHN)$J4pDl$,B8:_$7$F(B,
$$GF(q)=GF(p)w_1\oplus\cdots \oplus GF(p)w_n$$
$B$h$C$F(B, $|GF(q)|=(|GF(p)|)^n=p^n$. \qed

\begin{pr}
$GF(q)$ \quad ($q=p^n$) $B$O(B $x^{q-1}-1$, $x^q-x$ $B$N:G>.J,2rBN$G(B, 
$\displaystyle x^q-x=\prod_{\alpha \in GF(q)}(x-\alpha).$
\end{pr}
\proof
$B>hK!72(B $GF(q)^{\times}$ $B$OM-8B72$G(B, $B$=$N0L?t$O(B $q-1$ $B$h$j(B,
$BA4$F$N85(B $\alpha \in GF(q)^{\times}$ $B$KBP$7(B $\alpha^{q-1}=1$ $B$9$J$o$A(B
$\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, 
$$x^{q-1}-1=\prod_{\alpha \in GF(q)^{\times}}(x-\alpha), \quad
x^q-x = \prod_{\alpha \in GF(q)}(x-\alpha).$$ \qed

\begin{co}
$GF(q)$ $B$NI8?t$,4q?t$H$9$k(B. 
$$F_{+}=\{\alpha \in GF(q) \mid \alpha^{(q-1)/2}=1\},
\quad F_{-}=\{\alpha \in GF(q) \mid \alpha^{(q-1)/2}=-1\}$$
$B$H$*$1$P(B, $GF(q)=F_{+} \cup F_{-} \cup \{0\}$ $B$G(B $|F_{+}|=|F_{-}|=(q-1)/2.$
\end{co}
\proof
$x^q-x = x(x^{(q-1)/2}-1)(x^{(q-1)/2}+1)$
$B$J$kJ,2r$,@.$jN)$D$+$i(B, $GF(q)$ $B$,>e$N$h$&$KJ,2r$5$l$k$3$H$,$o$+$k(B.
$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. 
$F_{-}$ $B$bF1MM(B. \qed

\begin{pr}
$B0l$D$NBN(B $K$ $B$K4^$^$l$k(B $GF(q)$ ($q=p^n$), $GF(q')$ ($q'=p^{n'}$) $B$KBP$7(B
$$ GF(q) \subset GF(q') \Leftrightarrow n | n'.$$
\end{pr}
\proof
$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'.$

$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
$BBN$@$+$i(B, 
$$GF(q')=\{\alpha \in K \mid \alpha^{q'}-\alpha=0\}$$
$BF1MM$K(B, 
$$GF(q)=\{\alpha \in K \mid \alpha^{q}-\alpha=0\}$$
$n|n'$ $B$h$j(B $(q-1)|(q'-1)$ $B$,8@$($k$+$i(B, $x^q-x|x^{q'}-x.$ 
$B$h$C$F(B, $\alpha \in GF(q) \Rightarrow \alpha \in GF(q').$
\qed

\begin{co}
$GF(p)$ $B$NBe?tE*JDJq(B $\Omega$ $B$r0l$DDj$a$l$P(B, $GF(q) \subset \Omega$
$B$O(B, $\Omega$ $B$K$*$1$k(B $x^q-x$ $B$N:G>.J,2rBN$H$7$F0l0U$KDj$^$k(B. 
\end{co}

\begin{pr}
$GF(q)^{\times}$ $B$O0L?t(B $q-1$ $B$N=d2s72(B.
\end{pr}
\proof
$G=GF(q)^{\times}$ $B$OM-8B%"!<%Y%k72$h$j(B, $1 < n_i \in \Z$ ($i=1,\cdots,l$),
$n_i | n_j$ ($i<j$) $B$,B8:_$7$F(B, 
$$G \simeq \bigoplus \Z/(n_i).$$ 
$l>1$ $B$H$9$l$P(B, $B>/$J$/$H$b(B $n_1^2$ $B8D(B
$B$N85$,(B $x^{n_1}-1=0$ $B$N:,$H$J$k$,(B, $B$3$l$OIT2DG=(B. $B$h$C$F(B 
$$l=1,\quad G\simeq \Z/(n_1).$$ \qed

\begin{pr}
$f$ $B$r(B $GF(q)$ $B>e4{Ls$H$9$k$H(B, 
$$f | x^{q^n}-x \Leftrightarrow \deg(f) | n$$
\end{pr}
\proof
$GF(q)$ $B$NBe?tE*JDJq(B $\Omega$ $B$r0l$D8GDj$9$k(B. 
$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.\\
\underline{$\Rightarrow$)}
\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.$
$B$h$C$F(B, $\alpha \in GF(q^n)\subset \Omega.$ $B$3$l$+$i(B 
$GF(q)(\alpha)\subset GF(q^n).$ $B$f$($K(B
$$\deg(f)=[GF(q)(\alpha):GF(q)]|[GF(q^n):GF(q)]=n.$$\\
\underline{$\Leftarrow$)}
$\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
$B$+$i(B, 
$GF(q)(\alpha) \subset GF(q^n)$
$B$3$l$h$j(B $\alpha^{q^n}-\alpha=0$. $f$ $B$O(B $\alpha$ $B$N:G>.B?9`<0$@$+$i(B
$$f|x^{q^n}-x.$$
\qed\\
$x^{q^n}-x$ $B$O=E:,$r;}$?$J$$$+$i(B, $B<!$,@.$jN)$D(B. 

\begin{co}
\label{irred_mod}
$F = \{ f | f : GF(q)$ $B>e4{Ls(B, $B%b%K%C%/$G(B $\deg(f)|n\}$
$B$H$*$1$P(B $x^{q^n}-x = \prod_{f\in F} f.$
\end{co}

\section{$BL5J?J}J,2r(B}
$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
$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.

\begin{df}
$B=EJ#0x;R$r;}$?$J$$B?9`<0$r(B{\bf $BL5J?J}(B (squarefree)} $B$H$$$&(B. 
$f \in K[x]$ $B$KBP$7(B, 
$$f = \prod g_1^{n_i}$$$B$G3F(B $g_i$ $B$OL5J?J}$+$D8_$$$KAG$JB?9`(B
$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
$BJ,2r(B} $B$H8F$V(B.
\end{df}

$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.

\begin{lm} $K$ $B$rI8?t(B 0 $B$NBN$H$9$k(B. 
$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
$B$9$k$H$-(B, 
$$\GCD(f,f') = \prod_i g_i^{n_i-1}.$$
\end{lm}
\proof
$$f' = \prod_i g_i^{n_i-1}(\sum_i n_i g'_i \prod_{k\neq i}g_k)$$
$B$h$j(B
$$\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)$$
$K$ $B$NI8?t$,(B 0 $B$h$j(B $n_i \neq 0$, $g'_i \neq 0$ $B$@$+$i(B, 
$$\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)$$
$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$.
$B$h$C$F(B, $$\GCD(f,f') = \prod_i g_i^{n_i-1}.$$ \qed


\begin{al}($BL5J?J}J,2r(B)
\label{sqfr}
\begin{tabbing}
Input : $f(x) \in K[x]$ ($K$ $B$OI8?t(B 0 $B$NBN(B)\\
Output : $f$ $B$NL5J?J}J,2r(B $f= g_1^{n_1}g_2^{n_2}\cdots$\\
\\
$F \leftarrow 1$\\
$flat \leftarrow f/\GCD(f,f'),\quad m \leftarrow 0,\quad counter \leftarrow 1$\\
while\= ( $flat \neq constant$ ) \{\\
{\rm(a)}\> while \= ( $flat | f$ ) \{\\
\>\>$f \leftarrow f/flat,\quad m \leftarrow m + 1$\\
\>\}\\
{\rm(b)}\> $flat_1 \leftarrow \GCD(flat,f)$\\
\>$g \leftarrow flat/flat_1,\quad flat \leftarrow flat_1$\\
{\rm(c)}\>$F \leftarrow F\cdot g^m, \quad counter \leftarrow counter+1$\\
\}\\
return $F$\\
\end{tabbing}
\end{al}
\begin{pr}
\label{valid_sqfr}
$B%"%k%4%j%:%`(B \ref{sqfr} $B$O(B $f$ $B$NL5J?J}J,2r$r=PNO$9$k(B. 
\end{pr}
\proof (a) $B$K$*$$$F(B $counter = k$ $B$N;~(B,
\begin{center}
$f = g_k^{n_k-n_{k-1}}g_{k+1}^{n_{k+1}-n_{k-1}}\cdots$, \quad
$flat = g_k g_{k+1}\cdots$, \quad
$m = n_{k-1}\quad (n_0 = 0)$
\end{center}
$B$"$k$3$H$r5"G<K!$K$h$j<($9(B. 
$k = 1$ $B$N;~$OJdBj$h$j@5$7$$(B. $k$ $B$^$G@5$7$$$H$9$k(B. $B2>Dj$h$j(B, 
$flat^{n_k-n_{k-1}} | f\quad$ $B$+$D(B $flat^{n_k-n_{k-1}+1}{\not|} f$
$B$h$j(B(b) $B$K$*$$$F(B
$$m = n_{k-1}+(n_k-n_{k-1}) = n_k, \quad f = g_{k+1}^{n_{k+1}-n_k}\cdots$$
$B$H$J$k(B. $B$h$C$F(B, (c) $B$K$*$$$F$O(B $$flat = flat_1 = g_{k+1}\cdots$$
$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\\
$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. 

\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, 
$f'=0 \Leftrightarrow$ $B$"$kB?9`<0(B $g$ $B$,B8:_$7$F(B $f = g^p.$
\end{lm}

\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
$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, 
$$\GCD(f,f')=h\, \GCD(g,g')=h\prod g_i^{n_i-1}.$$
\end{lm}
\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').$
$$\GCD(g,g') = \prod_i g_i^{n_i-1} \GCD(\prod_k g_k,\sum_i n_i g'_i
\prod_{k\neq i}g_k)$$
$B2>Dj$K$h$j(B $n_i \neq 0$. $B$^$?(B $g_i$ $B$OL5J?J}$@$+$i(B, 
$BA0JdBj$K$h$j(B $g'_i \neq 0$ $B$@$+$i(B,
$$\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)$$
$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$.
$B$h$C$F(B, $$\GCD(g,g') = \prod_i g_i^{n_i-1}.$$ \qed

\begin{al}($BL5J?J}J,2r(B)
\label{sqfrmod}
\begin{tabbing}
Input : $f(x) \in K[x]$ ($K$ $B$OI8?t(B $p>0$ $B$NM-8BBN(B)\\
Output : $f$ $B$NL5J?J}J,2r(B $f= g_1^{n_1}g_2^{n_2}\cdots$\\
$F \leftarrow 1$\\
if \= $f'\neq 0$ \{\\
\> $flat \leftarrow f/\GCD(f,f'),\quad m \leftarrow 0,\quad counter \leftarrow 1$\\
\>while\= ( $flat \neq constant$ ) \{\\
{\rm(a)}\>\> while \= ( $flat | f$ ) \{\\
\>\>\>$f \leftarrow f/flat,\quad m \leftarrow m + 1$\\
\>\>\}\\
{\rm(b)}\>\> $flat_1 \leftarrow \GCD(flat,f)$\\
\>\>$g \leftarrow flat/flat_1,\quad flat \leftarrow flat_1$\\
{\rm(c)}\>\>$F \leftarrow F\cdot g^m, \quad counter \leftarrow counter+1$\\
\>\}\\
\}\\
if $f \neq constant$ \{\\
\> $g \leftarrow f^{1/p}$\\
\> $g = g_1^{n_1}g_2^{n_2}\cdots$ $B$HL5J?J}J,2r(B\\
\> $F = F\cdot g_1^{pn_1}g_2^{pn_2}\cdots$\\
\}\\
return $F$
\end{tabbing}
\end{al}
$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, 
$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. 
$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
$BJ,2r$,7W;;$G$-$?$3$H$K$J$k(B. 

$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 
$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
$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, 
$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
$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. 

$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
$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
$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
$B;R$+$i=g$KD>@\5a$a$F$$$/J}K!$,(B Wang-Trager
\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
$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. 


\section{Berlekamp $B%"%k%4%j%:%`(B}

$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
$B4D(B$R = K[x]$ $B$K$*$1$k4{Ls0x;RJ,2r$r9M$($k(B.
$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
$B$9$k$H(B, $BCf9q>jM>DjM}$K$h$j(B,
$$R/(f) \simeq \bigoplus R/(f_i).$$

$R/(f), R/(f_i)$ $B>e$K<!$N(B$K$-$B=`F17?(B (Frobenius $B<LA|(B) $B$r9M$($k(B.
$$\pi : f \mapsto f^q \bmod f$$
$$\pi_i : f \mapsto f^q \bmod {f_i}$$
$B$9$k$H(B, 
$$\Ker(\pi-I) \simeq \bigoplus \Ker(\pi_i-I)$$
$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. 
$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
$B$G9M$($l$P(B, $B:,$O$9$Y$F$3$l$G?T$/$5$l$F$$$k(B. $B$h$C$F(B
$\Ker(\pi_i-I) = K$.$B7k6I(B 
$$\Ker(\pi-I) \simeq \bigoplus K$$
$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)$
$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. 

\begin{pr}
\begin{enumerate}
\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)$

\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)$
\end{enumerate}
\end{pr}
$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, 
$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. 

$B<!$N%"%k%4%j%:%`$OM-8BBN>e$N0lJQ?tB?9`<0$N0x?tJ,2r$r9T$&(B. 

\begin{al}(Berlekamp{\rm\cite{BERL}})
\begin{tabbing}
Input : $f(x) \in R$; $f$ $B$OL5J?J}(B\\
Output : $\{f_1,f_2,\cdots\}$ $f = f_1 f_2 \cdots$ $B$O(B $f$ $B$N4{LsJ,2r(B\\
$F = \{f\}$\\
$Q \leftarrow \pi$ $B$N9TNsI=8=(B\\
$\{e_1 = 1, e_2, \cdots, e_r\} \leftarrow \Ker(Q-I)$ $B$N(B $K$-$B4pDl(B\\
if ($r = 1$) then return $F$\\
$k \leftarrow 2$\\
do \=\{\\
\> $F_1 \leftarrow \emptyset$\\
\> while \= $F \neq \emptyset$ do \{\\
\>\> $g \leftarrow$ $F$ $B$N0l$D$N85(B \\
\>\> $F \leftarrow F \backslash \{g\}$\\
\>\> $F_g \leftarrow \{\GCD(g,e_k-s)(s \in GF(q))$ $B$N$&$A(B, $BDj?t$G$J$$$b$N(B\}\\
\>\> $g \leftarrow g/\prod_{h\in F_g} h$\\
\>\> $F_1 \leftarrow F_1 \cup F_g$ \\
\>\> if ( $g \neq 1$ ) $F_1 \leftarrow F_1 \cup \{g\}$\\
\>\> if \= ($|(F \cup F_1)| = r$) return $F \cup F_1$\\
\>\}\\
\> $k \leftarrow k+1$ \\
\> $F \leftarrow F_1$ \\
\}\\
return F
\end{tabbing}
\end{al}
$B4pDl$K$h$jA4$F$N4{Ls0x;R$,J,N%$G$-$k$3$H$O<!$NL?Bj$h$j$o$+$k(B. 

\begin{pr}
$\{e_1,\cdots,e_r\}$ $B$r(B $\Ker(\pi-I)$ $B$N(B$K$-$B4pDl$H$9$k$H(B
$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)$
\end{pr}
\proof
$B$3$N<gD%$,56$J$i$P(B
\begin{center}
$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))$)
\end{center}
$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, 
$\{e_k\}$ $B$,4pDl$G$"$k$3$H$h$j(B
\begin{center}
$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).$
\end{center}
$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

$B0J>e=R$Y$?%"%k%4%j%:%`$O(B, $q$ $B$,>.$5$$;~$KMQ$$$i$l$k:G$b86;OE*$J7A$G$"(B
$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
$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$ 
$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.

\begin{pr}
$e \in \Ker(\pi-I)$ $B$KBP$7(B, 
$$S=\{s \in GF(q) \mid \GCD(e-s,f) \neq 1\}$$
$B$H$*$/(B. $B$3$N$H$-(B $m(x)=\prod_{s\in S}(x-s)$
$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. 
$B$9$J$o$A(B, $f|m(e)$ $B$H$J$k$h$&$J(B, $B:G>.<!?t$NB?9`<0(B. 
\end{pr}
\proof
$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
$s_i$ $B$,B8:_$9$k(B. $B$3$N$H$-(B $s_i \in S$ $B$G(B 
$$f_i | (e-s_i) | m(e).$$
$f$ $B$O(B $BL5J?J}$h$j(B $f | m(e).$
$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. 
$B$b$7(B $\deg(M)<\deg(m)$ $B$J$i$P(B, $B$"$k(B $s\in S$ $B$,B8:_$7$F(B
$$m=(x-s)q+r, \quad r \in GF(q) \backslash \{0\}$$
$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)$
$B$H$J$k$+$i(B, $f_i | r$. $B$3$l$OL7=b(B. \qed

$e$ $B$N:G>.B?9`<0$O(B, $e^k$ $B$,(B $\{1,e,e^2,\cdots,e^{k-1}\}$ $B$G(B
$BD%$i$l$F$$$k$+H]$+$r(B $k=1$ $B$+$i=g$KD4$Y$k$3$H$K$h$j7hDj$G$-$k(B. 

$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
$BBP$7$N$_(B GCD $B$r<B9T$9$l$P$h$$$3$H$K$J$k(B. 

\section{Cantor-Zassenhaus $B%"%k%4%j%:%`(B}
$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
$q$ $B$,>.$5$$>l9g$K$O==J,8zN($h$/0x?tJ,2r$G$-$k(B. $B$7$+$7(B, $q$ $B$,Bg$-$$(B
$B>l9g$K$O0J2<$G=R$Y$k$h$&$J3NN(E*%"%k%4%j%:%`$rMQ$$$J$1$l$P(B, $B8zN($h$$(B
$B0x?tJ,2r$OFq$7$$(B.
$B0J2<(B, $BA0@a$HF1MM$N5-9f$rMQ$$$k(B. 

\begin{pr}
$BI8?t(B $p$ $B$,4q?t$H$9$k(B. $e \in \Ker(\pi-I)$ $B$H$9$l$P(B, 
$$\GCD(e^{(q-1)/2}-1,f) \neq 1, f$$
$B$H$J$k3NN($O(B, $k$ $B$r(B $f$ $B$N4{Ls0x;R$N8D?t$H$9$k$H$-(B
$$1-({{q-1}\over{2q}})^k-({{q+1}\over{2q}})^k.$$
\end{pr}
\proof
$f_i$ ($i=1,\cdots,k$) $B$r(B $f$ $B$N4{Ls0x;R$H$7(B, 
$e \equiv s_i \bmod f_i$ ($s_i \in GF(q)$) $B$H$9$k(B.
$$e^{(q-1)/2} \equiv s_i^{(q-1)/2} \equiv 0, \pm 1 \bmod f_i$$
$B$h$j(B, 
\begin{center}
$\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$
\end{center}
\begin{center}
$\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$
\end{center}
$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, 
$s^{(q-1)/2} \equiv 0, -1$ $B$J$k85$O(B $(q+1)/2$ $B8D(B. 
$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
$B$O$=$l$>$l(B 
$$({{q-1}\over{2q}})^k,\quad ({{q+1}\over{2q}})^k$$
$B$H$J$k(B. \qed

$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
$BDj5A$9$k(B. 
\begin{df}
$GF(2^n)$ $B$K$*$$$F(B, $\Tr(x) \in GF(2^n)[x]$ $B$r(B
$$\Tr(x) = \sum_{i=0}^{n-1}x^{2^i}$$
$B$HDj5A$9$k(B.
\end{df}

\begin{lm}
$x^{2^n}-x=\Tr(x)(\Tr(x)+1).$
\end{lm}

\begin{co}
\begin{enumerate}
\item $a \in GF(2^n) \Rightarrow \Tr(a) \in GF(2)$
\item $|\{ s \in GF(2^n) \mid \Tr(s)=0\}| = |\{ s \in GF(2^n) \mid \Tr(s)=1 \}| = 2^{n-1}$
\end{enumerate}
\end{co}

\begin{pr}
$BI8?t(B $p=2$ $B$H$9$k(B. $e \in \Ker(\pi-I)$ $B$H$9$l$P(B, 
$$\GCD(\Tr(e),f) \neq 1, f$$
$B$H$J$k3NN($O(B, $k$ $B$r(B $f$ $B$N4{Ls0x;R$N8D?t$H$9$k$H$-(B
$1-1/2^{k-1}.$
\end{pr}
\proof
$f_i$ ($i=1,\cdots,k$) $B$r(B $f$ $B$N4{Ls0x;R$H$7(B, 
$e \equiv s_i \bmod f_i$ ($s_i \in GF(q)$) $B$H$9$k(B.
$$\Tr(e) \equiv \Tr(s_i) \equiv 0, 1 \bmod f_i$$
$B$h$j(B, 
\begin{center}
$\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$
\end{center}
\begin{center}
$\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$
\end{center}
$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. 
$B$h$C$F(B, $\GCD(\Tr(e),f) = f$, $\GCD(\Tr(e),f) = 1$ $B$J$k3NN((B
$B$O$=$l$>$l(B $1/2^k$ $B$H$J$k(B. \qed\\
$B$3$l$i$r$b$H$K(B, $B<!$N$h$&$J%"%k%4%j%:%`$rF@$k(B. 

\begin{al}(Cantor-Zassenhaus{\rm\cite{CZ}})
\begin{tabbing}
Input : $f(x) \in GF(q)[x]$, $q=p^n$, $f$ $B$OL5J?J}(B\\
Output: $\{f_1,f_2,\cdots\}$ $f = f_1 f_2 \cdots$ $B$O(B $f$ $B$N4{LsJ,2r(B\\
$F = \{f\}$\\
$Q \leftarrow \pi$ $B$N9TNsI=8=(B\\
$\{e_1 = 1, e_2, \cdots, e_r\} \leftarrow \Ker(Q-I)$ $B$N(B $K$-$B4pDl(B\\
if ($r = 1$) then return $F$\\
while\= ($|F| < r$) do \{\\
\> $(c_1,\cdots,c_r) \leftarrow$ $BMp?t%Y%/%H%k(B ($c_i \in GF(q)$)\\
\> $e \leftarrow \sum c_ie_i$ \\
\> if \= $p=2$\\
\>\> $E \leftarrow \Tr(e) \bmod f$\\
\>else\\
\>\> $E \leftarrow e^{(q-1)/2}-1 \bmod f$\\
\> $F_1 \leftarrow \emptyset$\\
\> while \= ($F \neq \emptyset$) do \{\\
\>        \> $g \leftarrow F$ $B$N85(B, \quad $F \leftarrow F \backslash \{g\}$\\
\>        \> $h \leftarrow \GCD(g,E)$\\
\>        \> if \= $h \neq 1,g$\\
\>        \> \> $F_1 \leftarrow F_1 \cup \{h,g/h\}$\\
\>        \> else \\
\>        \> \> $F_1 \leftarrow F_1 \cup \{g\}$\\
\> \}\\
\>   $F \leftarrow F_1$ \\
\}\\
return F
\end{tabbing}
\end{al}

\section{DDF (distinct degree factorization)}
$BM-8BBN>e$NB?9`<0$KBP$7$F$O(B, GCD $B$N$_$K$h$k(B DDF (distinct degree
factorization;$B<!?tJL0x;RJ,2r(B) $B$H$h$P$l$kM=HwE*$JJ,2r$,2DG=$G$"$k(B. DDF 
$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, 
$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. 
$B$^$?(B, $BJ,2r@.J,$N4{Ls0x;R$,F10l<!?t$G$"$k$3$H$rMxMQ$7$F(B, $BFC<l$J<jK!(B
$B$K$h$j4{LsJ,2r$r$9$k$3$H$b2DG=$K$J$k(B. 

$B7O(B \ref{irred_mod}$B$h$j(B, $B<!$N%"%k%4%j%:%`$,F@$i$l$k(B. 

\begin{al}
\begin{tabbing}
\\
Input : $f(x) \in GF(q)[x]$, $f$ $B$OL5J?J}(B\\
Output : $f(x) = \prod f_i$, $f_i$ $B$O(B $f$ $B$N(B $i$ $B<!4{Ls0x;R$N@Q(B\\
$w \leftarrow x$,\quad $i \leftarrow 1$\\
while\= ($i \le \deg(f)/2$) do \{\\
\> $w \leftarrow w^q \bmod f$\\
\> $f_i \leftarrow \GCD(f,w-x)$\\
\> if \= $f_i \neq 1$ \{\\
\>\> $f \leftarrow f/f_i$\\
\>\> $w \leftarrow w \bmod f$\\
\>\> $E \leftarrow e^{(q-1)/2}-1$\\
\>\}\\
\}\\
while ( $i < \deg(f)$ )\\
\> $f_i \leftarrow 1$\\
$f_{\deg(f)} \leftarrow f$\\
return $\prod f_i$
\end{tabbing}
\end{al}
$i$ $B2sL\$K$*$$$F$O(B, $i$ $B$N??$NLs?t$r<!?t$K;}$D0x;R$O4{$K=|$+$l$F(B
$B$$$k$?$a(B, $i$ $B<!$N0x;R$N$_$,<h$j=P$;$k(B. $B$^$?(B, $i \ge \deg(f)/2$
$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. 

$B$3$N%"%k%4%j%:%`$K$*$$$F(B, $w^q \bmod f$ $B$N7W;;$r7+$jJV$9I,MW$,$"$k(B. 
$B$7$+$7(B, $B0lHL$K(B
$$g = \sum_{i=0}^m a_ix^i \Rightarrow g^q \bmod f = \sum_{i=0}^m a_ix^{iq} \bmod f$$
$B$h$j(B, 
$w_0 = x^q \bmod f$
$B$N7W;;7k2L$+$i(B
$w_i = w_0^i \bmod f = w_{i-1}w_0 \bmod f$
$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
$B7W;;$O8zN($h$/7W;;$G$-$k(B. 

\section{$B<!?tJL0x;R$NJ,2r(B}
$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
$B%"%k%4%j%:%`$K$h$j4{LsJ,2r$G$-$k$,(B, $B4^$^$l$k4{Ls0x;R$N<!?t$,A4$FEy$7$$(B
$B$3$H$rMxMQ$7$FJ,2r$r9T$&$3$H$r9M$($k(B. 

\begin{pr}
$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 
$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
$B$V$H$-(B, 
$\GCD(g^{(q^d-1)/2}-1,f)=f_1$ $B$^$?$O(B $f_2$
$B$H$J$k3NN($O(B $1/2-1/(2q^d)$.
\end{pr}
\proof
$f_1$, $f_2$ $B$,(B $d$ $B<!4{Ls$h$j(B, 
$$GF(q)[x]/(f_1) \simeq GF(q)[x]/(f_2) \simeq GF(q^d).$$
$B$h$C$F(B, $BG$0U$N(B $g \in GF(q)[x]$ $B$KBP$7(B, 
$$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.$$
$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, 
$B$=$&$G$J$$$b$N$O(B $(q^d+1)/2$ $B8D$"$k(B. 
$\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
$B0lJ}$N$_$,(B 1 $B$K$J$k>l9g$G$"$k(B. 
$B$3$3$G(B, $BCf9q>jM>DjM}$K$h$j(B, 
$$GF(q)[x]/(f_1f_2) \simeq GF(q)[x]/(f_1)\bigoplus GF(q)[x]/(f_2)
\simeq GF(q^d)\bigoplus GF(q^d)$$$B$@$+$i(B, $BG$0U$N(B $(a_1,a_2) \in
GF(q^d)\bigoplus GF(q^d)$ $B$N85$KBP$7(B, $BB?9`<0$NAH$KBP$7(B, $a_1 = g
\equiv g \bmod f_1$, $a_2 = g \equiv g \bmod f_2$ $B$J$k(B$2d-1$ $B<!0J2<$N(B
$BB?9`<0(B $g$ $B$,0l0UE*$KBP1~$9$k(B.
$B$h$C$F(B, $2d-1$ $B0J2<$NB?9`<0(B $q^{2d}$ $B8D$N$&$A(B,
$\GCD(g^{(q^d-1)/2}-1,f)=f_1$ $B$^$?$O(B $f_2$ $B$H$J$k$N$O(B, 
$$2(q^d-1)/2\cdot (q^d+1)/2 = (q^{2d}-1)/2$$
$B8D$G$"$j(B, $B3NN($O(B $1/2-1/(2q^{2d}).$ \qed

\begin{pr}
$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 
$B$D$N(B $d$ $B<!4{Ls0x;R$H$7(B, 
$$\Tr(x) = \sum_{i=0}^{nd-1}x^{2^i}$$
$B$H$9$k(B. $GF(q)$ $B>e$N(B $B9b!9(B $2d-1$ 
$B<!<0(B $g$ $B$r%i%s%@%`$KA*$V$H$-(B,
$\GCD(\Tr(x),f)=f_1$ $B$^$?$O(B $f_2$
$B$H$J$k3NN($O(B $1/2$.
\end{pr}
\proof
$f_1$, $f_2$ $B$,(B $d$ $B<!4{Ls$h$j(B, 
$$GF(q)[x]/(f_1) \simeq GF(q)[x]/(f_2) \simeq GF(2^{nd}).$$
$B$h$C$F(B, $BG$0U$N(B $g \in GF(q)[x]$ $B$KBP$7(B, 
$$s_1=\Tr(g \bmod f_1) = 0,1,\quad s_2=\Tr(g \bmod f_2) = 0,1.$$
$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
$B$:$D$"$k(B. \\
$\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
$B0lJ}$N$_$,(B 0 $B$K$J$k>l9g$G$"$k(B. 
$B$3$3$G(B, $BCf9q>jM>DjM}$K$h$j(B, 
$$GF(q)[x]/(f_1f_2) \simeq GF(q)[x]/(f_1)\bigoplus GF(q)[x]/(f_2)
\simeq GF(2^{nd})\bigoplus GF(2^{nd})$$$B$@$+$i(B, $BG$0U$N(B $(a_1,a_2) \in
GF(2^{nd})\bigoplus GF(2^{nd})$ $B$N85$KBP$7(B, $BB?9`<0$NAH$KBP$7(B, $a_1 = g
\equiv g \bmod f_1$, $a_2 = g \equiv g \bmod f_2$ $B$J$k(B$2d-1$ $B<!0J2<$N(B
$BB?9`<0(B $g$ $B$,0l0UE*$KBP1~$9$k(B.
$B$h$C$F(B, $2d-1$ $B0J2<$NB?9`<0(B $2^{2nd}$ $B8D$N$&$A(B,
$\GCD(\Tr(x),f)=f_1$ $B$^$?$O(B $f_2$ $B$H$J$k$N$O(B, 
$2 \cdot (2^{nd-1})^2 = 2^{2nd-1}$
$B8D$G$"$j(B, $B3NN($O(B $1/2.$ \qed\\
$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 
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,
Cantor-Zassenhaus $B%"%k%4%j%:%`$NJQ7AHG$,E,MQ$G$-$k(B.

\begin{al}
\begin{tabbing}
\\
Input : $f(x) \in GF(q)[x]$, $q=p^n$, $f$ $B$OL5J?J}$G(B $d$ $B<!4{Ls0x;R$N@Q(B\\
Output : $f(x) = \prod f_i$, $f$ $B$N(B $B4{Ls0x;RJ,2r(B\\
$r \leftarrow \deg(f)/d,\quad F \leftarrow \{f\}$\\
while\= ($|F| < r$) do \{\\
\> $g \leftarrow 2d-1$ $B<!$N%i%s%@%`$JB?9`<0(B\\
\> if \= $p=2$\\
\>\>$G \leftarrow \sum_{j=0}^{rd-1}g^{2^i} \bmod f$\\
\> else\\
\>\> $G \leftarrow g^{(q^d-1)/2}-1 \bmod f$\\
\> $F_1 \leftarrow \emptyset$\\
\> while \= ($F \neq \emptyset$) do \{\\
\> 	  \> $h \leftarrow F$ $B$N(B $\deg(h)>d$ $B$J$k85(B,\quad $F \leftarrow F \backslash \{h\}$\\
\>        \> $z \leftarrow \GCD(h,G)$\\
\>        \> if \= $z \neq 1,h$\\
\>        \> \> $F_1 \leftarrow F_1 \cup \{z,h/z\}$\\
\>        \> else \\
\>        \> \> $F_1 \leftarrow F_1 \cup \{h\}$\\
\> \}\\
\>   $F \leftarrow F_1$ \\
\}\\
return $F$\\
\end{tabbing}
\end{al}

\section{$B@0?t78?t0lJQ?tB?9`<0$N0x?tJ,2r(B}
$B7W;;5!Be?t%7%9%F%`$K$*$$$FMQ$$$i$l$F$$$k0x?tJ,2r%"%k%4%j%:%`$O(B, 
$B2?$i$+$N=`F17?$K$h$jB?9`<0$r$h$j07$$$d$9$$6u4V$K<LA|$7(B, $B$=$N(B
$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
$BA|$+$i$b$H$N6u4V$K$*$1$k0x;R$r9=@.$9$k(B, $B$H$$$&J}K!$K$h$k$b$N$,B?$$(B. 
$BFC$K(B, $BFsJQ?t0J>e$NB?9`<0$N0x?tJ,2r$O0lJQ?tB?9`<0$K5"Ce$5$l$k$J$I(B, 
$B0lJQ?tB?9`<0$N0x?tJ,2r$O(B, $B0x?tJ,2r%"%k%4%j%:%`$K$*$$$F=EMW$J0LCV$r(B
$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
$B%"%k%4%j%:%`$K$D$$$F=R$Y$k(B. 

$BL5J?J}$J(B $f \in \Z[x]$ $B$N0x?tJ,2r%"%k%4%j%:%`$O(B, $BM-8BBN>e$N0x?tJ,2r(B,
Hensel $B9=@.(B, $B;n$73d$j$N;0$D$NItJ,$+$i$J$k(B. 

\begin{pr}(Hensel)
$f \in \Z[x], p \in \N$ $B$OAG?t$G(B, 
$$f \equiv \prod f_{1i} \bmod p,\quad f_{1i} \in GF(p)[x], \quad \deg(f) = \deg(\prod_i f_{1i})$$
$f_{1i}$ $B$O(B $GF(p)$ $B>e$G8_$$(B
$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
$B$7$F(B,
$$f \equiv \prod_i f_{ki} \bmod {p^k},\quad f_{1i} \equiv f_{ki} \bmod p, \quad \deg(f_{1i}) = \deg(f_{ki}).$$ 
\end{pr}
\proof
$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. 
$$f_{(k+1)i}=f_{ki}+p^k h_i$$
$B$J$k7A$r2>Dj$9$k$H(B, 
$$\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}}$$
$B0lJ}(B, $f \equiv \prod_i f_{ki} \bmod {p^k}$ $B$h$j(B, 
$$f = \prod_i f_{ki} + p^k h \bmod {p^{k+1}}$$
$B$H=q$1$k(B. 
$B$h$C$F(B, 
$$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$$
$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
$B$r<($;$P$h$$(B. $B$3$l$O(B, $BL?Bj(B \ref{exteuc} $B$K$h$j8@$($k(B. \qed

\begin{pr}
$f \in \Z[x], p \in \N$ $B$OAG?t(B, 
$$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$$
$B$H$9$k(B. $B$3$N;~(B,
$f \equiv gh \equiv g'h' \bmod {p^k}$ $B$+$D(B $g \equiv g' \equiv g_0 \bmod p,$
$\deg(g) = \deg(g') = \deg(g_0), \quad \deg(h) = \deg(h') = \deg(h_0),\quad
\lc(g) \equiv \lc(g') \bmod {p^k}$
$B$J$i$P(B, $$g \equiv g' \bmod {p^k}, \quad h \equiv h' \bmod {p^k}.$$
\end{pr}
\proof
$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
$B2>Dj$K$h$j(B, 
$$g' - g = p^k r,\quad h' - h = p^k s$$
$B$H=q$1$k(B.  $B0lJ}(B,
$gh \equiv g'h' \bmod {p^{k+1}}$ $B$+$i(B $r h_0 + s g_0 \equiv 0 \bmod p$
$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$
$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, 
$\lc(g) \equiv \lc(g') \bmod {p^{k+1}}$ $B$h$j(B,
$\deg(r \bmod p) < \deg(g_0).$ $B$h$C$F(B $r \equiv 0 \bmod p$ $B$H$J$j(B, 
$B$3$N>l9g$b(B $k+1$ $B$G@5$7$$(B. \qed

\begin{df}
$f = \sum_{i=0}^n a_i x^i \in C[x]$
$B$KBP$7(B, $f$ $B$N%N%k%`(B $\parallel f \parallel_1$, $\parallel f \parallel_2$ $B$r(B
$B$=$l$>$l(B, 
$$\parallel f \parallel_1 = \sum_{i=0}^n |a_i|, \quad
\parallel f \parallel_2 = \sqrt{\sum_{i=0}^n |a_i|^2}$$
($|a|$ $B$O(B $a$ $B$N@dBPCM(B) $B$GDj5A$9$k(B. 
\end{df}

\begin{pr}(Landau-Mignotte\cite{MIG})
$f = \sum_{i=0}^n a_i x^i \in \Z[x], g = \sum_{i=0}^m b_i x^i \in \Z[x]$
$B$H$9$k(B. $B$3$N;~(B $g|f$ $B$J$i$P(B,
$\parallel g\parallel_1 \le |b_m/a_n|2^m \parallel f\parallel_2$
\end{pr}

\begin{co}
\label{mig}
$f, g \in \Z[x]$, $g|f$ $B$J$i$P(B,
$\parallel \lc(f)/\lc(g)\cdot g\parallel_1 \le 2^{\deg(g)} \parallel f\parallel_2$
\end{co}

\begin{pr}
$f \in \Z[x]$ $B$,L5J?J}$J$i$P(B, $BM-8B8D$NAG?t(B $p$ $B$r=|$$$F(B
$\deg(f \bmod p) = \deg(f)$ $B$+$D(B $f \bmod p$ $B$OL5J?J}(B.
\end{pr}
$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
$B$"$k$3$H$+$iL@$i$+(B.\\
$B0J>e$K$h$j(B $\Z[x]$ $B$K$*$1$k0x?tJ,2r$O<!$N$h$&$K9T$J$o$l$k(B. 

\begin{al}(Zassenhaus{\rm \cite{ZASS}})
\label{zassenhaus}
\begin{tabbing}
Input : $f(x) \in \Z[x]$; $f$ $B$OL5J?J}(B\\
Output : $\{f_1,f_2,\cdots\}$ $f = f_1 f_2 \cdots$ $B$O(B $f$ $B$N4{LsJ,2r(B
\\
$p \leftarrow \deg(f) = \deg(f \bmod p)$ $B$+$D(B $f \bmod p$ $B$,L5J?J}$H$J$k$h$&$J(B $p$\\
$a \leftarrow f$ $B$N<g78?t(B\\
$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)\\
if $|F_1| = 1$ then return $\{f\}$\\
$F_1 = \{ f_{11},\cdots,f_{1m}\}$ $B$H$9$k(B. \\
$k \leftarrow p^k > \parallel f\parallel_2\cdot 2^{\deg(f)+1}$ $B$J$k@0?t(B\\
$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\\
Hensel $B9=@.$G5a$a$k(B\\
$l \leftarrow 1$\\
$F \leftarrow \emptyset$\\
while \= ( $2l \le m$ ) \{\\
(a)\> $S \leftarrow S \subset F_k$, $|S|=l$ $B$J$k?7$7$$ItJ,=89g(B\\
\> if \= $S$ $B$,B8:_$7$J$$(B then $l \leftarrow l+1$\\
\> else \= \{\\
\>\> $g \leftarrow a\cdots \prod_{s\in S}s$\\
(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\\
\> if $g|af$ \{\\
\>\> $g\leftarrow \pp(g)$ (primitive part),\quad $f \leftarrow f/g$,\quad
$F_k \leftarrow F_k \backslash S$\\
\> \}\\
\}\\
if ($f \neq 1$) then $F \leftarrow F \cup \{f\}$\\
return $F$
\end{tabbing}
\end{al}
\begin{pr}
$B%"%k%4%j%:%`(B \ref{zassenhaus} $B$O(B $f$ $B$N4{Ls0x;RJ,2r$r=PNO$9$k(B. 
\end{pr}
\proof
(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
$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
$B$K$h$j(B, (b) $B$K$*$$$F(B
$$a/\lc(G)\cdot G \equiv g \bmod p^k.$$
$B$3$3$G(B, $B7O(B \ref{mig} $B$*$h$S(B $k$ $B$N$H$jJ}$K$h$j(B, 
$$\parallel a/\lc(G)\cdot G\parallel_1 \le 2^{\deg(G)}\parallel f\parallel_2
\le 2^{\deg(f)}\parallel f\parallel_2 < p^k/2.$$
$B$^$?(B, $\parallel g \parallel_1\le p^k/2$ $B$h$j(B
$$\parallel g-a/\lc(G)\cdot G\parallel_1
\le \parallel g \parallel_1+\parallel a/\lc(G)\cdot G\parallel_1 < 2\cdot p^k/2=p^k.$$
$B0J>e$K$h$j(B, $a/\lc(G)\cdot G = g$. $B%"%k%4%j%:%`(B \ref{zassenhaus} $B$G$O(B, 
$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
$B4{Ls@-$,@.$jN)$D(B. \qed

$B$3$N%"%k%4%j%:%`$G$O(B, 
\begin{center}
$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
\end{center}
$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
$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
$B3d$j@Z$k$N$G$"$k(B.

$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
$B$KCm0U$9$kE@$O?tB?$/$"$k(B. $B$=$l$i$N$$$/$D$+$r=R$Y$k(B. 

\begin{enumerate}
\item $p$ $B$NA*Br(B

$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
$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. 
$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
$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 
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
$B8BBN>e$G$N0x?tJ,2r$rJ#?t2s5/F0$7(B, $B:G$b0x;R$N8D?t$,>/$J$$(B$p$ $B$rA*$V(B.

\item Hensel $B9=@.(B

$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
1 $B<!$N%*!<%@$G$7$+A}$($J$$(B. $BFC$K(B $p$ $B$,>.$5$$>l9g(B, $BL\E*$NI>2ACM$KE~C#(B
$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
$B$2$F$$$/(B quadratic lifting $B$H$$$&%"%k%4%j%:%`$,9M0F$5$l$F$$$k(B. $B$?$@$7(B
$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
Hensel $B9=@.$7$J$1$l$P$J$i$J$$$?$a(B, $p^k$ $B$,%^%7%s@0?tDxEY$N$&$A$O(B
quadratic lifting $B$7(B, $B%^%7%s@0?t$r1[$($?$"$?$j$G(B linear lifting $B$K@ZBX(B
$B$($k$H$$$&$3$H$,9T$J$o$l$k(B.

\item $B;n$73d$j(B

$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
$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
$BB?9`<0;~4V7W;;NL%"%k%4%j%:%`$O(B Lenstra $BEy$K$h$j(B lattice $B%"%k%4%j%:%`$H(B
$B$7$FDs0F$5$l$F$$$k$,(B, $B$"$/$^$GA26a7W;;NL$K$*$1$k8zN(2=$G$"$j(B, $B$3$3$G$O(B
$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
$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, 
\begin{center}
$g|f$ $B$J$i$P(B, $B@0?t(B $a$ $B$KBP$7(B $g(a) | f(a)$ 
\end{center}
$B$rMxMQ$7$F(B, 
\begin{itemize}
\item $BDj?t9`$I$&$7$N;n$73d$j(B ($g|f$ $B$J$i$P(B $g(0) | f(0)$)
\item $B78?t$NOB$I$&$7$N;n$73d$j(B ($g|f$ $B$J$i$P(B $g(1) | f(1)$)
\end{itemize}
$B$J$I$K$h$kA0=hM}$,9M0F$5$l$F$*$j(B, $B$=$l$>$l8z2L$rH/4x$7$F$$$k(B. 
\end{enumerate}


\section{$BB?JQ?tB?9`<0$N0x?tJ,2r(B, GCD, $BL5J?J}J,2r(B}
\subsection{$B0lHL2=$5$l$?(B Hensel $B9=@.(B}
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
$BJ,2r(B, GCD $B$OJ#;($+$D:F5"E*$K7k$SIU$$$F$$$F(B, $B$=$NA4BNA|$rGD0.$9$k$N$OMF(B
$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
$B$N>l9g$HA4$/F1MM$K7W;;$G$-$k$,(B, $B$"$k<gJQ?t$r8GDj$7$?;~(B, 1 $BJQ?t$N;~$K$O(B
$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
$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
$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
$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
$B$*$h$S$=$N2~NIHG$G$"$k(B PRS $BK!$rMQ$$$l$P86M}E*$K2DG=$G$O$"$k$,(B, $B$3$NJ}(B
$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
$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
$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
$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
$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
$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
$BF10l$G$"$k$?$a(B, $B0x?tJ,2r$K8B$i$:(B, GCD, $BL5J?J}J,2r$K$b1~MQ$G$-$k(B. 

$B0J2<$G$O(B, 
$$R = \Z[x_1,\cdots,x_n],\quad I = (x_2-a_2,\cdots,x_n-a_n)$$
($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
$\phi_I : R \rightarrow \Z[x_1]$ $B$r(B 
$$\phi_I(f) = f(x_1,a_2,\cdots,a_n)$$
$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
$B<g78?t$rI=$9$H$9$k(B. 

\begin{pr}(Moses-Yun{\rm\cite{YUN}})
\label{yun}
$f \in R, p \in \Z$ $B$OAG?t(B, 
$$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})$$
$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
$B$N(B $k$ $B$KBP$7(B, $f_{ki} \in \Z_{p^l}[x_1,\cdots,x_n]$ $B$,B8:_$7$F(B, 
$f \equiv \prod f_{ki} \bmod {(p^l,I^k)}$ $B$+$D(B $f_{ki} \equiv f_{1i} \bmod
{(p^l,I)},\quad \deg(f_{ki}) = \deg(f_{1i}).$
\end{pr}
\proof
$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. 
$$f_{(k+1)i}=f_{ki}+h_i\quad (h_i \in (p^l,I^k))$$
$B$J$k7A$r2>Dj$9$k$H(B,
$$\prod_i f_{(k+1)i} \equiv \prod_i f_{ki} + \sum_i h_i\prod_{j\neq i}f_{kj} 
\bmod {(p^l,I^{k+1})}$$
$B0lJ}(B, $f \equiv \prod_i f_{ki} \bmod {(p^l,I^k)}$ $B$h$j(B,
$$f = \prod_i f_{ki} + h\quad (h \in (p^l,I^k))$$
$B$H=q$1$k(B. $B$h$C$F(B, 
$$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})}$$
$B$H$J$k$h$&$K(B, 
$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
$B$r<($;$P$h$$(B. \\
$$h = \sum_{\alpha}h_{\alpha}(x_1)\prod_{j\ge 2}(x_j-a_j)^{\alpha_j} \bmod {I^{k+1}}$$
$$h_i = \sum_{\alpha}h_{i \alpha}(x_1)\prod_{j\ge 2}(x_j-a_j)^{\alpha_j} \bmod {I^{k+1}}$$
$B$H=q$/$H(B, $B3F78?t$KBP$7$F(B\\
$$h_{\alpha} \equiv \sum_i h_{i \alpha}\prod_{j\neq i}f_{1j} \bmod {p^l}$$
$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
$B>r7o$r9~$a$F2DG=$G$"$k(B. \qed

\begin{pr}
$f_i \in \Z[x]$, $p$ $B$OAG?t(B, $p {\not|}\lc(f_i)$, $f_i
\bmod p$ $B$O8_$$$KAG$H$9$k(B. $B$3$N;~(B, $BG$0U$N(B $k$, $BG$0U(B
$B$N(B $c \in \Z[x]$$B$KBP$7(B, $c_i \in \Z[x]$ $B$,B8:_$7$F(B, 
$$\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)$
$B$+$D(B, $B$3$N$h$&$J(B $c_i$ $B$O(B $p^k$ $B$rK!$H$7$F0l0UE*(B. 
\end{pr} 
\proof
$\bmod p$ $B$K$*$1$k>r7o$+$i(B, $e_{1i} \in GF(p)[x]$ $B$,B8:_$7$F(B,
$\sum_i e_{1i} f_i \equiv 1 \bmod p.$
$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
$\sum_i e_{ki} f_i \equiv 1 \bmod {p^k}.$
$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
$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$ 
$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
$\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
\deg(f_i)$$B$J$i$P(B, $\deg(c_1)+\sum_{j\neq 1}\deg(f_i) < \sum_i \deg(f_i)$
$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
$BK!$G>ZL@$G$-$k(B. \qed

\begin{pr}
{\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 
$f_{ki}$ $B$O(B $(p^l,I^k)$ $B$rK!$H$7$F0l0UE*$G$"$k(B. 
\end{pr}
$B>ZL@$O(B, $BA0Fs$D$NL?Bj$rMQ$$$l$P(B, $B0lJQ?t$N>l9g$HF1MM$K$G$-$k(B. 

\begin{pr}(Gel'fond{\rm\cite{GEL}})
$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
$|f$ $B$N0x;R$N78?t(B$|$ $\le e^{d_1+\cdots+d_n}\cdot \max$($|f$ $B$N78?t(B$|$).
\end{pr}

\begin{pr}
$f \in R$ $B$,L5J?J}$J$i$P(B, $BL58B$KB?$/$N(B $I$ $B$KBP$7(B
$\lc(\phi_I(f)) \neq 0$ $B$+$D(B $\phi_I(f)$ $B$OL5J?J}(B. 
\end{pr}
$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
$B$$$3$H$HF1CM$G$"$k$3$H$+$iL@$i$+(B.

\subsection{$BB?JQ?tB?9`<0$N0x?tJ,2r(B}
$B0J>e$K$h$j(B, $R$ $B$K$*$1$k0x?tJ,2r$O<!$N$h$&$K9T$J$o$l$k(B. 

\begin{al}
\begin{tabbing}
\\
Input : $f(x) \in R$; $f$ $B$OL5J?J}$+$D(B $x_1$ $B$K$D$$$F86;OE*(B\\
Output : $\{f_1,f_2,\cdots\}$ $f = f_1 f_2 \cdots$ $B$O(B $f$ $B$N4{LsJ,2r(B\\
$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
$BL5J?J}$J(B\\
$a=(a_2,\cdots,a_n) \in \Z^{n-1}$\\
$F_1 \leftarrow \{f_{1i}\} \leftarrow f_a(x_1)$ $B$N(B $\Z$ $B>e$G$N4{LsJ,2r(B\\
if $|F_1| = 1$ then return $\{f\}$\\
$p \leftarrow f_a(x_1)$ $B$N4{LsJ,2r$GMQ$$$?(B $p$\\
$F_1 = \{f_{11},\cdots,f_{1m}\}$ $B$H$9$k(B\\

$l \leftarrow 1$\\
$F \leftarrow \emptyset$\\
while \= ( $2l \le m$ ) \{\\
\> $S \leftarrow S \subset F_1$, $|S|=l$ $B$J$k?7$7$$ItJ,=89g(B\\
\> if \= $S$ $B$,B8:_$7$J$$(B then $l \leftarrow l+1$\\
\> else \= \{\\
\>\> $g_1 \leftarrow \prod_{s\in S}s$,\quad $h_1 \leftarrow \prod_{s\in F_1 \backslash S}s$\\
\>\> $g_1 \leftarrow \lc(f_a)/\lc(g_1)\cdot g_1$,\quad $\lc(g_1) \leftarrow \lc(f)$\\
\>\> $h_1 \leftarrow \lc(f_a)/\lc(h_1)\cdot h_1$,\quad $\lc(h_1) \leftarrow \lc(f)$\\
\>\> $B \leftarrow \lc(f)f$ $B$N(B Gel'fond bound\\
\>\> $l \leftarrow p^l > 2B$ $B$J$k@0?t(B $l$\\
\>\> $k \leftarrow f$ $B$N(B $x_2,\cdots,x_n$ $B$K4X$9$kA4<!?t(B $+1$\\
\>\> $\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\\
\>\> Hensel $B9=@.$G5a$a$k(B.\\
\>\> $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\\
\>\> if\= $g|\lc(f)f$ \{\\
\>\>\> $g\leftarrow \pp(g)$ (primitive part),\quad $f \leftarrow f/g$,\quad
$F_1 \leftarrow F_1 \backslash S$\\
\>\> \}\\
\> \}\\
\}\\
if ($f \neq 1$) then $F \leftarrow F \cup \{f\}$\\
return $F$
\end{tabbing}
\end{al}

$B$3$N%"%k%4%j%:%`$r<B8=$9$k>l9g(B, $B0lJQ?t$N>l9g$H$O0[$J$kLdBj$,$$$/$D$+@8$:$k(B. 

\begin{enumerate}
\item {\bf $BHsNmBeF~LdBj(B}

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
$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
$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
$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
$B78?t$r7W;;$9$kI,MW$,$"$k(B. $B85$NB?9`<0$,AB$G$bJ?9T0\F0$r9T$J$&$HL)$JB?9`<0(B
$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
$B>r7o$rK~$?$9$?$a$K$d$`$J$/(B 0 $B$G$J$$(B $a_i$ $B$rMQ$$$k$3$H$,$"$jF@$k(B. 
\item {\bf $B<g78?tLdBj(B}

$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
$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
$B9=@.$N:]$K(B, $BITI,MW$J9`$NA}2C$r2!$($i$l$k$,(B, $B<g78?t$,Bg$-$JB?9`<0$N>l9g(B
$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
$BBP1~$9$k<g78?t$r2?$i$+$NJ}K!$K$h$j7h$a$F$7$^$&J}K!$,(B Wang \cite{WANG} $B$K(B
$B$h$jDs0F$5$l$F$$$k(B. 
\item {\bf $B%K%;0x;R$NLdBj(B}

$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
$B<j=g$K$7$F$"$k(B. $B$3$l$O(B, 
\begin{itemize}
\item $BB?$/$N0x;R$rF1;~$K(B Hensel $B9=@.$9$k>l9g(B, $B<g78?t$r%b%K%C%/$N$^$^(B
$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
$BB?9`<0$N<g78?t$K9g$o$;$k$3$H$O(B, Hensel $B9=@.$NCJ?t$NA}2C$K$D$J$,$k(B. 
\item $B8uJd$,??$N0x;R$N%$%a!<%8$G$"$k$3$H$r4|BT$7$F$$$k(B. $B??$N0x;R$N(B
$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
$B$G;n$73d$j$r$7$F(B Hensel $B9=@.$r@Z$j>e$2$k$3$H$b$G$-$k(B. 
\end{itemize}
$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
$BF@$i$l$kCJ?t$^$G(B Hensel $B9=@.$,?J9T$7(B, $B5pBg$J8uJd$r@8@.$7$F$7$^$&(B. 
$B$3$l$O(B, $BBg$-$JL5BL$H$J$k$?$a(B, $B3FJQ?t$N<!?t$r>o$K%A%'%C%/$7$F(B, 
$B8uJd$N$I$l$+$NJQ?t$K4X$9$k<!?t$,M?$($i$l$?B?9`<0$N<!?t$r1[$($?;~E@$G(B
Hensel $B9=@.$rCfCG$9$k$J$I$NA`:n$,I,MW$H$J$k(B. 
\end{enumerate}
$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
$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
$B0x;R$N=P8=$N3NN($rBg$-$9$k(B. $B$3$N$?$a(B, $BJQ?t$N8D?t$r0l$D$:$DMn$7$F$$$/(B 
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
$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
$B0l$DA}$d$7$F(B Hensel $B9=@.$r9T$J$&:](B, $B%K%;0x;R$O<!Bh$KGS=|$5$l$F$$$/$?$a(B, 
$B%K%;0x;R$KBP$7$F6/$$%"%k%4%j%:%`$H$J$k(B.

\subsection{$BB?JQ?tB?9`<0$NL5J?J}J,2r5Z$S(B GCD}
\label{wangtrager}
$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
$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 
\ref{yun} $B$N(B$f_{1i}$) $B$,(B, $BK!(B $p$ $B$G8_$$$KAG$G$"$k$H$$$&>r7o$G$"$k(B. 
$\GCD(g,h)$ $B$N7W;;$K$*$$$F$O(B, $f_{1i}$ $B$H$7$F(B 
$$\{\GCD(\phi_I(g),\phi_I(h)),\phi_I(g)/\GCD(\phi_I(g),\phi_I(h))\}$$
$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
$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')$ 
$B$r5a$a$k:]$KI,MW$J(B $g_1=\GCD(g,g')$ $B$O(B, 
$$\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
$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 
$\GCD(g_s,h)$ $B$O(B $B0lHL2=$5$l$?(B Hensel $B9=@.$G7W;;$G$-(B, $\GCD(g,h)$ $B$N4{Ls(B
$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
$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
$B$l$?(B Hensel $B9=@.$G5a$a$k$3$H$,$G$-$k(B.

$B$7$+$7(B, $BL5J?J}J,2r$K$*$$$F(B, $g$ $B$,=EJ#EY$NBg$-$$0x;R$r4^$s$G$$$k$H$-(B, 
$g_s$ $B$N7W;;$KB?$/$N;~4V$,$+$+$k(B. $B$3$l$rHr$1$k$?$a(B, $B=EJ#EY$N:G$b9b$$(B
$B0x;R$+$i5a$a$F$$$/J}K!$,9M0F$5$l$?(B. $B$3$l$O(B, $B<!$NL?Bj$K4p$E$/(B. 

\begin{pr}
$f \in K[x]$ $B$KBP$7(B, 
$f = hg^e \quad (h,g \in K[x]),\quad  \GCD(h,g)=1$ $B$+$D(B $g$ $B$,L5J?J}(B
$B$J$i$P(B $g|(d/dx)^{e-1}f$ $B$G(B
$$\GCD(g,((d/dx)^{e-1}f)/g) = 1$$
\end{pr}
\proof
$e = 1$ $B$N$H$-L@$i$+(B. $e\ge 2$ $B$N$H$-(B, 
$(d/dx)^{e-1}(g^e) \equiv e!gg'^{e-1} \bmod{g^2}$
$B$,$$$($k(B. $B$h$C$F(B, 
$(d/dx)^{e-1}f \equiv h(d/dx)^{e-1}(g^e) \equiv e!hgg'^{e-1} \bmod{g^2}$
$B$H$J$j(B, $g|(d/dx)^{e-1}f$. $B$5$i$K(B, 
$((d/dx)^{e-1}f)/g \equiv e!hg'^{e-1} \bmod{g}$
$B$G(B, $\GCD(g,h) = 1$, $\GCD(g,g')=1$ $B$h$j(B
$\GCD(g,((d/dx)^{e-1}f)/g) = 1.$ \qed

\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
$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, 
$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
$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
$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. 
$BBEEv$JCM$,B8:_$9$k$3$H$O(B, $BL5J?J}$JB?JQ?tB?9`<0$KBP$9$kBEEv$JBeF~CM$NB8:_(B
$B$HF1MM$K8@$($k(B. 
$B$3$NJ}K!$N$h$$E@$O(B, 
\begin{itemize}
\item
($B=EJ#EY(B -1) $B$@$1B?9`<0$N<!?t$,Mn$;$k(B
\item
$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
$B$a$k>l9g$KHf3S$7$F7W;;$N<j4V$r8:$i$9$3$H$,$G$-$k(B
\item
$BA4BN$KBP$7$FBEEv$G$J$$BeF~$G$b(B, $B=EJ#EY:GBg$N0x;R$K$O1F6A$,$J$$>l9g$,$"$k(B. 
\item
$B$"$kB?9`<0$NQQ$K$J$C$F$$$k>l9g$K9bB.$KJ,2r$G$-$k(B. 
\end{itemize}
$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. 
$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
$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
$B$O(B, \cite{SQFR} $B$G$OCf9q>jM>DjM}$K$h$kJ}K!$rDs0F$7$F$$$k$,(B, Hensel $B9=@.(B
$B$K$h$k$b$N$b2DG=$G$"$k(B. 

$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
$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
$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
$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
$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
$B$H$J$j(B, $BEvA3(B debug $B$b:$Fq$J$b$N$K$J$k(B. 

\section{$BBe?tBN>e$N0x?tJ,2r(B}
$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
$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
$BK!$G$"$k(B. $K=\Q(\alpha)$ $B$H$$$&C13HBg$KBP$7$F$O(B, $B$3$NB>$K(B, Hensel $B9=@.(B
$B$rMQ$$$kJ}K!$,$$$/$D$+Ds0F$5$l$F$$$k$,$3$3$G$O=R$Y$J$$(B. Trager $B$NJ}K!(B
$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, 
$\Q$ $B>e$N0x?tJ,2r$5$(40Hw$7$F$$$l$P(B, $K=\Q(\alpha_1,\cdots,\alpha_r)$ $B>e(B
$B$G$N0x?tJ,2r$,2DG=$K$J$k(B. 

$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$ 
$B$J$k4{LsB?9`<0(B, $\alpha$ $B$r(B $g$ $B$N0l$D$N:,$H$9$k(B. 
$K(\alpha)=K[\alpha]=K[t]/(g)$ $B$G$"$k(B. $L\supset K$ $B$r(B $g$ $B$N:G>.J,2r(B
$BBN$H$9$k(B. $\alpha_1=\alpha,\alpha_2,\cdots,\alpha_m$ $B$r(B $g$ $B$NAj0[$J$k(B
$B:,$H$9$k$H(B, $L=K(\alpha_1,\cdots,\alpha_m)$ $B$H$+$1$k(B. 

\begin{df}
$f\in K(\alpha)[x]$ $B$KBP$7(B, $\Norm(f)$ $B$r(B
$$\Norm(f) = \prod_i f(x,\alpha_i)$$
$B$GDj5A$9$k(B. $L/K$ $B$N(B $\Norm$ $B$N@-<A(B
$B$K$h$j(B, $\Norm(f) \in K[x]$. $B$^$?(B, $$\Norm(f) = \res_t(f(x,t),g(t)).$$
\end{df}

\begin{pr}
$f\in K(\alpha)[x]$ $B$,4{Ls$J$i$P(B, $B$"$k4{LsB?9`<0(B $h \in K[x]$
$B$,B8:_$7$F(B, $$\Norm(f) = h^l.$$
\end{pr}
\proof
$\Norm(f) = ab,\quad a,b \in K[x],\quad \GCD(a,b)=1$ $B$H=q$1$?$H$9$k(B. $f
| \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
$B;~(B $$\Norm(f)|\Norm(a) = a^m.$$$B$h$C$F(B $\GCD(\Norm(f),b) = 1$ $B$H$J$j(B,
$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
$B;R$r4^$_F@$J$$(B. \qed

\begin{co}
$f\in K(\alpha)[x]$ $B$,L5J?J}$H$9$k;~(B, $\Norm(f)$ $B$,L5J?J}$J$i$P(B, 
$\Norm(f) = \prod f_i$
$B$r(B $K[x]$ $B$K$*$1$k4{LsJ,2r$H$9$k$H$-(B, 
$f = \prod \GCD(f,f_i)$
$B$O(B $f$ $B$N(B $K(\alpha)[x]$ $B$K$*$1$k4{LsJ,2r$rM?$($k(B. 
\end{co}
\proof $h$ $B$r(B $f$ $B$N(B $K(\alpha)[x]$ $B$K$*$1$k4{Ls0x;R$H$9$k(B.
$h$ $B$O$"$k(B $f_i$ $B$r3d$j@Z$k(B. 
$\Norm(h)$ $B$O(B $K[x]$ $B$N4{LsB?9`<0$NQQ$G(B, $\Norm(h)$ $B$OL5J?J}$J(B
$\Norm(f)$ $B$r3d$j@Z$k$+$i(B, $\Norm(h)$ $B<+?H$,(B $\Norm(f)$ $B$N4{Ls0x;R(B. 
$\Norm(h)$ $B$O(B $\Norm(f_i)$ $B$N0x;R$G$b$"$k$+$i(B, 
$f_i = \Norm(h).$
$B:#(B, $h$ $B$H0[$J$k0x;R(B $h_1$ $B$,(B $f_i$ $B$r3d$l$P(B, 
$BF1MM$K(B $f_i = \Norm(h_1)$. $hh_1|f$ $B$h$j(B 
$$\Norm(hh_1)={f_i}^2|\Norm(f).$$
$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
$B4{Ls0x;R$r4^$`(B.  \qed

$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
$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
$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
$B$o$+$k(B. 

\begin{pr}
$f\in K(\alpha)[x]$ $B$,L5J?J}$J$i$P(B, $\Norm(f(x-s\alpha))$ $B$,L5J?J}$H(B
$B$J$i$J$$(B $s \in K$ $B$OM-8B8D(B. 
\end{pr}
\proof $f$ $B$N:,$r(B $\beta_1,\cdots,\beta_m$ $B$H$9$k$H(B, $B2>Dj$h$j$3$l(B
$B$i$OAj0[$J$k(B. $B$9$k$H(B, $f(x-s\alpha_i)$ $B$N:,$O(B,
$$\beta_1+s\alpha_i,\cdots,\beta_m+s\alpha_i$$
$B$H$J$k(B. $B$3$l$h$j(B $\Norm(f(x-s\alpha))$ $B$,L5J?J}$G$J$$$N$O(B,
$B$"$k(B $i, j, k, l$ $B$KBP$7$F(B, 
$$\beta_j+s\alpha_i = \beta_k+s\alpha_l$$
$B$N>l9g$K8B$k(B.
$B$3$N$h$&$J>r7o$rK~$?$9(B $s$ $B$OM-8B8D$7$+$J$$(B.  \qed

$B0J>e$K$h$j(B, $B<!$N%"%k%4%j%:%`$,F@$i$l$k(B. 

\begin{al}
\label{trager}
\begin{tabbing}
\\
Input : $BL5J?J}$J(B $f(x,\alpha)\in K(\alpha)[x]$, $s \in \Z$\\
Output : $f$ $B$N(B $K(\alpha)$ $B>e$N4{Ls0x;R(B $\{f_1,\cdots,f_r\}$\\
again:\\
$r \leftarrow \res_t(f(x-st,t),g(t))$\\
if \= ( $r$ $B$,L5J?J}$G$J$$(B ) then\\
\>  $s \leftarrow s+1$; goto again\\
$r(x) = \prod r_i(x)$ : $r$ $B$N(B $K$ $B>e$G$N4{LsJ,2r(B\\
$z \leftarrow f$\\
for each $i$ do \{\\
\> $f_i \leftarrow \GCD(h(x+s\alpha),z(x,\alpha))$\\
\> $t \leftarrow z/f_i$\\
\}
\end{tabbing}
\end{al}
$B$3$N%"%k%4%j%:%`$K$*$$$F(B, $B%\%H%k%M%C%/$H$J$jF@$kItJ,$,?tB?$/$"$k(B. 
\begin{enumerate}
\item $B=*7k<0$N7W;;(B

$B=*7k<0$N7W;;$O(B, $BItJ,=*7k<0(B, $B9TNs<0$N(B modular $B1i;;$J$I$rAH$_9g$o$;$F9T$J(B
$B$&$,(B, $B<B:]$N7W;;;~4V$rH?1G$9$k7W;;NL$,M?$($i$l$F$$$J$$$?$a(B, $B%"%k%4%j%:(B
$B%`$NA*Br$,:$Fq$G$"$k(B. $B$^$?(B, $B$$$:$l$K$7$F$b(B, $B=*7k<0$N7W;;$O0lHL$K;~4V$,(B
$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
$BBg$-$5$OLdBj$G$"$k(B.

\item $K$ $B>e$G$N4{LsJ,2r(B

$K$ $B$,$^$?$"$k3HBgBN$K$J$C$F$$$k>l9g$K$O$3$N%"%k%4%j%:%`$,:F5"E*$K(B
$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
$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
$\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
$B$NLdBj$,$"$k(B. 

\item $K(\alpha)$ $B>e$G$N(B GCD $B7W;;(B

$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
$B$G$"$k(B. $BFC$K(B, Euclid $B8_=|K!$rMQ$$$k>l9g(B, $BCf4V<0KDD%$O(B, $BDj5AB?9`<0(B $g$
$B$,Bg$-$$>l9g(B, $B6K$a$F7c$7$$(B. $B$3$l$r$5$1$k$?$a$$$/$D$+$N(B modular $B7W;;K!(B
$B$,Ds0F$5$l$F$$$k(B. 
\end{enumerate}

$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
$B$G$J$$%N%k%`$rMxMQ$9$k$3$H$K$h$j(B, $B$"$kDxEY2sHr$G$-$k(B. 

\begin{pr}
$f \in K(\alpha)[x]$ $B$,L5J?J}(B, 
$$\Norm(f) = \prod_i {f_i}^{n_i}$$
($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, 
$\GCD(f,f_i)$ $B$O(B $f$ $B$NDj?t$G$J$$0x;R$G(B, 
$$f = \prod \GCD(f,f_i).$$
$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)$
$B$O4{Ls(B. 
\end{pr}
\proof
$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
$h | \prod \GCD(f,f_i).$
$f$ $B$OL5J?J}$h$j(B
$f | \prod \GCD(f,f_i).$
$\GCD(f,f_i)$ $B$O8_$$$KAG$h$j(B,
$f = \prod \GCD(f,f_i).$
$B$5$F(B, $f$ $B$N(B
$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, 
$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
$B$"$k(B $f$ $B$N4{Ls0x;R$r4^$`$N$G(B, $\GCD(f,f_i)$ $B$ODj?t$G$J$$(B. 
$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
$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
$h$ $B0J30$N0x;R$r4^$^$J$$(B \qed

$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
$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
$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
$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, 
$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
$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$ 
$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
$B0x?tJ,2r$N7W;;;~4V$bC;=L$G$-$k(B. $B$3$N2~NI$r:N$jF~$l$?%"%k%4%j%:%`$r<!$K(B
$B<($9(B.

\begin{al}
\label{modtrager}
\begin{tabbing}
\\
Input : $BL5J?J}$J(B $f(x,\alpha)\in K(\alpha)[x]$, $s \in \Z$\\
Output : $f$ $B$N(B $K(\alpha)$ $B>e$N4{Ls0x;R(B $\{f_1,\cdots,f_r\}$\\
$r \leftarrow \res_t(f(x-st,t),g(t))$\\
$r(x) = \prod r_i(x)^{m_i}$ : $r$ $B$N(B $K$ $B>e$G$N4{LsJ,2r(B\\
$z \leftarrow f$\\
for \= each $i$ do \{\\
\> $g_i \leftarrow \GCD(r_i(x+s\alpha),z(x,\alpha))$\\
\> if $m_i = 1$ then $g_i$ $B$O4{Ls(B\\
\> else $(g_i,s+1)$ $B$K$3$N%"%k%4%j%:%`$rE,MQ(B\\
\> $t \leftarrow z/g_i$\\
\}
\end{tabbing}
\end{al}

\begin{ex}
\cite{ABBOTT}
\begin{eqnarray*}
f(x) &=& x^{16}-136x^{14}+6476x^{12}-141912x^{10}+1513334x^8-7453176x^6+13950764x^4\\
& & -5596840x^2+46225
\end{eqnarray*}
$f(x)$ $B$O(B $\alpha = \sqrt{2}+\sqrt{3}+\sqrt{5}+\sqrt{7}$ $B$N(B $\Q$ $B>e$N(B
$B:G>.B?9`<0$G$"$k(B. $\Q(\alpha)/\Q$ $B$O%,%m%"3HBg$G$"$j(B, $f(x)$ $B$O(B 
$\Q(\alpha)$$B>e0l<!<0$N@Q$KJ,2r$9$k(B. $B$3$N0x?tJ,2r$r%"%k%4%j%:%`(B 
\ref{trager} $B$G5a$a$k>l9g(B, $F(x)=\Norm(f(x-s\alpha))$ $B$,L5J?J}$H$J$k(B 
$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
$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. 
$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 
(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
$B$KAH9g$;GzH/$r5/$3$7$F$$$F7W;;IT2DG=$G$"$k(B. $B0lJ}$G(B, $BNc$($P(B $s=-1$ $B$N>l(B
$B9g(B $F(x)$ $B$OL5J?J}$K$J$i$J$$$,(B, 16 $B8D$N0[$J$k4{Ls0x;R$,L5J?J}J,2r(B
$B$*$h$S$=$l$KB3$/4{Ls0x;RJ,2r$K$h$jMF0W$KF@$i$l$k(B. 
\begin{eqnarray*}
F(x) &=& x^{16} (x^2-28)^8 (x^2-20)^8 (x^2-8)^8 (x^2-12)^8\\
& & \cdot (x^4-64x^2+64)^4 (x^4-40x^2+16)^4\\
& & \cdot (x^4-80x^2+256)^4 (x^4-56x^2+144)^4\\
& & \cdot (x^4-72x^2+400)^4 (x^4-96x^2+64)^4\\
& & \cdot (x^8-240x^6+12512x^4-203520x^2+891136)^2\\
& & \cdot (x^8-192x^6+8576x^4-110592x^2+102400)^2\\
& & \cdot (x^8-224x^6+11264x^4-143360x^2+409600)^2\\
& & \cdot (x^8-160x^6+5632x^4-61440x^2+147456)^2\\
& & \cdot (x^{16}-544x^{14}+103616x^{12}-9082368x^{10}+387413504x^8-7632052224x^6\\
& & +57142329344x^4-91698626560x^2+3029401600)
\end{eqnarray*}
$B$3$l$i$N3F0x;R$+$i(B $f(x)$ $B$NA4$F$N0l<!0x;R$,F@$i$l$k(B. 
$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
$BBN>e$G0x?tJ,2r$9$k>l9g$K(B
$B%"%k%4%j%:%`(B \ref{modtrager} $B$,M-8z$H$J$k>l9g$,$"$k(B. 
\end{ex}

\section{$B1~MQ(B --- $BM-M}4X?t$NITDj@QJ,(B}
$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
$B$GI=<($9$kJ}K!$K$D$$$F=R$Y$k(B. 

$B0lHL$K(B, $BM-M}4X?t(B $f(x)=n(x)/d(x)$ ($n,d \in \Q[x]$) $B$NITDj@QJ,$O(B, 
$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
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. 
$B$^$?(B, $BITDj@QJ,<+BN$K(B, $d$ $B$NJ,2r$K$h$j8=$l$?Be?tE*?t$,8=$l$k$H$O(B
$B8B$i$J$$(B. 
\begin{ex}
$f=d'/d$ $B$J$i$P(B $\displaystyle \int f dx = \log d.$
\end{ex}
$B$3$N$3$H$+$i(B, $B:G>.$NBe?tE*?t$NE:2C$GITDj@QJ,$rI=<($9$k$3$H$r9M$($k(B. 

\subsection{$BM-M}ItJ,$N7W;;(B}

$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, 
$$n = qd+r, \quad q,d \in \Q[x], \deg(r) < \deg(d)$$
$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$
$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. 

\begin{pr}
$\deg(n)<\deg(d)$ $B$H$9$k(B. $d_r = \GCD(d,d')$, $d_l = d/d_r$ $B$H$*$/$H(B, 
$\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
$BE*$KB8:_$7$F(B, 
$$\int {n\over d} dx = {{n_r}\over {d_r}} + \int {{n_l}\over{d_l}} dx$$
\end{pr}
\proof
$d=\prod_i d_i^i$ $B$J$kL5J?J}J,2r$KBP1~$7$F(B, 
$${n\over d} = \sum_i \sum_j {{n_{ij}}\over{d_i^j}}\quad (\deg(r_{ij}) < \deg(d_i))$$
$B$J$kItJ,J,?tJ,2r$,L?Bj(B \ref{parfrac} $B$K$h$jB8:_$9$k(B. 
$d_r=\prod_i d_i^{i-1}$, $d_l=\prod_i d_i$ $B$G$"$k(B. 
$d_i$ $B$OL5J?J}$@$+$i(B, $\GCD(d_i,d_i')=1.$
$B$h$C$F(B, $B3F(B $n_{ij}$ $B$KBP$7(B, $s_{ij}, t_{ij} \in \Q[x]$ 
($\deg(s_{ij})< \deg(d_i)-1$, $\deg(t_{ij})< \deg(d_i)$) $B$,B8:_$7$F(B, 
$$s_{ij}d_i+t_{ij}d_i'=n_{ij}.$$
$B$3$l$rMQ$$$F(B, $j>1$ $B$N$H$-(B
$$\int {{n_{ij}}\over{d_i^j}} dx = \int {{s_{ij}}\over {d_i^{j-1}}}dx 
+ \int {{t_{ij}d_i'}\over {d_i^j}}dx$$
$B$3$3$G(B, $$({1\over {1-j}}\cdot {1\over{d^{j-1}}})'={{d_i'}\over {d_i^j}}$$
$B$h$j(B, 
$$\int {{t_{ij}d_i'}\over {d_i^j}}dx= {1\over {1-j}}\cdot {1\over{d_i^{j-1}}}\cdot t_{ij} - 
\int {1\over {1-j}}\cdot {1\over{d_i^{j-1}}} t_{ij}' dx.$$
$B$h$C$F(B
$$\int {{n_{ij}}\over{d_i^j}} dx = {t_{ij}\over {(1-j)d_i^{j-1}}}
+\int {{s_{ij}+{{t_{ij}'}\over{j-1}}}\over {d_i^{j-1}}} dx$$
$\deg({s_{ij}+{{t_{ij}'}\over{j-1}}}) < \deg(d_i)-1$ $B$h$j(B, 
$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, 
$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
$B$3$H$K$h$j(B, 
$$\int {n\over d}dx = \sum_i\sum_{j>1}{t_{ij}\over {(1-j)d_i^{j-1}}}
+\sum_i \int {{u_i}\over {d_i}} dx \quad (\deg(u_i)<\deg(d_i))$$
$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
$B$=$l$>$l(B ${{n_r}\over {d_r}}$,  ${{n_l}\over{d_l}}$ $B$H$*$1$P<!?t$N(B
$B>r7o$rK~$?$9(B. $B0l0U@-$OL@$i$+(B. \qed

$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. 

\begin{al}
\begin{tabbing}
\\
Input: $f(x)=n(x)/d(x)\in \Q(x)$, $\deg(n)<\deg(d)$\\
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\\
$B$?$@$7(B $\deg(n_r)<\deg(d_r)$, $\deg(n_l)<\deg(d_l)$\\
$d_r \leftarrow \GCD(d,d')$, \quad $d_l \leftarrow d/d_r$\\
$m_r \leftarrow \deg(d_r)$, \quad $m_l \leftarrow \deg(d_l)$\\
$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$\\
$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\\
return $\displaystyle \int f(x)dx = 
{{n_r(x)}\over{d_r(x)}}+\int {{n_l(x)}\over{d_l(x)}}dx$
\end{tabbing}
\end{al}

\subsection{$BBP?tItJ,$N7W;;(B}

$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
$$\int f dx = \sum_i c_i\log r_i$$
$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
$B2DG=@-$,$"$k$,(B, $B$3$NBe?t3HBg$r:G>.8B$K$9$k$h$&$JI=<($r5a$a$?$$(B. 

\begin{pr}(Rothstein{\rm\cite{DAV}})

$K$ $B$rJ#AG?tBN(B $\C$ $B$NItJ,BN$H$7(B, 
$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, 
$$n/d = \sum_{i=1}^n c_i v_i'/v_i$$
$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, 
$B$H=q$1$?$J$i$P(B, $c_i$ $B$O(B
$$R(z)=\res_x(n-zd',d) \in K[z]$$
$B$N:,$G(B, 
$$v_i=\GCD(n-c_id',d).$$
\end{pr}
\proof
\underline{claim 1} $v=d.$

$v=\prod_{i=1}^n$ $B$H$*$/$H(B, 
$$nv = d\sum_{i=1}^nc_iv_i'(v/v_i).$$
$\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$
$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. 
$B$h$C$F(B $v_i|d.$ $B7k6I(B $v|d$ $B$H$J$j(B $v=d.$ \qed\\
\underline{claim 2} $v_i=\GCD(n-c_id',d).$

claim 1 $B$h$j(B $n = \sum_{i=1}^n c_iv_i'(v/v_i).$ 
$d'=\sum_{i=1}^n v_i'(v/v_i)$ $B$h$j(B, 
$$n-c_id'=\sum_{j\neq i} (c_j-c_i)v_j'(v/v_j).$$
$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).$
$B0lJ}$G(B, $j\neq i$ $B$N$H$-(B, 
$$\GCD(n-c_id',v_j)=\GCD((c_j-c_i)v_j'(v/v_j),v_j)=1$$
$B$h$j(B, $v_i=\GCD(n-c_id',d).$ \qed

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. \\
\underline{claim 3} $\{c_1,\cdots,c_n\} = R(z)$ $B$N:,A4BN(B

$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.
$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.$
$$g|(n-cd')=\sum_{j=1}^n (c_j-c)v_j'(v/v_j)$$
$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

\begin{co}
$K$ $B$rJ#AG?tBN(B $\C$ $B$NItJ,BN$H$7(B, 
$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, 
$$R(z)=\res_x(n-zd',d) \in K[z]$$
$B$H$9$k(B. 
$K_R$ $B$r(B $R(z)$ $B$N:G>.J,2rBN$H$9$l$P(B, 
$K_R$ $B$,(B $\int n/d dx$ $B$rI=<($9$k$?$a$N:G>.$N(B $K$ $B$N3HBg(B. 
\end{co}
\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
$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 
$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 
$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
$B$,$G$-$k$3$H$OA0L?Bj$GJ]>Z$5$l$F$$$k(B. \qed