Return to rims2004-noro.tex CVS log

Up to [local] / OpenXM / doc / Papers

Annotation of OpenXM/doc/Papers/rims2004-noro.tex, Revision 1.1

1.1     ! noro        1: \documentclass[12pt]{jarticle}
        !             2: \usepackage[FVerb,theorem]{rims02}
        !             3: \topmargin -0.5in
        !             4: \oddsidemargin -0in
        !             5: \evensidemargin -0in
        !             6: \textheight 9.5in
        !             7: \textwidth 6in
        !             8: \IfFileExists{my.sty}{\usepackage{my}}{}
        !             9: \IfFileExists{graphicx.sty}{\usepackage{graphicx}}{}
        !            10: \IfFileExists{epsfig.sty}{\usepackage{epsfig}}{}
        !            11: \title{$BBe?tBN>e$N%$%G%"%k$N%0%l%V%J!<4pDl7W;;$K$D$$$F(B}
        !            12: \author{$BLnO$(B $B@59T(B \\ ($B?@8MBgM}(B)}
        !            13: \date{}
        !            14: \begin{document}
        !            15: \maketitle
        !            16: \def\gr{Gr\"obner $B4pDl(B}
        !            17: \def\st{\, s.t. \,}
        !            18: \def\noi{\noindent}
        !            19: \def\Q{{\bf Q}}
        !            20: \def\Z{{\bf Z}}
        !            21: \def\NF{{\rm NF}}
        !            22: \def\ve{\vfill\eject}
        !            23: \newcommand{\tmred}[1]{\smash{\mathop{\hbox{\rightarrowfill}}\limits_{\scriptstyle #1}\limits^{\scriptstyle *}}}
        !            24:
        !            25: \begin{abstract}
        !            26: $BK\9F$G$O(B, $BBe?tBN(B, $B$9$J$o$AM-M}?tBN(B $\Q$ $B$NM-8B<!Be?t3HBg$K$*$1$k(B
        !            27: $B8zN(E*1i;;$r9T$&$?$a$N(B, $BBe?tE*?t$N4JLs$*$h$S5U857W;;$K$D$$$F=R$Y$k(B.
        !            28: $B$5$i$K(B, $B$=$l$i$rMQ$$$?(B, $BBe?tBN>e$G$N>e$G$N%0%l%V%J!<(B
        !            29: $B4pDl7W;;$K$D$$$F=R$Y$k(B.
        !            30: \end{abstract}
        !            31:
        !            32: \section{$BBe?tBN>e$N1i;;$K$D$$$F(B}
        !            33:
        !            34:
        !            35: \subsection{$BBe?tBN$N85$NI=8=J}K!(B}
        !            36:
        !            37: $B$h$/CN$i$l$F$$$k$h$&$K(B, $BG$0U$NBe?tBN(B $F$ $B$O86;O85$r$b$D(B. $B$9$J$o$A(B, $B$"(B
        !            38: $B$kBe?tE*?t(B $\alpha$ $B$,B8:_$7$F(B $F=\Q(\alpha)$ $B$H=q$1$k(B. $B$h$C$F(B,
        !            39: $\alpha$ $B$N(B $\Q$ $B>e$N:G>.B?9`<0$r(B $m(t)$ $B$H$9$l$P(B,
        !            40: $F=\Q[t]/(m(t))$ $B$G$"$j(B, $F$ $B$N85$O0lJQ?tB?9`<0$GI=8=$G$-$k(B. $B$7$+$7(B,
        !            41: $B7W;;8zN($r9M$($?>l9g(B, $B86;O85$K$h$kI=8=$O(B, $B78?t%5%$%:$NA}Bg$r>7$-$d$9$$(B
        !            42: $B$?$aK>$^$7$/$J$$(B. $B$3$N$?$a(B, $F$ $B$rC`<!3HBg$H$7$FM?$($k$N$,8=<BE*$G$"$k(B.
        !            43: $B$9$J$o$A(B,
        !            44: $$F_0=\Q,\quad F_i = F_{i-1}(\alpha_i)\quad (i=1,\ldots,n),\quad F=F_m$$
        !            45: $B$G(B, $B3F(B $\alpha_i$ $B$,(B $F_{i-1}$ $B>eBe?tE*$G(B, $F_{i-1}$ $B>e$N:G>.(B
        !            46: $BB?9`<0$,(B $m_i(t,\alpha_1,\ldots,\alpha_{i-1})$ $B$GM?$($i$l$F$$$k$H$9$k(B
        !            47: $B$N$G$"$k(B. $m_i$ $B$N4{Ls@-$N%A%'%C%/$K$O$7$P$7$P:$Fq$JB?9`<00x?tJ,2r$,I,(B
        !            48: $BMW$H$J$k$,(B, $B9,$$(B, knapsack factorization $B%"%k%4%j%:%`$K$h$j(B, $B%A%'%C%/(B
        !            49: $B2DG=$JB?9`<0$NHO0O$,BgI}$K3HBg$7$?(B.  $B0J2<$G$O(B, $B4{$K4{Ls@-$,J]>Z$5$l$F(B
        !            50: $B$$$kC`<!3HBg$,M?$($i$l$F$$$k$H$9$k(B. $B%$%G%"%k$N8@MU$G=R$Y$l$P(B,
        !            51: $$I=\langle m_1(x_1),m_2(x_1,x_2),\ldots,m_n(x_1,\ldots,x_n)\rangle$$
        !            52: $B$,(B $\Q[X]=\Q[x_1,\ldots,x_n]$ $B$N6KBg%$%G%"%k$H$$$&$3$H$K$J$k(B.
        !            53:
        !            54: \subsection{$B4JLs2=(B}
        !            55:
        !            56: $B3F(B $m_i$ $B$O(B,
        !            57: $$m_i(x_1,\dots,x_i)=c_{d_i} x_i^{d_i}+c_{d_{i-1}}(x_1,\ldots,x_{i-1})x_i^{d_i-1}+\cdots+c_0(x_1,\ldots,x_{i-1})$$
        !            58: ($c_{d_i}\in \Z$, $c_j(x_1,\ldots,x_{i-1})\in \Z[x_1,\ldots,x_{i-1}]$)
        !            59: $B$H$$$&7A$G$"$k$H$7$F$h$$(B. $B$5$i$K(B, $m_i$ $B$O(B $\langle m_1,\ldots,m_{i-1}\rangle$ $B$K4X$7$F@55,7A(B, $B$9$J$o$A(B $\deg_{x_j}(m_i) < d_j$ ($j=1,\ldots,i-1$)
        !            60: $B$H$9$k(B. $B$3$N$H$-(B, $G=\{m_1,\ldots,m_n\}$ $B$O(B,
        !            61: $x_n > x_{n-1} > \cdots > x_1$ $B$J$k<-=q<0=g=x$K4X$9$k(B $I$ $B$N%0%l%V%J!<4pDl$H$J$C$F$$$k(B.
        !            62: $Q[X]/I$ $B$N85(B $h(x) \bmod I$ $B$KBP$7(B,
        !            63: $h_0 \equiv h \bmod I$, $\deg_{x_i}(h_0) < d_i$ $B$J$k(B $h_i$ $B$O(B
        !            64: $G$ $B$K4X$9$k@55,7A(B $\NF_G(h)$ $B$KEy$7$$(B.
        !            65:
        !            66: $h_0$ $B$O(B, $B%0%l%V%J!<4pDl$r;}$A=P$9$^$G$b$J$/(B, 1 $BJQ?tB?9`<0$N>jM>7W;;$K(B
        !            67: $B$h$jM?$($i$l$k(B.  $BNc$($P(B, $h$ $B$+$i(B, $m_n, m_{n-1},\ldots,m_1$ $B$H$$$&=g(B
        !            68: $B$K>jM>$r7W;;$7$F$$$1$PF@$i$l$k(B. $B$b$A$m$s(B, $m_i$ $B$K$h$k>jM>$O(B $x_i$ $B$r(B
        !            69: $B<gJQ?t$H$7$F7W;;$9$k(B. $B$7$+$7$3$NJ}K!$O(B, $B8zN($+$i8+$?>l9g:G0-$G$"$k(B. $B$J(B
        !            70: $B$<$J$i(B, $m_i$ $B$K$h$k>jM>$r7W;;$9$k$H(B, $B0lHL$K(B $j<i$ $B$J$k(B $x_j$ $B$K4X$9$k(B
        !            71: $B<!?t$,>e$,$k(B. $BFC$K(B, $m_2$ $B$^$G$N>jM>$r7W;;$7$?CJ3,$N>jM>$O(B, $x_1$ $B$K4X(B
        !            72: $B$9$k<!?t$,BgJQ9b$/$J$C$F$$$k2DG=@-$,$"$k(B. $B$=$3$G(B, $i$ $B$,>.$5$$(B $m_i$
        !            73: $B$K$h$k>jM>7W;;$rM%@h$5$;$kJ}K!$,9M$($i$l$k(B. $B$3$NJ}K!$O(B, $B>e$NJ}K!$h$j(B
        !            74: $B$O8zN($,$h$$$H9M$($i$l$k$,(B, $B$d$O$j2<$N=g=x$NJQ?t$N<!?t$,5^$K>e$,$k(B
        !            75: $B$3$H$OK>$^$7$/$J$$(B.
        !            76:
        !            77: $B$3$N>l9g(B, $B<B$O(B $G$ $B$K$h$kC19`4JLs$rMQ$$$l$P(B, $B8zN($h$/>jM>(B
        !            78: $B7W;;$r9T$&$3$H$,$G$-$k(B. $B$3$N:](B, $B3F4JLs%9%F%C%W$KMQ$$$k(B $m_i$
        !            79: $B$H$7$F$O(B, $i$ $B$N>.$5$$$b$N$rM%@h$9$kI,MW$,$"$k(B.
        !            80:
        !            81: \begin{Exp}\rm
        !            82: \label{exp:degree7}
        !            83: $m_1(x_1)=x_1^7-7x_1+3$,\\
        !            84: $m_2(x_1,x_2)=x_2^6+x_1x_2^5+x_1^2x_2^4+x_1^3x_2^3+x_1^4x_2^2+x_1^5x_2+x_1^6-7$,\\
        !            85: $m_3(x_1,x_2,x_3)=63x_3^4+((-2x_1^5-5x_1^4-x_1^3-7x_1^2+3x_1+6)x_2^5+(-5x_1^5-5x_1^3-3x_1^2+7x_1)x_2^4+(-x_1^5-5x_1^4+8x_1^2+4x_1-24)x_2^3+(-7x_1^5-3x_1^4+8x_1^3+6x_1^2-28x_1+6)x_2^2+(3x_1^5+7x_1^4+4x_1^3-28x_1^2+14x_1+18)x_2+6x_1^5-24x_1^3+6x_1^2+18x_1+12)x_3^3+((x_1^4-2x_1^3-4x_1^2+5x_1)x_2^5+(x_1^5-2x_1^3+12x_1^2+22x_1)x_2^4+(-2x_1^5-2x_1^4+8x_1^3+20x_1^2+15x_1-12)x_2^3+(-4x_1^5+12x_1^4+20x_1^3+12x_1^2+5x_1+15)x_2^2+(5x_1^5+22x_1^4+15x_1^3+5x_1^2+25x_1-6)x_2-12x_1^3+15x_1^2-6x_1+48)x_3^2+((5x_1^4+2x_1^3+x_1^2+16x_1-18)x_2^5+(5x_1^5+6x_1^4-4x_1^3+18x_1^2-13x_1)x_2^4+(2x_1^5-4x_1^4+16x_1^3-11x_1^2-18x_1+48)x_2^3+(x_1^5+18x_1^4-11x_1^3-6x_1^2+43x_1-6)x_2^2+(16x_1^5-13x_1^4-18x_1^3+43x_1^2+14x_1-48)x_2-18x_1^5+48x_1^3-6x_1^2-48x_1+24)x_3+(4x_1^5-x_1^4+9x_1^3-2x_1^2-16x_1+6)x_2^5+(-x_1^5+6x_1^4+2x_1^3-15x_1^2-x_1+45)x_2^4+(9x_1^5+2x_1^4-22x_1^3-5x_1^2+40x_1)x_2^3+(-2x_1^5-15x_1^4-5x_1^3+33x_1^2-8x_1+84)x_2^2+(-16x_1^5-x_1^4+40x_1^3-8x_1^2+36x_1-6)x_2+6x_1^5+45x_1^4+84x_1^2-6x_1-84$
        !            86: $B$H$9$k(B. $m_1(\alpha_1)=0$, $m_2(\alpha_1,\alpha_2)=0$, $m_3(\alpha_1,\alpha_2,\alpha_3)=0$ $B$rK~$?$9(B $\alpha_1$, $\alpha_2$, $\alpha_3$ $B$K$h$j(B
        !            87: $F=\Q(\alpha_1,\alpha_2,\alpha_3)$ $B$H$9$k(B. $(\alpha_1+\alpha_2+\alpha_3)^{20}$
        !            88: $B$r(B, $m_1,m_2,m_3$ $B$N=g$KMQ$$$kC19`4JLs$K$h$j4JLs$9$k$H(B 0.1 $BIC$G7W;;$G$-$k$,(B,
        !            89: $B5U=g$G9T$&$H(B 260 $BIC$+$+$k(B. $B$3$N:9$O4JLs$5$l$kBP>]$,Bg$-$/$J$k$H5^B.$K(B
        !            90: $BA}Bg$9$k(B.
        !            91: \end{Exp}
        !            92:
        !            93: \subsection{$B5U857W;;(B}
        !            94:
        !            95: $B4JLs7W;;$HJB$s$GBe?tBN>e$N8zN(E*7W;;$r:$Fq$K$9$k$b$N$,(B, $B5U857W;;$G$"$k(B.
        !            96: $BC13HBg$N>l9g$K$O(B, $B3HD%(B Euclid $B8_=|K!(B, $BNc$($PItJ,=*7k<0%"%k%4%j%:%`$K$h(B
        !            97: $B$j(B, $B3HBg<!?t(B $d$ $B$K4X$7(B $O(d^2)$ $B$N<j4V$G7W;;$G$-$k(B. $B$3$NJ}K!$O(B, $BC`<!(B
        !            98: $B3HBg$KBP$7$F$b:F5"E*$KE,MQ$G$-$k$,(B, $B7W;;8zN(>e<o!9$NLdBj$r@8$8$k(B.
        !            99: \begin{itemize}
        !           100: \item $BCf4V<0KDD%(B
        !           101:
        !           102: $h(x_1,\ldots,x_n) \bmod I$ $B$N5U85$r7W;;$9$k>l9g(B,
        !           103: $B$^$:JQ?t(B $x_n$ $B$K4X$7(B $m_n(x_1,\ldots,x_n)$ $B$H(B
        !           104: $B3HD%(B Euclid $B8_=|K!$rE,MQ$9$k$H(B, $ah+bm_n=r(x_1,\ldots,x_{n-1})$
        !           105: $B$H$J$k(B $a$, $b$, $r$ $B$rF@$k(B. $r \bmod I$ $B$N5U85$r(B $s \bmod I$ $B$H$9$l$P(B,
        !           106: $h \bmod I$ $B$N5U85$O(B $as \bmod I$ $B$H$J$k$,(B, $B7W;;J}K!$K$h$C$F$O(B
        !           107: $r$ $B$N5U85$,5pBg$K$J$k>l9g$,$"$k(B.
        !           108:
        !           109: \item $B4JLs2=$H$N4X78(B
        !           110:
        !           111: $h$ $B$r(B $n-1$ $BJQ?tB?9`<04D>e$N(B 1 $BJQ?tB?9`<0$H8+$J$7$FItJ,=*7k<0(B
        !           112: $B%"%k%4%j%:%`$rE,MQ$9$l$P(B, $B78?t$N=|;;$O@0=|$H$J$k$,(B, $B$3$l$i$K(B
        !           113: $B8=$o$l$kJQ?t$KBP$9$k4JLs2=$,9T$o$l$J$$$N$G(B, $B0lHL$KBg$-$JB?9`<0(B
        !           114: $B$,78?t$K8=$o$l$k(B. $B0lJ}$G(B, $B78?t$N4JLs2=$r5v$;$P(B, $B$=$l$i$rI=8=(B
        !           115: $B$9$kB?9`<0$,Bg$-$/$J$i$:$K7W;;$G$-$k$,(B, $B=|;;<+?H$,(B
        !           116: $BBN1i;;$H$J$j(B, $B5U857W;;$,I,MW$H$J$k(B.
        !           117: \end{itemize}
        !           118:
        !           119: $B4{$K(B Asir $B$N(B {\tt sp} $B%Q%C%1!<%8$K$*$1$kBe?tBN>e$N0lJQ?tB?9`<0(B
        !           120: GCD  $B$G$bMQ$$$i$l$F$$$k$h$&$K(B, $BBe?tE*?t$N7W;;$K$O%b%8%e%i!<7W;;$,(B
        !           121: $BM-8z$G$"$k(B \cite{NORO96}, \cite{HOEI02}.
        !           122: $B5U85$N%b%8%e%i!<7W;;$K$h$k7W;;K!$H$7$F$O(B, $B<!$N(B 2 $B$D$,M-NO$G$"$k(B.
        !           123:
        !           124: \begin{itemize}
        !           125: \item $BCf9q>jM>DjM}(B
        !           126:
        !           127: $B==J,B?$/$NK!(B $p$ $B$KBP$7(B, $BK!(B $p$ $B$G$N5U85$r7W;;$7$FCf9q>jM>DjM}$K$h$j(B
        !           128: $B7k9g$7(B, $B@0?t(B-$BM-M}?tJQ49$K$h$j5U85$rF@$kJ}K!$G$"$k(B. $BK!(B $p$ $B$G9M$($k$H(B,
        !           129: $B78?t4D$,BN$G$O$J$/$J$k$,(B, $BM-8B8D$N(B $p$ $B$r=|$$$FK!(B $p$ $B$G$N5U85$O(B
        !           130: $B7W;;$G$-$k(B. $B$3$N7W;;$,(B, $B8_=|K!$N$h$&$K(B $O(d^2)$ $B$G7W;;$G$-$k$J$i(B,
        !           131: 1 $B%9%F%C%W$"$?$j(B$O(d^2)$ $B$N<j4V$r(B, $B7k2L$N78?t$NBg$-$5$KHfNc$9$k(B
        !           132: $B2s?t7+$jJV$9$3$H$G5U85$,7W;;$G$-$k(B.
        !           133:
        !           134: \item $BL$Dj78?tK!(B + Hensel lifting
        !           135:
        !           136: $B5U85$rL$Dj78?tK!$K$h$j5a$a$k$3$H$b$G$-$k(B. $B$9$J$o$A(B,
        !           137: $\bmod I$ $B$G$NC19`<04pDl(B
        !           138: $$M=\{x_1^{e_1}\cdots x_n^{e_n} \bmod I \,|\, 0 \le e_i \le d_i-1
        !           139: (i=1,\ldots,n)\}$$ $B$K$h$j5U85$r(B $u = \sum_{t \in M} a_t t$ $B$HI=$7(B, $hu
        !           140: \equiv 1 \bmod I$ $B$+$i(B $a_t$ $B$N@~7AJ}Dx<07O$r:n$C$F2r$/J}K!$G$"$k(B. $B$3(B
        !           141: $B$NJ}K!$O(B, $B3HBg<!?t(B $d=\prod d_i$ $B$K4X$7(B $O(d^3)$ $B$N2rK!$H$J$C$F$7$^$&(B
        !           142: $B$,(B, $B@~7AJ}Dx<07O$N5a2r$K(B Hensel lifting+$B@0?t(B-$BM-M}?tJQ49$r;H$&$3$H$G(B,
        !           143: $O(d^3)$ $B$NItJ,$rM-8BBN>e$K$N$_8BDj$G$-$k(B. $B$h$C$F(B, $B$b$77k2L$,Bg$-$$78(B
        !           144: $B?t$r$b$D>l9g$K$O(B, $B<B:]$N7W;;;~4V$O(B 1 $B%9%F%C%W$"$?$j(B $O(d^2)$ $B$N(B Hensel
        !           145: lifting $B$K$h$j7hDj$5$l$k(B.  $B$^$?(B, $BCf4V<0$r:n$i$:(B, $\NF_G(th)$ ($t \in
        !           146: M$) $B$N7W;;$N$_$G@~7AJ}Dx<0$,$G$-$k$3$H$+$i(B, $B>e$G=R$Y$?$h$&$JCf4V<0KDD%(B
        !           147: $B$dBN=|;;$K$h$kLdBj$O8=$o$l$J$$(B.
        !           148: \end{itemize}
        !           149:
        !           150: \section{$BBe?tBN>e$N%0%l%V%J!<4pDl7W;;(B}
        !           151:
        !           152: \subsection{monic $B2=(B}
        !           153: Buchberger $B%"%k%4%j%:%`$r$O$8$a$H$9$k%0%l%V%J!<4pDl7W;;%"%k%4%j%:%`$O(B
        !           154: $BG$0UBN>e$G<B9T2DG=$G$"$k$,(B, $BBN$K$h$C$F$O78?tKDD%$NLdBj$,@8$:$k(B
        !           155: $B$N$G(B, $B<o!9$NCm0U$,I,MW$H$J$k(B. $F$ $B$,Be?tBN$N>l9g(B, $B78?t$N@Q$N(B
        !           156: $B4JLs2=(B, $B$*$h$S(B, monic $B2=$K$*$1$kBN=|;;$NLdBj$,$"$j(B, $B>/$/$H$b(B
        !           157: Risa/Asir $B$K$*$$$F$O(B, $B$3$l$^$GBe?tBN>e$N%0%l%V%J!<4pDl7W;;$O(B
        !           158: $BDs6!$7$F$3$J$+$C$?(B. $BBe$o$j$K(B, $B<!$K$h$j7W;;$,2DG=$G$"$k(B.
        !           159: \begin{Th}
        !           160: $F = \Q[\alpha_1,\ldots,\alpha_l] = \Q[t_1,\ldots,t_l]/I$, $I=\langle m_1(t_1),\ldots,m_l(t_1,\ldots,t_l)\rangle$, $B$H$7(B,
        !           161: $J =\langle B \rangle \subset R = F[x_1,\ldots,x_n]$
        !           162: $B$r(B $R$ $B$N??$N%$%G%"%k$H$9$k(B. $<$ $B$r(B $R$ $B$N9`=g=x$H$9$k(B. $R$ $B$N9`=g=x(B $<_F$ $B$r(B $<$ $B$*$h$S(B
        !           163: $F$ $B$N(B $t_1 < \cdots < t_l$ $B$J$k<-=q<0=g=x$+$i$J$k%V%m%C%/=g=x(B
        !           164: ($t_1^{a_1}\cdots t_l^{a_l} <_F x_1^{b_1}\cdots x_n^{b_n}$)
        !           165: $B$H$9$k(B. $B$3$N$H$-(B, $B_F = B \cup \{m_1,\ldots,m_l\}$ $B$N(B $<_F$ $B$K4X$9$k(B
        !           166: $B%0%l%V%J!<4pDl(B $G_F$ $B$N85$N$&$AJQ?t(B $x_1,\ldots,x_n$ $B$r4^$`$b$N$N=89g(B
        !           167: $G$ $B$O(B, $J$ $B$N(B $<$ $B$K4X$9$k%0%l%V%J!<4pDl$H$J$k(B. $G_F$ $B$,4JLs(B
        !           168: $B%0%l%V%J!<4pDl$J$i$P(B, $G$ $B$N85$NF,9`$O(B $t_1,\ldots,t_l$ $B$r4^$^$J$$(B.
        !           169: \end{Th}
        !           170: $G_F$ $B$r7W;;$9$k>l9g(B, $B<B:]$N%"%k%4%j%:%`$N<B9T$r4Q;!$9$k$H(B,
        !           171: $B@8@.$5$l$kCf4V4pDl$NF,9`$N(B $t$ $BJQ?t$,$@$s$@$s8:$C$F9T$-?k$K>CLG(B
        !           172: $B$9$k$3$H$,J,$+$k(B. $B$9$J$o$A(B, $BF,9`$N78?t$N5U85$r$+$1$kA`:n$r(B
        !           173: S-$BB?9`<0$HC19`4JLs$K$h$j9T$C$F$$$k$3$H$K$J$k(B. $B$3$N$3$H$O(B
        !           174: S-$BB?9`<0$N?t$NA}Bg$r0z$-5/$3$9(B. S-$BB?9`<0$N=hM}$N=g=x$O(B sugar
        !           175: strategy $B$J$I(B, $B$J$s$i$+$N4p=`$K$h$j5!3#E*$K7h$a$i$l$k$,(B,
        !           176: S-$BB?9`<0$,A}$($k$H(B, $BITE,@Z$J=g=x$G=hM}$5$l$k2DG=@-$bA}$((B,
        !           177: $BITI,MW$J78?tKDD%$r0z$-5/$3$92DG=@-$,$"$k(B. $B$=$3$G(B, $BA0@a$N5U85(B
        !           178: $B7W;;$rMQ$$$F(B, Buchberger $B%"%k%4%j%:%`$K$*$1$k(B, 0 $B$K4JLs$5$l$J$$(B
        !           179: $B85$N4pDl$N=hM}$r<!$N$h$&$KJQ99$9$k(B:
        !           180: \begin{itemize}
        !           181: \item $BDL>o$N=hM}(B
        !           182:
        !           183: $S(f,g) \tmred{G} h \neq 0$ $B$J$i$P(B, $G \leftarrow G \cup \{h\}$
        !           184:
        !           185: \item $BJQ998e$N=hM}(B
        !           186:
        !           187: $S(f,g) \tmred{G} h(x,t) \neq 0$ $B$J$i$P(B,
        !           188: $h(x,\alpha)$ $B$r(B monic $B2=$7$?$b$N(B
        !           189: $\tilde{h}(x,\alpha)$ $B$r:n$j(B,
        !           190: $G \leftarrow G \cup \{\tilde{h}(x,t)\}$
        !           191: \end{itemize}
        !           192: $B$3$N$h$&$JJQ99$r9T$C$F$b(B $G_F$ $B$,7W;;$G$-$k$3$H$O$"$-$i$+$G(B
        !           193: $B$"$m$&(B.
        !           194:
        !           195: \subsection{trace $B%"%k%4%j%:%`(B}
        !           196:
        !           197: monic $B2=$r9T$C$?$H$7$F$b(B, $B<B:]$K$O(B trace $B%"%k%4%j%:%`$rE,MQ$9$k$N$,0B(B
        !           198: $BA4$G$"$m$&(B. $\bmod p$ $B$G$N(Btrace $B%"%k%4%j%:%`$N@5Ev@-$O(B, $\Q$ $B>e$N4JLs(B
        !           199: $B2=$K(B $p$ $B$G3d$j@Z$l$kJ,Jl$r$b$DM-M}?t$,8=$o$l$J$$$3$H(B, $B$5$i$K4JLs7k2L(B
        !           200: $B$N@55,7A$NF,78?t$,(B $p$ $B$G3d$j@Z$l$J$$$3$H$,I,MW$H$J$k(B. $BA0@a$NJQ99$r9T$C(B
        !           201: $B$?>l9g(B, $B87L)$K$O(B, $BF,78?t$N5U857W;;$K$b(B $p$ $B$G3d$l$kJ,Jl$,8=$o$l$J$$$3(B
        !           202: $B$H$rMW5a$9$k$3$H$K$J$k$,(B, $B$3$N>r7o$r4K$a$F(B, $B7k2L$r(B monic $B2=$7$?$"$H(B,
        !           203: $p$ $B$G3d$l$kJ,Jl$,8=$o$l$J$$$3$H(B, $B$H$9$k$3$H$b$G$-$k(B.  $B<B:](B, $B$3$N7k2L(B
        !           204: $B<+?H$OF~NO%$%G%"%k$N85$G$"$k$3$H$O3N$+$G(B, $B$3$N85$,$"$i$+$8$a%$%G%"%k$N(B
        !           205: $B@8@.85$N0l$D$G$"$C$?$H9M$($l$P$h$$(B.
        !           206:
        !           207: trace $B%"%k%4%j%:%`$N<B8=$K$D$$$F$O$$$/$D$+$N%P%j%(!<%7%g%s$,9M$($i$l$k(B.
        !           208: $B$?$H$($P(B, $\overline{I}=I \bmod p$ $B$,:,4p%$%G%"%k$K$J$k$h$&$J(B $p$ $B$r$H$l$P(B,
        !           209: $GF(p)[t]/\overline{I}$ $B$,$$$/$D$+$NM-8BBN$ND>OB$KJ,2r$9$k(B.
        !           210: $I_p$ $B$r(B, $I$ $B$N78?t$r(B $\Q_{<p>}=\{a/b\,|\, a, b \in Z, p \not{|} b\}$
        !           211: $B$K@)8B$7$?$b$N$H$7(B, $\phi$ $B$r(B $I_p$ $B$+$i$"$kD>OB@.J,$X$N(B
        !           212: $B<M1F$H$9$l$P(B, $B$3$l$b(B trace $B%"%k%4%j%:%`$r<B8=$9$k(B. $B$3$l$K$h$j(B,
        !           213: trace $B$N7W;;$O(B, $BM-8BBN>e$G$NF~NOB?9`<0=89g$N%0%l%V%J!<4pDl7W;;$H(B
        !           214: $B$J$k$?$a(B, $B7W;;$N<j4V$r8:$i$;$k2DG=@-$,$"$k(B.
        !           215:
        !           216:
        !           217: \section{Risa/Asir $B>e$G$N<BAu(B}
        !           218:
        !           219: \subsection{$BC`<!Be?t3HBg(B}
        !           220:
        !           221: Risa/Asir $B$K$O(B, $BC`<!Be?t3HBg$N85$NI=8=$H$7$F(B,
        !           222: $B:F5"I=8=B?9`<0$r%\%G%#It$K$b$D(B {\tt Alg} $B$,$"$j(B, $BBe?tBN>e$N0x?tJ,2r(B
        !           223: $B$*$h$S:G>.B?9`<07W;;$K4{$KMQ$$$i$l$F$$$k$,(B, $B4JLs7W;;(B, $B5U857W;;$r4^$`(B
        !           224: $B$[$H$s$I$N4X?t$O(B, {\tt sp} $BCf$K%f!<%64X?t$H$7$F(B
        !           225: $B=q$+$l$F$$$F9b8zN($OK>$a$J$$(B. $BFC$K(B, $B4{$K=R$Y$?$h$&$J(B, $BC19`4JLs(B
        !           226: $B$K$h$k4JLs$r9T$&$N$K$OE,$7$F$$$J$$$?$a(B, $BJ,;6I=8=B?9`<0$r%\%G%#It(B
        !           227: $B$K$b$DC`<!Be?t3HBg$NI=8=$r?7$?$KDj5A$7$?(B.
        !           228: \begin{verbatim}
        !           229: typedef struct oDAlg {
        !           230:         short id;
        !           231:         char nid;
        !           232:         char pad;
        !           233:         struct oDP *nm;
        !           234:         struct oQ *dn;
        !           235: } *DAlg;
        !           236: \end{verbatim}
        !           237: {\tt DAlg} $B$O%\%G%#It$H$7$F(B, $BJ,;6I=8=B?9`<0$G$"$k(B {\tt nm} $B$*$h$S(B
        !           238: $BM-M}?t$G$"$k(B {\tt dn} $B$r$b$D(B.
        !           239: $BBe?tE*?t$H$7$F$O(B {\tt nm/dn} $B$rI=$9$,(B, {\tt nm} $B$O@0?t78?t$N(B
        !           240: $BJ,;6I=8=B?9`<0(B, {\tt dn} $B$O@0?t$K8BDj$9$k(B. $B$9$J$o$A(B,
        !           241: $B%\%G%#It$NM-M}?t78?t$rDLJ,$7$FI=<($9$k$HLsB+$9$k$N$G$"$k(B.
        !           242: $B$^$?(B, $B78?tBN$G$"$kC`<!3HBgBN$r(B, $B$=$l$r@8@.$9$kBe?tE*?t$N%j%9%H(B
        !           243: $B$G;XDj$9$k4X?t(B {\tt set\_field()} $B$rMQ0U$7$?(B. $B$3$N8F$S=P$7(B
        !           244: $B$K$h$j(B, $B4JLs7W;;(B, $B5U857W;;$KI,MW$J(B, $B:G>.B?9`<0%j%9%H$d(B
        !           245: $BC19`<04pDl$,7W;;$5$l(B, $BFbItE*$K78?tBN>pJs$H$7$F%;%C%H(B
        !           246: $B$5$l$k(B.
        !           247:
        !           248: {\tt DAlg} $B7?$N%*%V%8%'%/%H$O(B, {\tt Alg} $B7?$+$i$NJQ494X?t(B
        !           249: {\tt algtodalg()} $B$K$h$j@8@.$5$l$k(B. $B$=$N5UJQ49$O(B {\tt dalgtoalg()}
        !           250: $B$G$"$k(B.
        !           251:
        !           252: \subsection{$B%0%l%V%J!<4pDl7W;;(B}
        !           253:
        !           254: $B8=:_$N;n83E*<BAu$O(B, {\tt nd\_gr} $B$*$h$S(B {\tt nd\_gr\_trace} $B$r(B, $BF~NOB?(B
        !           255: $B9`<0=89g$K:G>.B?9`<0$rDI2C$7$F<B9T$7(B, $BA0@a$G=R$Y$?$h$&$JJQ99(B (monic $B2=(B)
        !           256: $B$r2C$($k(B, $B$H$$$&7A$G9T$C$F$$$k(B. $B$3$l$KBP$7(B, $BBe?tE*?t$r40A4$K78?t$K<h$j(B
        !           257: $B9~$s$G(B, $B78?t$K4X$7$F4{$K=R$Y$?$h$&$J4JLs2=$*$h$S5U857W;;$r9T$&$H$$$&J}(B
        !           258: $BK!$b9M$($i$l$k(B. $BA0<T$N>l9g(B, $B4JLs2=$,(B $\Q$ $B>e$G9T$o$l$k$N$G(B, $B4{$K<BAu$7(B
        !           259: $B$F$"$k(B, $B78?t$N(B content $B=|5n$,<+F0E*$KE,MQ$5$l$k(B.  sugar $BCM$K(B, $BBe?tE*?t(B
        !           260: $B$N<!?t$,H?1G$5$l$k$N$rKI$0$?$a(B, $BBe?tE*?t$KBP1~$9$k(Bweight $B$r(B 0 $B$K@_Dj$7(B
        !           261: $B$F$$$k(B.  $B$7$+$7(B, $B@F<!2=$K$D$$$F$OIT<+A3$J<BAu$r$;$6$k$rF@$J$$(B.  $B8e<T$O(B
        !           262: $B<+A3$J<BAu$H$b8@$($k$,(B, content $B=|5n$KAjEv$9$kJ}K!$r?7$?$K9M0F$9$kI,MW(B
        !           263: $B$,$"$j(B, $B:#8e$N2]Bj$H$7$?(B.
        !           264:
        !           265: \section{$B%?%$%_%s%0%G!<%?(B}
        !           266:
        !           267: $B0J2<(B, $BFC$KCG$i$J$$8B$j(B, $B9`=g=x$O(B DRL $B$H$9$k(B.
        !           268: \begin{Exp}\rm
        !           269: \label{exp:c7}
        !           270: \begin{eqnarray*}
        !           271: Cyc&=&\{f_1,f_2,f_3,f_4,f_5,f_6,f_7\}\\
        !           272: f_1&=&\omega c_5c_4c_3c_2c_1c_0-1\\
        !           273: f_2&=&(((((c_5+\omega )c_4+\omega c_5)c_3+\omega c_5c_4)c_2+\omega c_5c_4c_3)c_1+\omega c_5c_4c_3c_2)c_0+\omega c_5c_4c_3c_2c_1\\
        !           274: f_3&=&((((c_4+\omega )c_3+\omega c_5)c_2+\omega c_5c_4)c_1+\omega c_5c_4c_3)c_0+c_5c_4c_3c_2c_1+\omega c_5c_4c_3c_2\\
        !           275: f_4&=&(((c_3+\omega )c_2+\omega c_5)c_1+\omega c_5c_4)c_0+c_4c_3c_2c_1+c_5c_4c_3c_2+\omega c_5c_4c_3\\
        !           276: f_5&=&((c_2+\omega )c_1+\omega c_5)c_0+c_3c_2c_1+c_4c_3c_2+c_5c_4c_3+\omega c_5c_4\\
        !           277: f_6&=&(c_1+\omega )c_0+c_2c_1+c_3c_2+c_4c_3+c_5c_4+\omega c_5\\
        !           278: f_7&=&c_0+c_1+c_2+c_3+c_4+c_5+\omega
        !           279: \end{eqnarray*}
        !           280:
        !           281: $Cyc$ $B$O(B, cyclic-7 $B$K$*$$$F(B, $c_6$ $B$r(B 1 $B$N86;O(B 7 $B>h:,(B
        !           282: $\omega$ $B$KCV$-49$($?$b$N$G$"$k(B. $Cyc$ $B$N(B $\Q(\omega)$ $B>e$G$N(B
        !           283: $B%0%l%V%J!<4pDl7W;;$O(B, $B@F<!2=(B trace $B%"%k%4%j%:%`$K$h$j(B 22 $BIC(B
        !           284: $B$G7W;;$G$-$k(B. $B$3$N$&$A(B, monic $B2=$N7W;;;~4V$O(B 2.2 $BIC(B, $B$=$N$&$A(B
        !           285: $B5U857W;;$O(B 0.2$BIC(B $B$G$"$k(B.
        !           286:
        !           287: $\omega$ $B$N:G>.B?9`<0$rE:2C$7$F(B $\Q$ $B>e$G(B
        !           288: $B7W;;$9$k>l9g(B 220 $BIC$+$+$k(B.
        !           289: \end{Exp}
        !           290:
        !           291: \begin{Exp}\rm
        !           292: \label{exp:cap}
        !           293: \begin{eqnarray*}
        !           294: Cap&=&\{f_1,f_2,f_3,f_4\}\\
        !           295: f_1&=&(2ty-2)x-(\alpha+\beta)zy^2-z\\
        !           296: f_2&=&2\beta\alpha^4zx^3+(4ty+\beta)x^2+(4zy^2+4z)x+2ty^3-10y^2-10ty+2\alpha^2+\beta^2\\
        !           297: f_3&=&(t^2-1)x+(\beta\alpha^4+\beta^3\alpha^3)tzy-2z\\
        !           298: f_4&=&(-z^2+4t^2+\beta\alpha+2\beta^3)zx+(4tz^2+2t^3-10t)y+4z^2-10t^2+\beta\alpha^3\\
        !           299: m_1&=&u^7-7u+3\\
        !           300: m_2&=&u^6+\alpha u^5+\alpha^2u^4+\alpha^3u^3+\alpha^4u^2+\alpha^5u+\alpha^6-7
        !           301: \end{eqnarray*}
        !           302: $Cap$ $B$O(B $Caprasse$ \cite{SYMBDATA}
        !           303: $B$N78?t$r%i%s%@%`$KBe?tE*?t$KCV$-49$($?(B
        !           304: $B$b$N$G$"$k(B. $\alpha$, $\beta$ $B$O(B $t^7-7t+3$ $B$N(B 2 $B:,$G(B,
        !           305: $\alpha$ $B$N(B $\Q$$B>e$N:G>.B?9`<0$,(B $m_1(u)$, $\beta$ $B$N(B $\Q(\alpha)$
        !           306: $B>e$N:G>.B?9`<0$,(B $m_2(u)$ $B$G$"$k(B. $Cap$ $B$N(B $\Q(\alpha,\beta)$ $B>e(B
        !           307: $B$G$N%0%l%V%J!<4pDl7W;;$O(B trace $B%"%k%4%j%:%`$G(B 589 $BIC(B ($BFb(B monic $B2=(B 36 $BIC(B),
        !           308: $\Q$ $B>e$G$O@F<!2=$7$F$b(B, 1 $B;~4VBT$C$F$b=*N;$7$J$$(B.
        !           309: \end{Exp}
        !           310:
        !           311: \begin{Exp} \rm
        !           312: $BNc(B \ref{exp:degree7} $B$GDj5A$5$l$k(B $F$ $B$O(B, $f(x)=x^7-7x+3$ $B$N:G>.J,2rBN(B
        !           313: $B$G$"$k(B. $f(x)$ $B$N(B $F$ $B>e0x?tJ,2r$K8=$l$k(B, $F$ $B>e$N(B 2 $B$D$N(B 2 $B<!<0$N(B
        !           314: GCD $B7W;;(B (GCD $B$O(B 1 $B<!<0(B) $B$r(B $F$ $B>e$N%0%l%V%J!<4pDl7W;;$K$h$j9T$&$H(B,
        !           315: 0.8 $BIC$G=*N;$9$k(B. $B5U857W;;(B 1 $B2sJ,$,7W;;;~4V$NBgItJ,$r@j$a$k(B. $B0lJ}(B,
        !           316: $B$3$l$r(B $\Q$ $B>e$G9T$&$H(B, 60 $BIC$+$+$k(B.
        !           317: \end{Exp}
        !           318:
        !           319: \section{$B$*$o$j$K(B}
        !           320: $BK\9F$GDs0F$7$?J}K!$K$h$j(B, $BBe?tBN>e$N%0%l%V%J!<4pDl7W;;$,(B, $BC1$K:G>.B?9`(B
        !           321: $B<0$rE:2C$7$FM-M}?tBN>e$G7W;;$9$k$h$j9bB.$K7W;;$G$-$k>l9g$,$"$k$3$H$,<((B
        !           322: $B$;$?(B.  $B$7$+$7(B, $B$3$N$h$&$J7W;;$,:$Fq$G$"$k$3$H$K$OJQ$o$j$J$$(B. $B$h$jK\<A(B
        !           323: $BE*$J2~NI(B, $B?7%"%k%4%j%:%`$bI,MW$G$"$m$&(B.
        !           324:
        !           325: $B:#8e$NM=Dj$H$7$F0J2<$r5s$2$F$*$/(B.
        !           326: \begin{itemize}
        !           327: \item DCGB $B$H$N4X78(B
        !           328:
        !           329: $B:4F#$i(B \cite{SATO} $B$K$h$k(B DCGB $B$b(B, $BF1MM$KBe?tBN>e$N%0%l%V%J!<(B
        !           330: $B4pDl$rM?$($k(B. $B$3$NJ}K!$H$NHf3S$O6=L#$"$kOCBj$G$"$m$&(B.
        !           331:
        !           332: \item change of ordering, RUR
        !           333:
        !           334: $B<B:]$N5a2r$KI,MW$K$J$k(B, FGLM $B$d(B RUR $B$N7W;;$rBe?tBN>e$K(B
        !           335: $B3HD%$9$k$3$H$OI,MW$G$"$m$&(B. $B$3$N>l9g$K$b(B, $B@~7AJ}Dx<05a2r$r(B
        !           336: $BBe?tBN>e$G9T$&$+(B, $BM-M}?tBN>e$G9T$&$+$NA*Br$,@8$:$k(B. $B$3$l$i$N(B
        !           337: $BHf3S$b:#8e$N2]Bj$G$"$k(B.
        !           338:
        !           339: \item $BBe?tBN1i;;$N<BAu$N8zN(2=(B
        !           340:
        !           341: $B:#2s$N<BAu$G$O(B, $BBe?tBN$NI=8=$H$7$F(B, Asir $B5lMh$NJ,;6B?9`<07?$G$"$k(B
        !           342: {\tt DP} $B$rMQ$$$?(B. $B$3$l$O(B, {\tt nd} $B7O4X?t$,8=>u$G$O:FF~IT2D$G$"$k(B
        !           343: $B$H$$$&$N$,<g$JM}M3$G$"$C$?(B. {\tt nd} $B$N3+H/F05!$,(B {\tt DP} $B7?$N(B
        !           344: $B7W;;8zN($X$NITK~$G$"$C$?$3$H$r9M$($l$P(B, $B$3$NItJ,$N2~NI$O0UL#$,$"$k(B.
        !           345: $BFC$K(B, triangular form $B$K$h$k4JLs2=$KFC2=$7$?%G!<%?7?$*$h$S4X?t(B
        !           346: $B$r=q$/$3$H$K$h$j(B, $B$h$j0lAX$N8zN(2=$,C#@.$G$-$k$G$"$m$&(B.
        !           347: \end{itemize}
        !           348:
        !           349:
        !           350:
        !           351: \begin{thebibliography}{99}
        !           352: \bibitem{HOEI02}
        !           353: M.v. Hoeij, M. Monagan, A Modular GCD algorithm over Number Fields presented with Multiple Extensions. Proc. ISSAC'02 (2002), 109-116.
        !           354:
        !           355: \bibitem{NORO96}
        !           356: $BLnO$(B, $BC`<!Be?t3HBgBN>e$G$N(B 1 $BJQ?tB?9`<0$N(B GCD $B$K$D$$$F(B. $B?tM}8&9V5fO?(B 920 (1996), 1-8.
        !           357:
        !           358: \bibitem{SATO}
        !           359: Y. Sato, A. Suzuki,  Discrete Comprehensive Gr\"obner Bases.
        !           360: Proc. ISSAC'01 (2001), 292-296.
        !           361:
        !           362: \bibitem{SYMBDATA}
        !           363: SymbolicData. {\tt http://www.SymbolicData.org}.
        !           364: \end{thebibliography}
        !           365: \end{document}