Return to poly.tex CVS log

Up to [local] / OpenXM / doc / compalg

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

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