Return to rims2004-noro.tex CVS log

Up to [local] / OpenXM / doc / Papers

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

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,
1.2     ! noro       63: $h_0 \equiv h \bmod I$, $\deg_{x_i}(h_0) < d_i$ $B$J$k(B $h_0$ $B$O(B
1.1       noro       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}$)
1.2     ! noro      165: $B$H$9$k(B. $B$3$N$H$-(B, $B_F = B \cup \{m_1,\ldots,m_l\}$ $B$N@8@.$9$k%$%G%"%k(B
        !           166: $B$N(B $<_F$ $B$K4X$9$k(B
1.1       noro      167: $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
                    168: $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
                    169: $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.
                    170: \end{Th}
                    171: $G_F$ $B$r7W;;$9$k>l9g(B, $B<B:]$N%"%k%4%j%:%`$N<B9T$r4Q;!$9$k$H(B,
                    172: $B@8@.$5$l$kCf4V4pDl$NF,9`$N(B $t$ $BJQ?t$,$@$s$@$s8:$C$F9T$-?k$K>CLG(B
                    173: $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
                    174: 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
                    175: 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
                    176: strategy $B$J$I(B, $B$J$s$i$+$N4p=`$K$h$j5!3#E*$K7h$a$i$l$k$,(B,
                    177: S-$BB?9`<0$,A}$($k$H(B, $BITE,@Z$J=g=x$G=hM}$5$l$k2DG=@-$bA}$((B,
                    178: $BITI,MW$J78?tKDD%$r0z$-5/$3$92DG=@-$,$"$k(B. $B$=$3$G(B, $BA0@a$N5U85(B
                    179: $B7W;;$rMQ$$$F(B, Buchberger $B%"%k%4%j%:%`$K$*$1$k(B, 0 $B$K4JLs$5$l$J$$(B
                    180: $B85$N4pDl$N=hM}$r<!$N$h$&$KJQ99$9$k(B:
                    181: \begin{itemize}
                    182: \item $BDL>o$N=hM}(B
                    183:
                    184: $S(f,g) \tmred{G} h \neq 0$ $B$J$i$P(B, $G \leftarrow G \cup \{h\}$
                    185:
                    186: \item $BJQ998e$N=hM}(B
                    187:
                    188: $S(f,g) \tmred{G} h(x,t) \neq 0$ $B$J$i$P(B,
                    189: $h(x,\alpha)$ $B$r(B monic $B2=$7$?$b$N(B
                    190: $\tilde{h}(x,\alpha)$ $B$r:n$j(B,
                    191: $G \leftarrow G \cup \{\tilde{h}(x,t)\}$
                    192: \end{itemize}
                    193: $B$3$N$h$&$JJQ99$r9T$C$F$b(B $G_F$ $B$,7W;;$G$-$k$3$H$O$"$-$i$+$G(B
                    194: $B$"$m$&(B.
                    195:
                    196: \subsection{trace $B%"%k%4%j%:%`(B}
                    197:
                    198: 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
                    199: $BA4$G$"$m$&(B. $\bmod p$ $B$G$N(Btrace $B%"%k%4%j%:%`$N@5Ev@-$O(B, $\Q$ $B>e$N4JLs(B
                    200: $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
                    201: $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
                    202: $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
                    203: $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,
                    204: $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
                    205: $B<+?H$OF~NO%$%G%"%k$N85$G$"$k$3$H$O3N$+$G(B, $B$3$N85$,$"$i$+$8$a%$%G%"%k$N(B
                    206: $B@8@.85$N0l$D$G$"$C$?$H9M$($l$P$h$$(B.
                    207:
                    208: trace $B%"%k%4%j%:%`$N<B8=$K$D$$$F$O$$$/$D$+$N%P%j%(!<%7%g%s$,9M$($i$l$k(B.
                    209: $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,
                    210: $GF(p)[t]/\overline{I}$ $B$,$$$/$D$+$NM-8BBN$ND>OB$KJ,2r$9$k(B.
                    211: $I_p$ $B$r(B, $I$ $B$N78?t$r(B $\Q_{<p>}=\{a/b\,|\, a, b \in Z, p \not{|} b\}$
                    212: $B$K@)8B$7$?$b$N$H$7(B, $\phi$ $B$r(B $I_p$ $B$+$i$"$kD>OB@.J,$X$N(B
                    213: $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,
                    214: trace $B$N7W;;$O(B, $BM-8BBN>e$G$NF~NOB?9`<0=89g$N%0%l%V%J!<4pDl7W;;$H(B
                    215: $B$J$k$?$a(B, $B7W;;$N<j4V$r8:$i$;$k2DG=@-$,$"$k(B.
                    216:
                    217:
                    218: \section{Risa/Asir $B>e$G$N<BAu(B}
                    219:
                    220: \subsection{$BC`<!Be?t3HBg(B}
                    221:
                    222: Risa/Asir $B$K$O(B, $BC`<!Be?t3HBg$N85$NI=8=$H$7$F(B,
                    223: $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
                    224: $B$*$h$S:G>.B?9`<07W;;$K4{$KMQ$$$i$l$F$$$k$,(B, $B4JLs7W;;(B, $B5U857W;;$r4^$`(B
                    225: $B$[$H$s$I$N4X?t$O(B, {\tt sp} $BCf$K%f!<%64X?t$H$7$F(B
                    226: $B=q$+$l$F$$$F9b8zN($OK>$a$J$$(B. $BFC$K(B, $B4{$K=R$Y$?$h$&$J(B, $BC19`4JLs(B
                    227: $B$K$h$k4JLs$r9T$&$N$K$OE,$7$F$$$J$$$?$a(B, $BJ,;6I=8=B?9`<0$r%\%G%#It(B
                    228: $B$K$b$DC`<!Be?t3HBg$NI=8=$r?7$?$KDj5A$7$?(B.
                    229: \begin{verbatim}
                    230: typedef struct oDAlg {
                    231:         short id;
                    232:         char nid;
                    233:         char pad;
                    234:         struct oDP *nm;
                    235:         struct oQ *dn;
                    236: } *DAlg;
                    237: \end{verbatim}
                    238: {\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
                    239: $BM-M}?t$G$"$k(B {\tt dn} $B$r$b$D(B.
                    240: $BBe?tE*?t$H$7$F$O(B {\tt nm/dn} $B$rI=$9$,(B, {\tt nm} $B$O@0?t78?t$N(B
                    241: $BJ,;6I=8=B?9`<0(B, {\tt dn} $B$O@0?t$K8BDj$9$k(B. $B$9$J$o$A(B,
                    242: $B%\%G%#It$NM-M}?t78?t$rDLJ,$7$FI=<($9$k$HLsB+$9$k$N$G$"$k(B.
                    243: $B$^$?(B, $B78?tBN$G$"$kC`<!3HBgBN$r(B, $B$=$l$r@8@.$9$kBe?tE*?t$N%j%9%H(B
                    244: $B$G;XDj$9$k4X?t(B {\tt set\_field()} $B$rMQ0U$7$?(B. $B$3$N8F$S=P$7(B
                    245: $B$K$h$j(B, $B4JLs7W;;(B, $B5U857W;;$KI,MW$J(B, $B:G>.B?9`<0%j%9%H$d(B
                    246: $BC19`<04pDl$,7W;;$5$l(B, $BFbItE*$K78?tBN>pJs$H$7$F%;%C%H(B
                    247: $B$5$l$k(B.
                    248:
                    249: {\tt DAlg} $B7?$N%*%V%8%'%/%H$O(B, {\tt Alg} $B7?$+$i$NJQ494X?t(B
                    250: {\tt algtodalg()} $B$K$h$j@8@.$5$l$k(B. $B$=$N5UJQ49$O(B {\tt dalgtoalg()}
                    251: $B$G$"$k(B.
                    252:
                    253: \subsection{$B%0%l%V%J!<4pDl7W;;(B}
                    254:
                    255: $B8=:_$N;n83E*<BAu$O(B, {\tt nd\_gr} $B$*$h$S(B {\tt nd\_gr\_trace} $B$r(B, $BF~NOB?(B
                    256: $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)
1.2     ! noro      257: $B$r2C$($k(B, $B$H$$$&7A$G9T$C$F$$$k(B. $BF~NO$O(B, {\tt Alg} $B7?$r78?t$K4^$`(B
        !           258: $BB?9`<0=89g$G$h$$(B. $BNc$($P(B $\langle \sqrt{2}x^2+(\sqrt{2}+\sqrt{3})xy+\sqrt{3}y^2-\sqrt{3},(\sqrt{2}-2\sqrt{3})x^2+2\sqrt{3}xy+2\sqrt{2}x^2+\sqrt{2}+\sqrt{3}\rangle$ $B$N<-=q<0=g=x%0%l%V%J!<4pDl$N7W;;$O<!$N$h$&$K$9$l$P$h$$(B.
        !           259: \begin{verbatim}
        !           260: [0] S2=newalg(x^2-2);
        !           261: (#0)
        !           262: [1] S3=newalg(x^2-3);
        !           263: (#1)
        !           264: [2] F1=S2*x^2+(S2+S3)*x*y+S3*y^2-S3$
        !           265: F2=(S2-2*S3)*x^2+2*S3*x*y+2*S2*x^2+S2+S3]$
        !           266: [3] nd_gr_trace([F1,F2],[x,y],1,1,2);
        !           267: [90*y^4+(-21*#0*#1-246)*y^2+(16*#0*#1+144),
        !           268: 20*x+(15*#0*#1-60)*y^3+(-7*#0*#1+83)*y]
        !           269: \end{verbatim}
        !           270: $BFbItE*$K$O(B, $BBe?tE*?t$O(B, $B85$NB?9`<0JQ?t$HF1Ey$K07$o$l(B, $B@55,2=7W;;$OM-M}?tBN(B
        !           271: $B>e$G9T$o$l$k(B. monic $B2=$N:]$K$N$_(B, $BK\Mh$N78?t$,Be?tE*?t(B ({\tt DAlg $B7?(B}) $B$H(B
        !           272: $B$7$F<h$j=P$5$l(B, $B5U857W;;$J$I$,9T$o$l$k(B.
        !           273: $B$3$l$KBP$7(B, $BBe?tE*?t$r40A4$K78?t$K<h$j(B
1.1       noro      274: $B9~$s$G(B, $B78?t$K4X$7$F4{$K=R$Y$?$h$&$J4JLs2=$*$h$S5U857W;;$r9T$&$H$$$&J}(B
                    275: $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
                    276: $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
                    277: $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
                    278: $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
                    279: $B<+A3$J<BAu$H$b8@$($k$,(B, content $B=|5n$KAjEv$9$kJ}K!$r?7$?$K9M0F$9$kI,MW(B
                    280: $B$,$"$j(B, $B:#8e$N2]Bj$H$7$?(B.
                    281:
                    282: \section{$B%?%$%_%s%0%G!<%?(B}
                    283:
                    284: $B0J2<(B, $BFC$KCG$i$J$$8B$j(B, $B9`=g=x$O(B DRL $B$H$9$k(B.
                    285: \begin{Exp}\rm
                    286: \label{exp:c7}
                    287: \begin{eqnarray*}
                    288: Cyc&=&\{f_1,f_2,f_3,f_4,f_5,f_6,f_7\}\\
                    289: f_1&=&\omega c_5c_4c_3c_2c_1c_0-1\\
                    290: 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\\
                    291: 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\\
                    292: 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\\
                    293: 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\\
                    294: f_6&=&(c_1+\omega )c_0+c_2c_1+c_3c_2+c_4c_3+c_5c_4+\omega c_5\\
                    295: f_7&=&c_0+c_1+c_2+c_3+c_4+c_5+\omega
                    296: \end{eqnarray*}
                    297:
                    298: $Cyc$ $B$O(B, cyclic-7 $B$K$*$$$F(B, $c_6$ $B$r(B 1 $B$N86;O(B 7 $B>h:,(B
                    299: $\omega$ $B$KCV$-49$($?$b$N$G$"$k(B. $Cyc$ $B$N(B $\Q(\omega)$ $B>e$G$N(B
                    300: $B%0%l%V%J!<4pDl7W;;$O(B, $B@F<!2=(B trace $B%"%k%4%j%:%`$K$h$j(B 22 $BIC(B
                    301: $B$G7W;;$G$-$k(B. $B$3$N$&$A(B, monic $B2=$N7W;;;~4V$O(B 2.2 $BIC(B, $B$=$N$&$A(B
                    302: $B5U857W;;$O(B 0.2$BIC(B $B$G$"$k(B.
                    303:
                    304: $\omega$ $B$N:G>.B?9`<0$rE:2C$7$F(B $\Q$ $B>e$G(B
                    305: $B7W;;$9$k>l9g(B 220 $BIC$+$+$k(B.
                    306: \end{Exp}
                    307:
                    308: \begin{Exp}\rm
                    309: \label{exp:cap}
                    310: \begin{eqnarray*}
                    311: Cap&=&\{f_1,f_2,f_3,f_4\}\\
                    312: f_1&=&(2ty-2)x-(\alpha+\beta)zy^2-z\\
                    313: 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\\
                    314: f_3&=&(t^2-1)x+(\beta\alpha^4+\beta^3\alpha^3)tzy-2z\\
                    315: 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\\
                    316: m_1&=&u^7-7u+3\\
                    317: m_2&=&u^6+\alpha u^5+\alpha^2u^4+\alpha^3u^3+\alpha^4u^2+\alpha^5u+\alpha^6-7
                    318: \end{eqnarray*}
                    319: $Cap$ $B$O(B $Caprasse$ \cite{SYMBDATA}
                    320: $B$N78?t$r%i%s%@%`$KBe?tE*?t$KCV$-49$($?(B
                    321: $B$b$N$G$"$k(B. $\alpha$, $\beta$ $B$O(B $t^7-7t+3$ $B$N(B 2 $B:,$G(B,
                    322: $\alpha$ $B$N(B $\Q$$B>e$N:G>.B?9`<0$,(B $m_1(u)$, $\beta$ $B$N(B $\Q(\alpha)$
                    323: $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
                    324: $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),
                    325: $\Q$ $B>e$G$O@F<!2=$7$F$b(B, 1 $B;~4VBT$C$F$b=*N;$7$J$$(B.
                    326: \end{Exp}
                    327:
                    328: \begin{Exp} \rm
                    329: $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
                    330: $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
                    331: 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,
                    332: 0.8 $BIC$G=*N;$9$k(B. $B5U857W;;(B 1 $B2sJ,$,7W;;;~4V$NBgItJ,$r@j$a$k(B. $B0lJ}(B,
                    333: $B$3$l$r(B $\Q$ $B>e$G9T$&$H(B, 60 $BIC$+$+$k(B.
                    334: \end{Exp}
                    335:
                    336: \section{$B$*$o$j$K(B}
                    337: $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
                    338: $B<0$rE:2C$7$FM-M}?tBN>e$G7W;;$9$k$h$j9bB.$K7W;;$G$-$k>l9g$,$"$k$3$H$,<((B
                    339: $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
                    340: $BE*$J2~NI(B, $B?7%"%k%4%j%:%`$bI,MW$G$"$m$&(B.
                    341:
                    342: $B:#8e$NM=Dj$H$7$F0J2<$r5s$2$F$*$/(B.
                    343: \begin{itemize}
                    344: \item DCGB $B$H$N4X78(B
                    345:
                    346: $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
                    347: $B4pDl$rM?$($k(B. $B$3$NJ}K!$H$NHf3S$O6=L#$"$kOCBj$G$"$m$&(B.
                    348:
                    349: \item change of ordering, RUR
                    350:
                    351: $B<B:]$N5a2r$KI,MW$K$J$k(B, FGLM $B$d(B RUR $B$N7W;;$rBe?tBN>e$K(B
                    352: $B3HD%$9$k$3$H$OI,MW$G$"$m$&(B. $B$3$N>l9g$K$b(B, $B@~7AJ}Dx<05a2r$r(B
                    353: $BBe?tBN>e$G9T$&$+(B, $BM-M}?tBN>e$G9T$&$+$NA*Br$,@8$:$k(B. $B$3$l$i$N(B
                    354: $BHf3S$b:#8e$N2]Bj$G$"$k(B.
                    355:
                    356: \item $BBe?tBN1i;;$N<BAu$N8zN(2=(B
                    357:
                    358: $B:#2s$N<BAu$G$O(B, $BBe?tBN$NI=8=$H$7$F(B, Asir $B5lMh$NJ,;6B?9`<07?$G$"$k(B
                    359: {\tt DP} $B$rMQ$$$?(B. $B$3$l$O(B, {\tt nd} $B7O4X?t$,8=>u$G$O:FF~IT2D$G$"$k(B
                    360: $B$H$$$&$N$,<g$JM}M3$G$"$C$?(B. {\tt nd} $B$N3+H/F05!$,(B {\tt DP} $B7?$N(B
                    361: $B7W;;8zN($X$NITK~$G$"$C$?$3$H$r9M$($l$P(B, $B$3$NItJ,$N2~NI$O0UL#$,$"$k(B.
                    362: $BFC$K(B, triangular form $B$K$h$k4JLs2=$KFC2=$7$?%G!<%?7?$*$h$S4X?t(B
                    363: $B$r=q$/$3$H$K$h$j(B, $B$h$j0lAX$N8zN(2=$,C#@.$G$-$k$G$"$m$&(B.
                    364: \end{itemize}
                    365:
                    366:
                    367:
                    368: \begin{thebibliography}{99}
                    369: \bibitem{HOEI02}
                    370: M.v. Hoeij, M. Monagan, A Modular GCD algorithm over Number Fields presented with Multiple Extensions. Proc. ISSAC'02 (2002), 109-116.
                    371:
                    372: \bibitem{NORO96}
                    373: $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.
                    374:
                    375: \bibitem{SATO}
                    376: Y. Sato, A. Suzuki,  Discrete Comprehensive Gr\"obner Bases.
                    377: Proc. ISSAC'01 (2001), 292-296.
                    378:
                    379: \bibitem{SYMBDATA}
                    380: SymbolicData. {\tt http://www.SymbolicData.org}.
                    381: \end{thebibliography}
                    382: \end{document}