Return to poly.tex CVS log

Up to [local] / OpenXM / doc / compalg

Fixed several bugs.

%$OpenXM: OpenXM/doc/compalg/poly.tex,v 1.4 2000/11/21 08:01:11 noro Exp $
\chapter{$BB?9`<0(B}

\section{$BB?9`<0$NI=8=(B}
$B@0?t$N>l9g$=$N0lIt$r<h$j=P$7$FMQ$$$k$3$H$O$[$H$s$I$J$$$,(B, $BB?9`<0$O(B, $B$=(B
$B$N0lIt(B ($BNc$($P78?t(B) $B$rB?9`<0$"$k$$$O?t$H$7$F<h$j=P$9I,MW$,$7$P$7$P$"$k(B. 
$B=>$C$F(B, $B$=$NI=8=$b(B, $BMQES$K1~$8$F$5$^$6$^$J$b$N$,9M$($i$l$k(B. $B$3$3$G$O(B, 
$B$=$l$i$NCf$G(B{\bf $B:F5"I=8=(B}$B$H(B {\bf $BJ,;6I=8=(B} $B$K$D$$$F=R$Y$k(B.

\subsection{$B:F5"I=8=(B}
$B:F5"I=8=$H$O(B, $BB?9`<0$K8=$l$kJQ?t$K=g=x$r$D$1(B, $B$=$N=g=x$K=>$C$F(B, $BB?9`<0$r(B
$B0lJQ?tB?9`<0$H$_$J$7$F(B, $B$=$N3F78?t$r(B, $B$3$NJQ?t=g=x$K=>$C$F$5$i$KJ,2r$7$F(B
$B$$$/I=8=$G$"$k(B. 

\begin{ex}
$(x+y+z)^2 = 1 \cdot x^2 + (2 \cdot y + (2 \cdot z)) \cdot x + ((2 \cdot z) \cdot y + (1 \cdot z^2 ))$
\end{ex}
$B$3$NI=8=$O(B, $B<B:]$N%7%9%F%`$K$*$$$F$O:G$b0lHLE*$KMQ$$$i$l$k(B. $BFC$K(B, $BB?9`(B
$B<0$r(B, $B$"$kJQ?t$K4X$9$k0lJQ?tB?9`<0$H$_$J$7$F?J9T$9$k%"%k%4%j%:%`$KBP$7(B
$B$FM-8z$G$"$k(B. $B$3$N$h$&$J%"%k%4%j%:%`$K$O(B, $BB?9`<0$N;MB'1i;;$r=i$a$H$7$F(B, 
$BB?9`<0$N(B GCD, $B0x?tJ,2r$J$I(B, $B4pK\E*$G=EMW$J$b$N$,B?$/(B, $B=>$C$F(B, $BFbItI=8=(B
$B$H$7$F:F5"I=8=$r:NMQ$9$k$3$H$O(B, $B%7%9%F%`$N8zN($NE@$+$i8+$F<+A3$G$"$k(B. 
$B$?$@$7(B, $B:F5"I=8=$K$*$$$F$O(B, $B<gJQ?t$G$J$$JQ?t$K4X$9$k78?t$r<h$j=P$9>l9g(B
$B$K(B, $B<gJQ?t$K4X$9$k>l9g$KHf3S$7$FB?$/$N;~4V$,$+$+$k$N$,FqE@$G$"$k(B. $B$3$N(B
$B$?$a(B, $B7W;;$K@h$@$C$F(B, $B0[$J$kJQ?t=g=x$K$h$k:F5"I=8=$KJQ49$9$k$3$H$,$7$P(B
$B$7$P9T$J$o$l$k$,(B, $BJQ?t(B, $B9`$N8D?t$,B?$$>l9g$K$O(B, $BB?$/$N;~4V$,$+$+$k>l9g(B
$B$b$"$k(B. 

$B:F5"I=8=$r7W;;5!>e$G<B8=$9$k>l9g(B, $BJ8;zDL$j:F5"E*$JI=8=$H$J$k(B. $B$3$3$G(B, 
$B<gJQ?t$r0l$D7h$a$l$P(B, $B$=$NB?9`<0$O(B, $B$=$N<gJQ?t$K4X$9$k;X?t$H78?t$N%Z%"(B
$B$NJB$S$H$7$FI=8=$5$l$k(B. 
  
\subsection{$BJ,;6I=8=(B}

$BJ,;6I=8=$H$O(B, $BB?9`<0$r(B, $BC19`<0$NOB$H$7$FI=8=$9$kJ}<0$G$"$k(B. $B$3$3$G(B, 
$BC19`<0$H$O(B, $BJQ?t$NQQ@Q$H78?t$N@Q$G$"$k(B. 

\begin{ex}
$(x+y+z)^2 = 1 \cdot x^2 + 2 \cdot xy + 2 \cdot xz + 1 \cdot y^2 + 2 \cdot yz + 1 \cdot z^2$
\end{ex}
$B$3$N>l9g(B, $B3FC19`<0$N=g=x$KITDj@-$,$"$k$,(B,  $B3FJQ?t$OJ?Ey$K07$o$l$k(B. $B$3$NI=8=(B
$B$O(B, $B8e=R$9$k(B $B%0%l%V%J4pDl7W;;$K$*$$$F:G$b9%ET9g$JI=8=7A<0$G$"$j(B, $B$=$3$G$O(B
$BC19`<0$N4V$N=g=x$,K\<AE*$JLr3d$r2L$?$9(B. $B$3$l$K$D$$$F$O(B, $B%0%l%V%J4pDl$N(B
$B$H$3$m$G>\$7$/=R$Y$k(B. 

$BB?9`<0$O(B, $B7W;;5!>e$G$O%j%9%H(B ($BLZ9=B$(B) $B$"$k$$$OG[Ns$GI=8=$5$l$k(B. $BG[NsI=(B
$B8=$NB?9`<0$K4X$7$F$O(B, $BF10l<!?t$N78?t$N<h$j=P$7$,MF0W$N$?$a(B, $B;MB'1i;;$N(B
$B%"%k%4%j%:%`$O<+L@$G$"$k(B. $B$7$+$7(B, $B%j%9%HI=8=$N>l9g(B, $B;MB'1i;;$O(B, $B9`$N=g(B
$B=x$rHf3S$7$J$,$i(B, $B$b$7=g=x$,Ey$7$$>l9g$K$O78?t$KBP$9$k1i;;$r9T$&$H$$$&(B
$B$b$N$G(B, $B%=!<%F%#%s%0$NJQ7A$H9M$($i$l$k(B. $B$?$@$7(B, $BBP>]$H$J$kB?9`<0$O4{$K(B
$B%=!<%H$5$l$F$$$k$?$a(B, $B$=$N@-<A$rMxMQ$7$F8zN($h$/1i;;$r9T$&$3$H$,I,MW$G(B
$B$"$k(B.

\section{$B2C8:;;(B}
$BG[NsI=8=$N>l9g(B, $B2C8:;;$O<+L@$G$"$k(B. 

$B%j%9%HI=8=$N>l9g(B, $B1i;;7k2L%j%9%H$r6u$K=i4|2=$7(B, $B@hF,$N9`$N<!?t$rHf3S$7(B, 
$B<!?t$NBg$-$$J}$N9`$r$=$N$^$^(B, $B1i;;7k2L$N%j%9%H$K7R$.(B, $B$b$7<!?t$,Ey$7$$(B
$B>l9g$K$O(B, $B78?t$I$&$7$r1i;;$7(B, $B$=$l$,(B 0$B$G$J$$>l9g$K1i;;7k2L%j%9%H$K7R$0(B, 
$B$H$$$&A`:n$r7+$jJV$9(B.

\section{$B>h;;(B}
$B>h;;$O(B, $BJ,G[K!B'$K$h$j0lJ}$NB?9`<0$N3FC19`<0$H$b$&0lJ}$NB?9`<0$N@Q$NOB(B
$B$H$J$k$,(B, $BC19`<0$HB?9`<0$N@Q$O(B, $B78?t$O78?t$I$&$7$N@Q$G(B, $B3F9`$N<!?t$OC1(B
$B$J$kJ?9T0\F0$H$J$k$?$a(B, $B0lJ}$NB?9`<0$N9`$N8D?t$@$1$NB?9`<0$NOB$H$J$k(B. 

\section{$BQQ(B}
$BB?9`<0$NQQ$N7W;;$O(B, $B?t$N>l9g$H$O0[$J$j1i;;$NJ}K!$K$h$jBg$-$/8zN($,0[$J(B
$B$k(B. 

$B@0?t1i;;$N9`$G=R$Y$?QQ$N(B 2 $B?J7W;;K!$G$O(B, $B8+3]$1$N>h;;$N2s?t$OQQ;X(B
$B?t$NBP?tDxEY$G$"$k$,(B, $B<B:]$K$OCf4V$K8=$l$kB?9`<0$N9`$N8D?t$,A}$((B, $B$+$D(B
$BESCf$N@Q$K$*$1$k<!?t$NEy$7$$3F9`$N4V$N1i;;2s?t$bA}$($k$?$a(B, $B<B:]$N1i;;(B
$B;~4V$O5^7c$KA}2C$9$k(B. $B$3$N$?$a(B, $B0l8+8zN($,0-$=$&$K8+$($k(B, $BFs9`DjM}$rMQ(B
$B$$$kJ}K!$NJ}$,8zN($h$/QQ$r7W;;$G$-$k(B. $BB($A(B, $BQQ>h$9$Y$-B?9`<0$r(B 2$B$D$KJ,(B
$B$1(B, $BFs9`DjM}$K$h$jQQ$r7W;;$9$k$N$G$"$k(B. $B$3$N:]Fs9`78?t$,I,MW$K$J$k$,(B, 
$B$"$kDxEY$NBg$-$5$^$GM=$a%F!<%V%k$K$7$F$*$$$F$bNI$$$7(B, $B$"$k$$$O$=$NETEY(B
$B7W;;$7$F$b(B, $BAGKQ$JJ}K!$KHf3S$7$F=<J,9bB.$G$"(B
$B$k(B. 

\section{$B=|;;(B, $B>jM>1i;;(B}
$B=|;;(B, $B>jM>1i;;$O(B, $B$"$kJQ?t(B ($B<gJQ?t(B) $B$r7h$a$F(B, $B<gJQ?t$K4X$9$k(B 1 $BJQ?tB?9`<0(B
$B$H$7$F9T$&(B. $BBN(B $K$ $B>e$N0lJQ?tB?9`<0$N=|;;$O<!$N%"%k%4%j%:%`$G7W;;$G$-$k(B. 

\begin{al}
\begin{tabbing}
\\
Input : $f, g \in K[x]$, $g\neq 0$\\
Output : $f = qg+r$, $q,r \in K[x]$, $\deg(r) < \deg(g)$ $B$J$k(B $q,r$\\
$q\leftarrow 0$, \quad $r\leftarrow f$\\
while \= ( $\deg(r)\ge \deg(g)$ ) \{\\
\> $t \leftarrow \lc(r)/\lc(g)\cdot x^{\deg(r)-\deg(g)}$\\
\> $r \leftarrow r-tg$,\quad $q \leftarrow q+t$\\
\}\\
return $(q,r)$
\end{tabbing}
\end{al}

\section{Karatsuba $B%"%k%4%j%:%`(B}
\label{kara}

$B$3$3$G$O(B, 1 $BJQ?tB?9`<0$N9bB.>h;;K!$*$h$S$=$N1~MQ$K$D$$$F=R$Y$k(B. $B4{$K=R(B
$B$Y$?J}K!$G$O(B, 2 $B$D$N(B $n$ $B<!$NL)$JB?9`<0$N@Q7W;;$O(B $O(n^2)$ $B$N7W;;NL(B
$B$,I,MW$G$"$k(B. 
$B$3$l$KBP$7(B, Karatsuba $B%"%k%4%j%:%`$O(B $O(n^{\log_23}) \simeq
O(n^{1.58})$ $B$N7W;;NL$G@Q$r7W;;$9$k(B. $B$5$i$K7W;;NL$N>.$5$$(B FFT $B%"%k%4%j%:%`(B
$B$K$D$$$F$O(B \cite[Section 4.3]{KNUTH} $B$K>\$7$$2r@b$,$"$k(B. 

$B$^$:(B, 1 $B<!<0(B $f=ax+b$, $g=cx+d$ $B$N@Q$O(B, $B78?t4D$K$*$1$k@Q(B 3 $B2s$G<B9T$G$-$k$3$H(B
$B$KCm0U$9$k(B. $B$9$J$o$A(B, 
$$fg=(ax+b)(cx+d)=acx^2+((a-b)(d-c)+ac+bd)x+bd$$
$B$G(B, $B$3$3$K8=$l$k78?t4D$N@Q1i;;$O(B, $ac$, $bd$, $(a-b)(d-c)$ $B$N(B 3 $B2s$G$"$k(B.
$B$3$l$r(B, $B9b<!$N>l9g$K$b:F5"E*$KE,MQ$9$k(B. 
\begin{pr}
$2^m-1$ $B<!<0$I$&$7$N@Q$O(B, $O(3^m)$ $B$N7W;;NL$G7W;;$G$-$k(B. 
\end{pr}
\proof
$2^m-1$ $B<!<0$I$&$7$N7W;;%3%9%H$r(B $T(m)$ $B$H$9$k(B. 
$B78?t4D$K$*$1$kOB(B, $B@Q$N%3%9%H$r$=$l$>$l(B $A$, $M$ $B$H$9$k(B. 
$f$, $g$ $B$r(B $2^m-1$ $B<!<0$H$9$k(B. 
\begin{center}
$f=f_1x^m+f_2,\quad g=g_1x^m+g_2 \quad (\deg(f_1),\deg(f_2),\deg(g_1),\deg(g_2)<m)$
\end{center}
$B$H=q$/$H(B, 
$$fg=(f_1g_1x^{2m}+((f_1-f_2)(g_2-g_1)+f_1g_1+f_2g_2)x^m+f_2g_2$$
$B$3$3$G(B $fg$ $B$N7W;;%3%9%H$O(B $3T(m-1)+4\cdot 2^mA$, $B$9$J$o$A(B
$T(m) = 3T(m-1)+4\cdot 2^mA \quad (m\le 1).$
$B$5$i$K(B, $T(0)=M$ $B$+$i(B
$T(m) = (M+8A)3^m-8A\cdot 2^m.$ \qed

$B$3$NL?Bj$h$j(B, $n$ $B<!<0$I$&$7$N@Q$O(B, $O(n^{\log_23})$ $B$N7W;;NL$G7W;;$G$-$k(B
$B$3$H$,J,$+$k(B. $B99$K>\$7$/(B, $BDL>o$N(B $O(n^2)$ $B%"%k%4%j%:%`$HHf3S$7$F$_$h$&(B. 
$2^m-1$ $B<!<0$I$&$7$NDL>o$N%"%k%4%j%:%`$K$h$k7W;;%3%9%H$r(B $T_0(m)$ $B$H$9$l$P(B, 
$T_0(m)=M2^{2m}+A(2^m-1)^2$
$B$G$"$k(B. 
$$T_0(m)-T(m) \ge M2^{2m}+A(2^m-1)^2-((M+8A)3^m-8A\cdot 2^m)$$
$B$G(B, $B1&JU$N(B $m=0,\cdots,6$ $B$KBP$9$kCM$O<!$N$h$&$K$J$k(B. 

\begin{center}
\begin{tabular}{|c||c|c|c|c|c|c|c|} \hline
$m$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline
$B1&JU(B & 0 & M-7A & 7M-31A & 37M-103A & 175M-195A & 781M-727A & 3367M-1351A \\ \hline
\end{tabular} 
\end{center}

$B0lHL$K(B, $M>A$ $B$@$+$i(B $m \ge 5$ $B$9$J$o$A(B 31 $B<!<00J>e$N@Q$KBP$7$F$O(B, Karatsuba
$BK!$O>o$K9bB.$G$"$j(B, $M$ $B$,(B $A$ $B$KHf$Y$FBg$-$$>l9g$[$I(B, $BDc$$<!?t$+$i(B Karatsuba
$BK!$,8z2LE*$G$"$k$3$H$,J,$+$k(B. $B99$K(B, $B7W;;NL$N%*!<%@$N0c$$(B 
($O(n^2)$ $B$H(B  $O(n^{\log_23})$) $B$K$h$j(B, $B9b<!Dx(B Karatsuba $BK!$,9bB.$K$J$j(B, 
$BNc$($P(B $M/A=5$ $B$N;~(B, $2^m-1$ $B<!<0$N@Q$NDL>oK!$H(B Karatsuba $BK!$N7W;;%3%9%H$N(B
$BHf$O<!$N$h$&$K$J$k(B. 

\begin{center}
\begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|c|} \hline
$m$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline
$B7W;;%3%9%HHf(B & 1 & 1.1 & 0.96 & 0.78 & 0.61 & 0.48 & 0.37 & 0.28 & 0.21 & 0.16 & 0.12 \\ \hline
\end{tabular} 
\end{center}

$B$9$J$o$A(B, 100 $B<!$G(B 1.5 $BG\(B, 1000 $B<!<0$G(B 8 $BG\DxEY$N:9$,$D$/$3$H$K$J$k(B. 
Karatsuba $BK!$K$*$1$k(B, $BB?9`<0$NJ,3d(B, $B4X?t8F$S=P$7$N<j4V$J$I$,(B
$B$+$+$k$?$a(B, $B<B:]$K$O$3$N?t;z$rC#@.$9$k$3$H$OFq$7$$$,(B, $BB?9`<0$N@Q$K(B
$B4X$7$F$O(B, Karatsuba $BK!$O==J,<BMQE*$G$"$k$H8@$($k(B. 

\section{$B=|;;$r>h;;$G9T$&$K$O(B?}
$B4{$K=R$Y$?B?9`<0=|;;$O(B, $B<!?t(B $n$ $B$K$D$$$F(B $O(n^2)$ $B$N7W;;NL$rI,MW$H$9$k(B. 
$B$3$l$r(B, $B$h$j>/$J$$<j4V$G7W;;$9$k$?$a$K(B, $B>h;;$rMQ$$$F=|;;$r9T$&$3$H$r(B
$B9M$($k(B. 

\begin{pr}
$f = \sum_{i=0}^n a_ix^i$ $B$r(B, $a_0\neq 0$ $B$J$kB?9`<0$H$9$k(B. 
$g_0 = 1/{a_0}, \quad g_i = 2g_{i-1}-g_{i-1}^2f \bmod x^{2^i}$
$B$H$9$l$P(B, $g_if \equiv 1 \bmod x^{2^i}.$
\end{pr}

\begin{df}
$n$ $B<!B?9`<0(B $f$ $B$KBP$7(B, $f^{*} = x^nf(1/x)$ $B$HDj5A$9$k(B. 
\end{df}

\begin{pr}
$f$, $g$ $B$r3F!9(B $n$, $m$ $B<!(B ($n\ge m$) $BB?9`<0$H$7(B, 
$f=gq+r \quad (\deg(r)<m)$
$B$H$9$k(B. $B$3$N;~(B $tg^{*}\equiv 1 \bmod x^{n-m+1}$ $B$J$k(B $t$ $B$K$h$j(B
$q = (tf^{*} \bmod x^{n-m+1})^{*}.$
\end{pr}
\proof
$f=gq+r$ $B$h$j(B 
$x^nf(1/x)=x^mg(1/x)x^{n-m}q(1/x)+x^nr(1/x).$
$B$9$J$o$A(B 
$f^{*}=g^{*}q^{*}+x^{n-\deg(r)}r^{*}.$
$B$3$3$G(B, $\deg(r)<m$ $B$h$j(B $n-\deg(r)\le n-m+1.$ $B$h$C$F(B
$f^{*}\equiv g^{*}q^{*} \bmod x^{n-m+1}.$
$B$h$C$F(B $tf^{*}\equiv q^{*} \bmod x^{n-m+1}$ $B$H$J$k$,(B, 
$\deg(q)=n-m$ $B$h$j(B
$q = (tf^{*} \bmod x^{n-m+1})^{*}.$
\qed\\
$r=f-gq$ $B$h$j(B, $q$, $r$ $B$,2?2s$+$N>h;;$G7W;;$G$-$k$3$H$,$o$+$k(B.

\begin{itemize}
\item $t$ $B$r5a$a$k:]$KI,MW$J>h;;$N2s?t$O(B $\log_2{(n-m)}$ $BDxEY(B,
\item $t$ $B$,5a$^$C$F$$$l$P(B, $q$, $r$ $B$N7W;;$K$O>h;;(B 2 $B2s$G:Q$`(B. 
\item $B>h;;$K(B Karatsuba $BK!(B ($B$"$k$$$O(B FFT $BK!(B) $B$rMQ$$$k$3$H$K$h$j(B $O(n^2)$ $B$h$j(B
$B??$K>/$J$$<j4V$G=|;;$,7W;;$G$-$k(B. 
\item $g$ $B$rK!$H$9$k1i;;$N$h$&$K(B, $g$ $B$,8GDj$N>l9g(B, $t$ $B$r(B 1 $B2s7W;;$7$F(B
$B$*$1$P$h$$$+$i(B, $n$, $m$ $B$,Bg$-$$;~$K$OM-8z(B. (50 $B<!DxEY$+$i8z$$$F$/$k(B.)
\end{itemize}