Return to poly.tex CVS log

Up to [local] / OpenXM / doc / compalg

Annotation of OpenXM/doc/compalg/poly.tex, Revision 1.1

1.1     ! noro        1: \chapter{$BB?9`<0(B}
        !             2:
        !             3: \section{$BB?9`<0$NI=8=(B}
        !             4: $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
        !             5: $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.
        !             6: $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,
        !             7: $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.
        !             8:
        !             9: \subsection{$B:F5"I=8=(B}
        !            10: $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
        !            11: $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
        !            12: $B$$$/I=8=$G$"$k(B.
        !            13:
        !            14: \begin{ex}
        !            15: $(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 ))$
        !            16: \end{ex}
        !            17: $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
        !            18: $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
        !            19: $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,
        !            20: $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
        !            21: $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.
        !            22: $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
        !            23: $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
        !            24: $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
        !            25: $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
        !            26: $B$b$"$k(B.
        !            27:
        !            28: $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,
        !            29: $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
        !            30: $B$NJB$S$H$7$FI=8=$5$l$k(B.
        !            31:
        !            32: \subsection{$BJ,;6I=8=(B}
        !            33:
        !            34: $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,
        !            35: $BC19`<0$H$O(B, $BJQ?t$NQQ@Q$H78?t$N@Q$G$"$k(B.
        !            36:
        !            37: \begin{ex}
        !            38: $(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$
        !            39: \end{ex}
        !            40: $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
        !            41: $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
        !            42: $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
        !            43: $B$H$3$m$G>\$7$/=R$Y$k(B.
        !            44:
        !            45: $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
        !            46: $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
        !            47: $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
        !            48: $B=x$rHf3S$7$J$,$i(B, $B$b$7=g=x$,Ey$7$$>l9g$K$O78?t$KBP$9$k1i;;$r9T$&$H$$$&(B
        !            49: $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
        !            50: $B%=!<%H$5$l$F$$$k$?$a(B, $B$=$N@-<A$rMxMQ$7$F8zN($h$/1i;;$r9T$&$3$H$,I,MW$G(B
        !            51: $B$"$k(B.
        !            52:
        !            53: \section{$B2C8:;;(B}
        !            54: $BG[NsI=8=$N>l9g(B, $B2C8:;;$O<+L@$G$"$k(B.
        !            55:
        !            56: $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,
        !            57: $B<!?t$NBg$-$$J}$N9`$r$=$N$^$^(B, $B1i;;7k2L$N%j%9%H$K7R$.(B, $B$b$7<!?t$,Ey$7$$(B
        !            58: $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,
        !            59: $B$H$$$&A`:n$r7+$jJV$9(B.
        !            60:
        !            61: \section{$B>h;;(B}
        !            62: $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
        !            63: $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
        !            64: $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.
        !            65:
        !            66: \section{$BQQ(B}
        !            67: $BB?9`<0$NQQ$N7W;;$O(B, $B?t$N>l9g$H$O0[$J$j1i;;$NJ}K!$K$h$jBg$-$/8zN($,0[$J(B
        !            68: $B$k(B.
        !            69:
        !            70: $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
        !            71: $B?t$NBP?tDxEY$G$"$k$,(B, $B<B:]$K$OCf4V$K8=$l$kB?9`<0$N9`$N8D?t$,A}$((B, $B$+$D(B
        !            72: $BESCf$N@Q$K$*$1$k<!?t$NEy$7$$3F9`$N4V$N1i;;2s?t$bA}$($k$?$a(B, $B<B:]$N1i;;(B
        !            73: $B;~4V$O5^7c$KA}2C$9$k(B. $B$3$N$?$a(B, $B0l8+8zN($,0-$=$&$K8+$($k(B, $BFs9`DjM}$rMQ(B
        !            74: $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
        !            75: $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,
        !            76: $B$"$kDxEY$NBg$-$5$^$GM=$a%F!<%V%k$K$7$F$*$$$F$bNI$$$7(B, $B$"$k$$$O$=$NETEY(B
        !            77: $B7W;;$7$F$b(B, $BAGKQ$JJ}K!$KHf3S$7$F=<J,9bB.$G$"(B
        !            78: $B$k(B.
        !            79:
        !            80: \section{$B=|;;(B, $B>jM>1i;;(B}
        !            81: $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
        !            82: $B$H$7$F9T$&(B. $BBN(B $K$ $B>e$N0lJQ?tB?9`<0$N=|;;$O<!$N%"%k%4%j%:%`$G7W;;$G$-$k(B.
        !            83:
        !            84: \begin{al}
        !            85: \begin{tabbing}
        !            86: \\
        !            87: Input : $f, g \in K[x]$, $g\neq 0$\\
        !            88: Output : $f = qg+r$, $q,r \in K[x]$, $\deg(r) < \deg(g)$ $B$J$k(B $q,r$\\
        !            89: $q\leftarrow 0$, \quad $r\leftarrow f$\\
        !            90: while \= ( $\deg(r)\ge \deg(g)$ ) \{\\
        !            91: \> $t \leftarrow \lc(r)/\lc(q)\cdot x^{\deg(r)-\deg(g)}$\\
        !            92: \> $r \leftarrow r-tg$,\quad $q \leftarrow q+t$\\
        !            93: \}\\
        !            94: return $(q,r)$
        !            95: \end{tabbing}
        !            96: \end{al}
        !            97:
        !            98: \section{Karatsuba $B%"%k%4%j%:%`(B}
        !            99:
        !           100: $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
        !           101: $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
        !           102: $B$,I,MW$G$"$k(B.
        !           103: $B$3$l$KBP$7(B, Karatsuba $B%"%k%4%j%:%`$O(B $O(n^{\log_23}) \simeq
        !           104: 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
        !           105: $B$K$D$$$F$O(B \cite[Section 4.3]{KNUTH} $B$K>\$7$$2r@b$,$"$k(B.
        !           106:
        !           107: $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
        !           108: $B$KCm0U$9$k(B. $B$9$J$o$A(B,
        !           109: $$fg=(ax+b)(cx+d)=acx^2+((a-b)(d-c)+ac+bd)x+bd$$
        !           110: $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.
        !           111: $B$3$l$r(B, $B9b<!$N>l9g$K$b:F5"E*$KE,MQ$9$k(B.
        !           112: \begin{pr}
        !           113: $2^m-1$ $B<!<0$I$&$7$N@Q$O(B, $O(3^m)$ $B$N7W;;NL$G7W;;$G$-$k(B.
        !           114: \end{pr}
        !           115: \proof
        !           116: $2^m-1$ $B<!<0$I$&$7$N7W;;%3%9%H$r(B $T(m)$ $B$H$9$k(B.
        !           117: $B78?t4D$K$*$1$kOB(B, $B@Q$N%3%9%H$r$=$l$>$l(B $A$, $M$ $B$H$9$k(B.
        !           118: $f$, $g$ $B$r(B $2^m-1$ $B<!<0$H$9$k(B.
        !           119: \begin{center}
        !           120: $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)$
        !           121: \end{center}
        !           122: $B$H=q$/$H(B,
        !           123: $$fg=(f_1g_1x^{2m}+((f_1-f_2)(g_2-g_1)+f_1g_1+f_2g_2)x^m+f_2g_2$$
        !           124: $B$3$3$G(B $fg$ $B$N7W;;%3%9%H$O(B, $B9b!9(B $3T(m-1)+3\cdot 2^mA$, $B$9$J$o$A(B
        !           125: $T(m) \le 3T(m-1)+3\cdot 2^mA \quad (m\le 1).$
        !           126: $B$5$i$K(B, $T(0)=M$ $B$+$i(B
        !           127: $T(m) \le (M+6A)3^m-6A\cdot 2^m.$ \qed
        !           128:
        !           129: $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
        !           130: $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.
        !           131: $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,
        !           132: $T_0(m)=M2^{2m}+A(2^m-1)^2$
        !           133: $B$G$"$k(B.
        !           134: $$T_0(m)-T(m) \ge M2^{2m}+A(2^m-1)^2-((M+6A)3^m-6A\cdot 2^m)$$
        !           135: $B$G(B, $B1&JU$N(B $m=0,\cdots,7$ $B$KBP$9$kCM$O<!$N$h$&$K$J$k(B.
        !           136:
        !           137: \begin{center}
        !           138: \begin{tabular}{|c||c|c|c|c|c|c|c|} \hline
        !           139: $m$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline
        !           140: $B1&JU(B & 0 & M-5A & 7M-21A & 37M-65A & 175M-165A & 781M-305A & 3367M-21A \\ \hline
        !           141: \end{tabular}
        !           142: \end{center}
        !           143:
        !           144: $B0lHL$K(B, $M>A$ $B$@$+$i(B $m \ge 4$ $B$9$J$o$A(B 15 $B<!<00J>e$N@Q$KBP$7$F$O(B, Karatsuba
        !           145: $BK!$O>o$K9bB.$G$"$j(B, $M$ $B$,(B $A$ $B$KHf$Y$FBg$-$$>l9g$[$I(B, $BDc$$<!?t$+$i(B Karatsuba
        !           146: $BK!$,8z2LE*$G$"$k$3$H$,J,$+$k(B. $B99$K(B, $B7W;;NL$N%*!<%@$N0c$$(B
        !           147: ($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,
        !           148: $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
        !           149: $BHf$O<!$N$h$&$K$J$k(B.
        !           150:
        !           151: \begin{center}
        !           152: \begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|c|} \hline
        !           153: $m$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline
        !           154: $B7W;;%3%9%HHf(B & 1 & 1 & 0.84 & 0.67 & 0.53 & 0.41 & 0.31 & 0.24 & 0.18 & 0.13 & 0.10 \\ \hline
        !           155: \end{tabular}
        !           156: \end{center}
        !           157:
        !           158: $B$9$J$o$A(B, 100 $B<!$G(B 4 $BG\(B, 1000 $B<!<0$G(B 10 $BG\DxEY$N:9$,$D$/$3$H$K$J$k(B.
        !           159: Karatsuba $BK!$K$*$1$k(B, $BB?9`<0$NJ,3d(B, $B4X?t8F$S=P$7$N<j4V$J$I$,(B
        !           160: $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
        !           161: $B4X$7$F$O(B, Karatsuba $BK!$O==J,<BMQE*$G$"$k$H8@$($k(B.
        !           162:
        !           163: \section{$B=|;;$r>h;;$G9T$&$K$O(B?}
        !           164: $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.
        !           165: $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
        !           166: $B9M$($k(B.
        !           167:
        !           168: \begin{pr}
        !           169: $f = \sum_{i=0}^n a_ix^i$ $B$r(B, $a_0\neq 0$ $B$J$kB?9`<0$H$9$k(B.
        !           170: $g_0 = 1/{a_0}, \quad g_i = 2g_{i-1}-g_{i-1}^2f \bmod x^{2^i}$
        !           171: $B$H$9$l$P(B, $g_if \equiv 1 \bmod x^{2^i}.$
        !           172: \end{pr}
        !           173:
        !           174: \begin{df}
        !           175: $n$ $B<!B?9`<0(B $f$ $B$KBP$7(B, $f^{*} = x^nf(1/x)$ $B$HDj5A$9$k(B.
        !           176: \end{df}
        !           177:
        !           178: \begin{pr}
        !           179: $f$, $g$ $B$r3F!9(B $n$, $m$ $B<!(B ($n\ge m$) $BB?9`<0$H$7(B,
        !           180: $f=gq+r \quad (\deg(r)<m)$
        !           181: $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
        !           182: $q = (tf^{*} \bmod x^{n-m+1})^{*}.$
        !           183: \end{pr}
        !           184: \proof
        !           185: $f=gq+r$ $B$h$j(B
        !           186: $x^nf(1/x)=x^mg(1/x)x^{n-m}q(1/x)+x^nr(1/x).$
        !           187: $B$9$J$o$A(B
        !           188: $f^{*}=g^{*}q^{*}+x^{n-\deg(r)}r^{*}.$
        !           189: $B$3$3$G(B, $\deg(r)<m$ $B$h$j(B $n-\deg(r)\le n-m+1.$ $B$h$C$F(B
        !           190: $f^{*}\equiv g^{*}q^{*} \bmod x^{n-m+1}.$
        !           191: $B$h$C$F(B $tf^{*}\equiv q^{*} \bmod x^{n-m+1}$ $B$H$J$k$,(B,
        !           192: $\deg(q)=n-m$ $B$h$j(B
        !           193: $q = (tf^{*} \bmod x^{n-m+1})^{*}.$
        !           194: \qed\\
        !           195: $r=f-gq$ $B$h$j(B, $q$, $r$ $B$,2?2s$+$N>h;;$G7W;;$G$-$k$3$H$,$o$+$k(B.
        !           196:
        !           197: \begin{itemize}
        !           198: \item $t$ $B$r5a$a$k:]$KI,MW$J>h;;$N2s?t$O(B $\log_2{(n-m)}$ $BDxEY(B,
        !           199: \item $t$ $B$,5a$^$C$F$$$l$P(B, $q$, $r$ $B$N7W;;$K$O>h;;(B 2 $B2s$G:Q$`(B.
        !           200: \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
        !           201: $B??$K>/$J$$<j4V$G=|;;$,7W;;$G$-$k(B.
        !           202: \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
        !           203: $B$*$1$P$h$$$+$i(B, $n$, $m$ $B$,Bg$-$$;~$K$OM-8z(B. (50 $B<!DxEY$+$i8z$$$F$/$k(B.)
        !           204: \end{itemize}
        !           205:
        !           206: