Return to effgr.tex CVS log

Up to [local] / OpenXM / doc / compalg

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

1.1     ! noro        1: \chapter{$B%0%l%V%J4pDl7W;;$N8zN(2=(B}
        !             2:
        !             3: $BBh(B \ref{chapgr} $B>O$G%0%l%V%J4pDl$r7W;;$9$k%"%k%4%j%:%`$G$"$k(B
        !             4: Buchberger $B%"%k%4%j%:%`$N:G$b86;OE*$J7A$r<($7$?(B. $B$7$+$7(B, $B$=$3$G=R$Y$?(B
        !             5: $B$h$&$K(B, $B%"%k%4%j%:%`(B \ref{buch}$B$r$=$N$^$^<B9T$9$k$3$H$O(B, $B8zN($NE@$+$i(B
        !             6: $B$_$FLdBj$,$"$k(B. $B$3$l$O(B, $B%"%k%4%j%:%`$N?J9T$K$D$l$F(B, $B@55,2=$7$F(B 0 $B$K$J(B
        !             7: $B$kBP$,A}2C$7$F$$$/$?$a$G$"$k(B. $B$^$?(B, $BBP$NA*$SJ}$K$bG$0U@-$,$"$k(B. $B$I$N$h(B
        !             8: $B$&$JA*$SJ}$rMQ$$$F$b(B, $B:G=*7k2L$G$"$k%0%l%V%J4pDl$N0l0U@-$OJ]>Z$5$l$F$$(B
        !             9: $B$k$,(B, $BA*$SJ}$K$h$j8zN($KBg$-$J:9$,$G$k$3$H$,B?$/$N<B83$K$h$j3N$+$a$i$l(B
        !            10: $B$F$$$k(B.  $BK\>O$G$O(B, $B%0%l%V%J4pDl$N7W;;$r8zN(2=$9$k$5$^$6$^$JJ}K!$r>R2p(B
        !            11: $B$9$k(B.
        !            12:
        !            13: \begin{nt}
        !            14: $B0J2<$G(B, $B<!$N$h$&$J5-K!$rMQ$$$k(B.
        !            15:
        !            16: \noi
        !            17: $p$ : $BAG?t(B.\\
        !            18: $GF(p)$ : $p$ $B85BN(B.\\
        !            19: $\Z_{(p)}$ = $\{a/b \mid a \in \Z; b \in \Z \setminus p\Z\} \subset \Q$ :
        !            20: $\Z$\, $B$N(B $p\Z$ $B$K$*$1$k6I=j2=(B.\\
        !            21: $X = \{x_1,\cdots,x_n\}$ : $BITDj85(B.\\
        !            22: $\phi_p$ : $\Z_{(p)}[X]$ $B$+$i(B $GF(p)[X]$ $B$X$NI8=`E*<M1F(B.
        !            23: $\phi_p(a/b) = \phi_p(a)/\phi_p(b)$. ($a \in \Z$, $b\in \Z\setminus p\Z$.)\\
        !            24: $<$, $<_0$, $<_1$, $<_i$ : term order.\\
        !            25: $HT_<(f)$ : $f$ $B$N(B $<$ $B$K4X$9$kF,9`(B.\\
        !            26: $HC_<(f)$ : $f$ $B$N(B $<$ $B$K4X$9$kF,78?t(B.\\
        !            27: $T(f)$ : $f$ $B$K8=$l$k9`A4BN$N=89g(B.\\
        !            28: $GB_<(S)$ : $S$ $B$N(B $<$ $B$K4X$9$kHoLs%0%l%V%J4pDl(B.\\
        !            29: $f_1,\cdots,f_m$ : $\Z[X]$ $B$N85(B.\\
        !            30: $NF_<(f,G)$ : $f$ $B$N(B $G$ $B$K4X$9$k@55,7A$N0l$D(B.\\
        !            31: $Init_<(I)$ : \{$HT_<(f)\mid f\in I$\} $B$G@8@.$5$l$k%$%G%"%k(B.\\
        !            32: $Useless\_Pairs(D)$ : $BITI,MWBP$N8!=P(B.\\
        !            33: $Select\_Pair(D)$ : $BBP$NA*Br(B\\
        !            34: $Sp(C)$ : $BB?9`<0BP$N(B S-$BB?9`<0$N7W;;(B
        !            35: \end{nt}
        !            36:
        !            37: \section{$BITI,MWBP$N8!=P(B}
        !            38: Buchberger $B%"%k%4%j%:%`$K$*$$$F(B, $B@55,2=$K$h$j(B 0 $B$K$J$kBP$rITI,MWBP$H8F(B
        !            39: $B$V(B. $B$3$l$i$O(B, $B$"$kB?9`<0=89g$,(B $B%0%l%V%J4pDl$G$"$k$3$H$N3NG'$N$?$a$K$N$_0UL#$,(B
        !            40: $B$"$j(B, $B$b$77W;;$;$:$K(B 0 $B$K@55,2=$5$l$k$3$H$,$o$+$l$P7W;;8zN($NE@$+$i$_(B
        !            41: $B$F6K$a$F9%ET9g$G$"$k(B. $B$5$i$K(B, $B$3$N(B $B!V(B0 $B$X$N@55,2=!W$O(B, $B%"%k%4%j%:%`$N(B
        !            42: $B$"$k;~E@$K$*$$$F$G$O$J$/(B, $B%0%l%V%J4pDl$N$9$Y$F$N85$,@8@.$5$l$?$N$A(B, 0 $B$K@55,2=(B
        !            43: $B$5$l$k$N$G$"$C$F$b$h$$(B. $B<B:](B, $B$=$N$h$&$J>u67$O(B, $BL?Bj(B \ref{'thomo'} $B$K(B
        !            44: $B$*$$$F8=$l$F$$$k(B. $B$3$NL?Bj$r(B, Taylor $B4pDl$KE,MQ$9$l$P(B, Taylor $B4pDl$N$&(B
        !            45: $B$A(B, $B>iD9$J(B ($B$9$J$o$AB>$N4pDl$K$h$j@8@.$5$l$k(B) $B4pDl$r$H$j=|$$$?;D$j$K$D(B
        !            46: $B$$$F(B 0 $B$K@55,2=$5$l$l$P$h$$$3$H$K$J$k(B. $B$3$3$G<h$j=|$+$l$k4pDl$KBP1~$9(B
        !            47: $B$kB?9`<0BP$N$[$+(B, $BB>$NJ}K!$K$h$j(B 0 $B$K@55,2=$5$l$k$3$H$,$o$+$j(B, $B$H$j=|(B
        !            48: $B$+$l$kBP$b$"$jF@$k(B. $B$3$l$i$K$D$$$F=R$Y$k(B.
        !            49:
        !            50: \subsection{$B>iD9$J4pDl$N=|5n(B}
        !            51: Taylor $B4pDl$+$i>iD9$J4pDl$r<h$j=|$/$?$a$N4pK\E*$JF;6q$O(B, $B4pDl4V$N<!$N(B
        !            52: $B<+L@$J91Ey<0$G$"$k(B.
        !            53: $$ {T_{ijk}\over T_{ij}} S_{ij} + {T_{ijk}\over T_{jk}} S_{jk} +
        !            54: {T_{ijk}\over T_{ki}} S_{ki} = 0 $$
        !            55: $B$3$N91Ey<0$K$*$$$F(B, $B$$$:$l$+$N78?t$,(B 1 $B$G$"$l$P(B, $B$=$N9`$KBP1~$9$k4pDl(B
        !            56: $B$O(B, $BB>$N4pDl$K$h$j@8@.$5$l$k(B. $B$3$l$r7+$jJV$7$F>iD9$J4pDl$r<h$j=|$$$F(B
        !            57: $B9T$/$,(B, $B$3$N:](B, $BAj8_$K0MB8$79g$&4pDl$r8m$C$F<h$j=|$/$3$H$rHr$1$k$?$a(B,
        !            58: $B4pDl4V$KA4=g=x$rF~$l(B, $B$"$k4pDl$,$=$l$h$j=g=x$NDc$$4pDl$K$h$j@8@.$5$l$F(B
        !            59: $B$$$k>l9g$K$N$_(B, $B$=$N4pDl$r<h$j=|$/$3$H$H$9$k(B.
        !            60:
        !            61: \begin{df}
        !            62: $\{S_{ij}\mid i < j\}$ $B$K$*$1$kA4=g=x$r<!$N$h$&$KDj5A$9$k(B.
        !            63:
        !            64: \noi
        !            65: $S_{ij} < S_{kl} \Leftrightarrow$\\
        !            66: $T_{ij} < T_{kl}$ $B$^$?$O(B\\
        !            67: ($T_{ij} = T_{kl}$ $B$+$D(B ($j < l$ $B$^$?$O(B ($j = l$ $B$+$D(B $i < k$)))
        !            68: \end{df}
        !            69:
        !            70: \begin{df}
        !            71: $BBP(B $(i,j)$ $B$K4X$9$k;0$D$N@-<A$r<!$N$h$&$KDj5A$9$k(B.
        !            72:
        !            73: \noi
        !            74: $M(i,j) \Leftrightarrow$ $B$"$k(B $k < j$ $B$,B8:_$7$F(B $T_{kj} \mid T_{ij}$ $B$+$D(B $T_{kj} \neq T_{ij}$
        !            75:
        !            76: \noi
        !            77: $F(i,j) \Leftrightarrow$ $B$"$k(B $k < i$ $B$,B8:_$7$F(B $T_{kj} = T_{ij}$
        !            78:
        !            79: \noi
        !            80: $B(i,j) \Leftrightarrow$ $B$"$k(B $k > j$ $B$,B8:_$7$F(B $T_{k} \mid T_{ij}$ $B$+$D(B $T_{jk} \neq T_{ij}$ $B$+$D(B $T_{ik} \neq T_{ij}$
        !            81: \end{df}
        !            82:
        !            83: \noi
        !            84: $B$3$l$i$O(B, $BA05-91Ey<0$K$*$$$F(B, $S_{ij}$ $B$N78?t$,(B 1 $B$+$D(B $S_{ij}$ $B$N=g=x(B
        !            85: $B$,:GBg$K$J$k>r7o$r>l9gJ,$1$K$h$jI=$7$?$b$N$G$"$k(B. $B$$$:$l$N@-<A$K$*$$$F$b(B
        !            86: $T_{k} | T_{ij}$ $B$h$j(B $S_{ij}$ $B$N78?t$O(B 1. $B$=$l$>$l$K$D$$$F3N$+$a$l$P(B,
        !            87: $B<B:]$K(B $S_{ij}$ $B$,:GBg=g=x$H$J$C$F$$$k$3$H$,$o$+$k(B. $B$h$C$F(B, $B<!$NL?Bj$,(B
        !            88: $B$J$jN)$D(B.
        !            89:
        !            90: \begin{pr}(Gebauer and M\"oller{\rm\cite{GEB}})
        !            91: Taylor $B4pDl$O(B,  $\{S_{ij} \mid \neg M(i,j), \neg F(i,j), \neg B(i,j)\}$
        !            92: $B$G@8@.$5$l$k(B.
        !            93: \end{pr}
        !            94:
        !            95: \begin{re}
        !            96: $B<B:]$N%"%k%4%j%:%`$K$*$$$F$O(B, 0 $B$G$J$$@55,7A$,@8@.$5$l$F(B, $D$ $B$KBP$r(B
        !            97: $BDI2C$9$k:]$K(B, $B>e5-$N@-<A$rK~$?$9BP$r:o=|$7$F$$$/$,(B, $B@-<A(B $M, F, B$ $B$N$&$A(B,
        !            98: $M, F$ $B$O(B, $BB?9`<0=89g(B $G$ $B$KDI2C$9$k85$r4^$`BP$,BP>]$H$J$k$N$KBP$7(B,
        !            99: $B$ $B$O4{$KB8:_$7$F$$$kBP$,BP>]$H$J$k(B. $B$3$N;v<B$O(B, $B@55,2=BP$NA*Br@oN,$H$N(B
        !           100: $B4XO"$G(B, $B%"%k%4%j%:%`$N?J9T$K=EBg$J1F6A$r5Z$\$9>l9g$,$"$k(B.
        !           101: \end{re}
        !           102:
        !           103: \subsection{0 $B$K@55,2=$5$l$kBP$N=|5n(B}
        !           104: $BA0@a$G=R$Y$?$b$N0J30$K(B, $BF,9`$N$_$K$h$j(B, 0 $B$K@55,2=$G$-$k$HH=CG$G$-$kBP(B
        !           105: $B$,$"$jF@$k(B.
        !           106:
        !           107: \begin{pr}(Buchberger)\\
        !           108: $\GCD(HT(f),HT(g))=1$ $B$J$i$P(B  $Sp(f,g) \tmred{\{f,g\}} 0$
        !           109: \end{pr}
        !           110: \proof
        !           111: $f = \sum_i f_i$, $g = \sum_i g_i$ ($f_i, g_i \in M; f_1 > f_2 >
        !           112: \cdots, g_1 > g_2 > \cdots$; $B$"$kE:;z0J9_$O(B 0 $B$H$7$F$*$/(B) $B$H$9$k(B.
        !           113: $B2>Dj$K$h$j(B $\GCD(f_1,g_1) = 1$.  $B$3$N$H$-(B, $Sp(f,g) = g_1\sum_{i\ge
        !           114: 2}f_i - f_1\sum_{j\ge 2}g_j$$B$3$l$+$i(B, $BG$0U$N(B $m \ge 2$ $B$KBP$7$F$"$k(B
        !           115: $k$ $B$,B8:_$7$F(B \\ $Sp(f,g) \tmred{\{f,g\}} R_m =
        !           116: (g_1+\cdots+g_k)(f_{m-k+1}+\cdots)-(f_1+\cdots+f_{m-k})(g_{k+1}+\cdots)$\\
        !           117: $B$H$J$k(B. $B<B:](B, $m = 2$ $B$K$D$$$F$O@5$7$$(B. $m$ $B$^$G@5$7$$$H$9$k(B.
        !           118: $\GCD(f_1,g_1) = 1$ $B$h$j(B, $g_1f_{m-k+1} \neq f_1g_{k+1}$ $B$,8@$($k(B. $B$h$C(B
        !           119: $B$F(B, $B$b$7(B $g_1f_{m-k+1} > f_1g_{k+1}$ $B$J$i$P(B, $HM(R_m) = g_1f_{m-k+1}$.
        !           120: $B$9$k$H(B, \\
        !           121: $R_m \mred{f} R_m - gf_{m-k+1} = (g_1+\cdots+g_k)(f_{m-k+2}+\cdots)-(f_1+\cdots+f_{m-k+1})(g_{k+1}+\cdots)$\\
        !           122: $B$H$J$j(B, $m+1$ $B$N;~$b@5$7$$(B. $g_1f_{m-k+1} < f_1g_{k+1}$ $B$G$bF1MM$G$"$k(B.
        !           123: $B$h$C$F(B, $B$3$NA`:n$r7+$jJV$7$F(B, $B7k6I(B $Sp(f,g) \tmred{\{f,g\}} 0$ $B$rF@$k(B. \qed
        !           124:
        !           125: \noi
        !           126: $B$3$NL?Bj$K$h$j(B, $BA0@a$NA`:n$G;D$C$?4pDl$NCf$+$i$5$i$K(B 0 $B$K@55,2=$5$l$k(B
        !           127: $BBP$r=|5n$9$k$3$H$,$G$-$k(B.
        !           128:
        !           129: \section{$B@55,2=BP$NA*Br@oN,(B}
        !           130: $B%"%k%4%j%:%`(B \ref{buch} $B$N%k!<%W$K$*$1$k(B, $B@55,2=$NBP>]$H$J$kBP$NA*Br$O(B,
        !           131: $B%"%k%4%j%:%`$N@5Ev@-$K$O$J$s$i1F6A$7$J$$$,(B, $B<B:]$N7W;;8zN($KBg$-$/1F6A(B
        !           132: $B$rM?$($k(B. Buchberger $B$K$h$jDs0F$5$l$?@oN,$O<!$N$b$N$G$"$k(B.
        !           133:
        !           134: \begin{df}
        !           135: {\bf normal strategy}\\
        !           136: $T_{ij}$ $B$,:G>.$JBP$+$iA*Br$9$k@oN,$r$$$&(B.
        !           137: \end{df}
        !           138:
        !           139: \noi
        !           140: $B$3$N@oN,$O(B, $B=g=x$NDc$$F,9`$r$b$D4pDl$rAa$a$K@8@.$9$k$H$$$&<BMQE*$J0UL#(B
        !           141: $B$r$b$DB>$K(B, $B$3$N@oN,$K$h$l$P(B S $BB?9`<0$O(B, $B4JLs$N;EJ}$K$h$i$:0l0UE*$J@5(B
        !           142: $B5,7A$H$J$k$3$H$,<($5$l$F$$$k(B. $B$3$N@oN,$O(B, term order $B$K$h$C$F$O6K$a$F(B
        !           143: $B0-$$7k2L$r$b$?$i$9>l9g$,B?$/(B, $BFC$K(B, $B<-=q<0=g=x$N$h$&$K(B, $BA4<!?t$K$h$k(B
        !           144: $BHf3S$r9T$o$J$$=g=x$G?S$@$7$$(B.
        !           145:
        !           146: \begin{df}
        !           147: {\bf $B@F<!2=(B}\\
        !           148: $t$ $B$r@F<!2=JQ?t$H$7(B, $R = k[x_1,\cdots,x_n]$ and $R_h = k[x_1,\cdots,x_n,t]$
        !           149: $B$H$9$k(B. $f \in R$ $B$N@F<!2=$r(B $f^*$, $g\in R_h$ $B$NHs@F<!2=$r(B $g_*$ $B$H=q$/(B.
        !           150: $B0J2<(B, $f$ $B$NA4<!?t$r(B $\tdeg(f)$ $B$H=q$/(B.
        !           151: $$f^* = t^{\tdeg(f)}f(x_1/t,\cdots,x_n/t)$$
        !           152: $$g_* = g|_{t=1}$$$B$G$"$k(B. $BB?9`<0=89g(B $F \subset R$, $G \subset R_h$ $B$K(B
        !           153: $BBP$7$F$b(B, $B3F85$r@F<!2=(B, $BHs@F<!2=$7$?$b$N$r$=$l$>$l(B $F^*$, $F_*$ $B$H=q$/(B.
        !           154:
        !           155: $B$3$N$H$-(B, $R$ $B$N(B order $<$ $B$KBP$7$F(B, $R_h$ $B$N(B order $<_h$ $B$,(B
        !           156: \begin{center}
        !           157: (H) $BG$0U$N@F<!B?9`<0(B $g \in R_h$ $B$KBP$7(B,
        !           158: $HT(g)_* = HT(g_*)$
        !           159: \end{center}
        !           160: $B$rK~$?$9$H$-(B, $<_h$ $B$r(B $<$ $B$N@F<!2=$H8F$V$3$H$K$9$k(B.
        !           161: \end{df}
        !           162:
        !           163: \begin{ex}
        !           164: \label{horder}
        !           165: $X \cup \{t\}$ ($X$ $B$K4X$7$F(B $<$) $B$K$h$k(B block order $B$O(B $<$ $B$N@F<!2=$N0l$D(B
        !           166: $B$G$"$k$,(B, $BDj5A$K$h$j(B,
        !           167:
        !           168: \begin{center}
        !           169: $ut^m <_h vt^n \Leftrightarrow \tdeg(ut^m) < \tdeg(vt^n)$ $B$^$?$O(B $\tdeg(ut^m) = \tdeg(vt^n)$ $B$+$D(B $u < v$
        !           170: \end{center}
        !           171: $B$J$k(B $<_h$ $B$b(B $<$ $B$N@F<!2=$G$"$k(B.
        !           172: \end{ex}
        !           173:
        !           174: \begin{pr}
        !           175: \label{hcomp}
        !           176: $F \subset R$ $B$H$7(B, $<_h$ $B$r(B $<$ $B$N@F<!2=(B order $B$H$9$k(B. $B$3$N$H$-(B,
        !           177: $B$b$7(B $G$ $B$,(B $Id(F^*)$ $B$N@F<!B?9`<0$+$i$J$k%0%l%V%J4pDl$J$i(B,
        !           178: $G_*$ $B$O(B $Id(F)$ $B$N%0%l%V%J4pDl$H$J$k(B.
        !           179: \end{pr}
        !           180: $B@F<!2=$OA*Br@oN,$=$N$b$N$G$O$J$$$,(B, $BF~NO$r@F<!2=$7$?8e(B, $B>e$NNc$G=R$Y$?(B
        !           181: $BA4<!?tHf3SF~$j$N(B $<_h$ $B$N$b$H$G(B normal strategy $B$G7W;;$7$?8eHs@F<!2=$9(B
        !           182: $B$k$H$$$&<j=g$G%0%l%V%J4pDl$r5a$a$k$H(B, $BITI,MWBP$OA}2C$9$k$b$N$N(B, $B7W;;$,(B
        !           183: $B%9%`!<%:$K?J9T$9$k$3$H$,7P83E*$KCN$i$l$F$$$?(B. $B78?tBN$,M-8BBN$N>l9g$K$O(B,
        !           184: $B8e$G=R$Y$k(B, $BITI,MWBP$KBP$9$k@55,7A7W;;$G@8$8$k78?tKDD%$NLdBj$,@8$8$J$$(B
        !           185: $B$?$a(B, $BM-8BBN>e$G$N%0%l%V%J4pDl7W;;$K$O@F<!2=$OM-MQ$G$"$k(B.
        !           186:
        !           187: \begin{df}
        !           188: {\bf sugar strategy}\\
        !           189: $B%0%l%V%J4pDl7W;;$NESCf$K8=$l$kB?9`<0(B $f$ $B$K(B, $B<!$N5,B'$K$h$j$"$k<+A3?t(B
        !           190: $s_f$ (sugar) $B$rBP1~$5$;$k(B.
        !           191:
        !           192: \begin{enumerate}
        !           193: \item $BF~NOB?9`<0(B $f$ $B$KBP$7$F$O(B, $s_f = \tdeg(f)$
        !           194: \item $m$ $B$,(B monomial $B$N;~(B $s_{mf} = \tdeg(m)+s_f$
        !           195: \item $s_{f+g} = \max(s_f,s_g)$
        !           196: \end{enumerate}
        !           197: sugar strategy $B$H$O(B, S $BB?9`<0$N(B sugar $B$N:G$b>.$5$$$b$N$N=89g$+$i(B normal
        !           198: strategy $B$GBP$rA*Br$9$k@oN,$r$$$&(B.
        !           199: \end{df}
        !           200: Giovini $B$i(B{\rm\cite{SUGAR}}$B$K$h$jDs0F$5$l$?$3$N@oN,$O(B, $BF~NOB?9`<0=89g(B
        !           201: $B$r@F<!2=$7$F$N%0%l%V%J4pDl7W;;$r(B{\bf $B2>A[E*(B}$B$K9T$J$&$b$N$G(B, sugar $B$O(B
        !           202: $B@F<!2=8e$N<!?t$KBP1~$7$F$$$k(B.
        !           203:
        !           204: \section{Trace lifting}
        !           205:
        !           206: sugar strategy $B$K$h$j(B, $B>/$J$/$H$b78?tBN$,M-8BBN$N>l9g$K$O(B, $B==J,$J8zN((B
        !           207: $B$,C#@.$G$-$k$h$&$K$J$C$?(B.  $B$7$+$7(B, $B78?tBN$,M-M}?t$N>l9g(B, $BA0$K=R$Y$?8!(B
        !           208: $B=P4p=`$K$+$+$i$J$$ITI,MWBP$N(B S $BB?9`<0$N@55,2=7W;;$K$+$+$k%3%9%H$,Bg$-(B
        !           209: $B$$>l9g$,$7$P$7$P$"$k(B.
        !           210: $B$=$N$?$a(B, $B<!$N$h$&$J%"%k%4%j%:%`(B ({\bf trace lifting})
        !           211: $B$,Ds0F$5$l$?(B \cite{TRAV}.
        !           212:
        !           213: \begin{al}
        !           214: \label{tl}
        !           215: \begin{tabbing}
        !           216: \\
        !           217: trace\_lifting$(F,<)$\\
        !           218: Input : $F \subset \Z[X]$; term order $<$\\
        !           219: Output : $F$ $B$N(B $<$ $B$K4X$9$k%0%l%V%J4pDl(B\\
        !           220:
        !           221: do \= \{\\
        !           222: \> $p \leftarrow$ $BL$;HMQ$NAG?t(B\\
        !           223: \> $G \leftarrow tl\_guess(F,<,p)$\\
        !           224: \> if \= $G \neq$ {\bf nil} $B$+$D(B tl\_check$(F,G,<) =1$ \\
        !           225: \> then return $G$\\
        !           226: \}
        !           227: \end{tabbing}
        !           228: \end{al}
        !           229:
        !           230: \begin{al}
        !           231: \label{tlguess}
        !           232: \begin{tabbing}
        !           233: \\
        !           234: tl\_guess$(F,<,p)$\\
        !           235: Input : $F \subset \Z[X]$; term order $<$; $BAG?t(B $p$\\
        !           236: Output : $F$ $B$N%0%l%V%J4pDl8uJd$^$?$O(B {\bf nil}\\
        !           237:
        !           238: if \= $B$"$k(B $f \in F$ $B$,B8:_$7$F(B $\phi_p(HC(f))=0$ then return {\bf nil}\\
        !           239: $G \leftarrow F$\\
        !           240: $G_p \leftarrow \{\phi_p(f) \mid f \in G\}$\\
        !           241: $D \leftarrow \{\{f,g\} \mid f,g \in G; f \neq g\}$\\
        !           242: do \= \{\\
        !           243: \> $D \leftarrow D \setminus Useless\_Pairs(D)$\\
        !           244: \> if \= $D = \emptyset$ then return $G$\\
        !           245: \> else \{ \= $C \leftarrow Select\_Pair(D)$\\
        !           246: \>         \> $D \leftarrow D \setminus \{C\}$\\
        !           247: \> \}\\
        !           248: \> $s \leftarrow Sp(C)$\\
        !           249: \> $t_p = NF(\phi_p(s),G_p)$\\
        !           250: \> if \= $t_p \neq 0$ then \{\\
        !           251: \>    \> $t \leftarrow NF(s,G)$\\
        !           252: \>    \> if $\phi_p(HC(f)) = 0$ then return {\bf nil}\\
        !           253: \>    \> $D \leftarrow D \cup \{\{f,t\} \mid f \in G\}$\\
        !           254: \>    \> $G \leftarrow G \cup  \{t\}$\\
        !           255: \>    \> $G_p \leftarrow G_p \cup  \{t_p\}$\\
        !           256: \> \}\\
        !           257: \}
        !           258: \end{tabbing}
        !           259: \end{al}
        !           260:
        !           261: \noi
        !           262: $B%"%k%4%j%:%`(B \ref{tlguess} $B$O(B, $BM-M}?tBN>e$G$N@55,7A7W;;$r9T$J$&A0$KM-8BBN>e(B
        !           263: $B$G@55,7A$r7W;;$7(B, $B$=$l$,(B 0 $B$H$J$k>l9g$K$O(B, $BM-M}?tBN>e$N@55,7A$b(B 0 $B$G$"(B
        !           264: $B$k$H2>Dj$7$F$=$N7W;;$r>JN,$9$k(B. $B$3$N$h$&$JA`:n$r9T$J$C$F$b(B, $B@8@.$5$l$k(B
        !           265: 0$B$G$J$$B?9`<0$K$D$$$F(B, $B$=$NF,9`$O(B, $BDL>o$N(B Buchberger $B%"%k%4%j%:%`$HF1(B
        !           266: $BMM$N@-<A$r;}$D$?$a%"%k%4%j%:%`$ODd;_$9$k(B. $B$7$+$7(B, $p$ $B$NA*$SJ}$K$h$C$F(B
        !           267: $B$O%0%l%V%J4pDl$r=PNO$7$J$$>l9g$,$"$k$?$a(B, $B<!$N$h$&$J%F%9%H$,I,MW$H$J$k(B.
        !           268: \begin{al}
        !           269: \label{tlcheck}
        !           270: \begin{tabbing}
        !           271: \\
        !           272: tl\_check$(F,G,<)$\\
        !           273: Input : $BB?9`<0=89g(B $F, G \subset \Z[X] \st G \subset Id(F)$; order $<$\\
        !           274: Output :\= $B$b$7(B $G$ $B$,(B $<$ $B$K4X$9$k(B $F$ $B$N%0%l%V%J4pDl$J$i(B 1\\
        !           275:         \> $B$=$&$G$J$1$l$P(B 0\\
        !           276: if \= $G$ $B$,(B $<$ $B$K4X$7$F%0%l%V%J4pDl$G$J$$(B then return 0\\
        !           277: if $B$9$Y$F$N(B $f \in F$ $B$KBP$7(B $NF_<(f,G) = 0$ then return 1 else return 0
        !           278: \end{tabbing}
        !           279: \end{al}
        !           280: $B<B:](B, $B%"%k%4%j%:%`(B \ref{tlguess} $B$N=PNO(B $G$ $B$KBP$7(B, $G \subset Id(F)$
        !           281: $B$O9=@.K!$h$j>o$K@.$jN)$D$+$i(B, \ref{tlcheck} $B$,(B 1 $B$rJV$;$P(B $Id(G) =
        !           282: Id(F)$ $B$G(B, $G$ $B$O(B $Id(F)$ $B$N%0%l%V%J4pDl$H$J$k(B. $B$3$N%F%9%H$rAH$_9g$o$;(B
        !           283: $B$?$b$N$,(B, $B%"%k%4%j%:%`(B \ref{tl} $B$G$"$k(B. $B$3$N%F%9%H$rDL2a$G$-$k$h$&$J(B
        !           284: $p$ $B$H$7$F$O(B, $BDL>o$N(B Buchberger $B%"%k%4%j%:%`$r<B9T$7$?>l9g$K8=$l$k$9$Y(B
        !           285: $B$F$NB?9`<0$NF,78?t$r3d$i$J$$$h$&$JAG?t$r$H$l$P$h$$(B. $B$b$A$m$s$3$N$h$&$J(B
        !           286: $BAG?t$O$"$i$+$8$a7hDj$9$k$3$H$O$G$-$J$$$,(B, $BITET9g$JAG?t$OM-8B8D$G$"$j(B,
        !           287: $B%"%k%4%j%:%`A4BN$H$7$F$NDd;_@-$bJ]>Z$5$l$k(B. $B$3$N%"%k%4%j%:%`$K$*$$$F$O(B,
        !           288: \begin{center}
        !           289: $BITI,MWBP$KBP$9$k(B S $BB?9`<0$N7W;;%3%9%H(B\\
        !           290: $\Downarrow$\\
        !           291: $BM-8BBN>e$G$N%0%l%V%J4pDl7W;;(B + $B%0%l%V%J4pDl%F%9%H(B + $BF~NOB?9`<0$KBP$9$k(B
        !           292: $B%a%s%P%7%C%W%F%9%H(B
        !           293: \end{center}
        !           294: $B$H$$$&CV$-49$($,9T$J$o$l$F$$$k(B. $B$h$C$F(B, $B$3$NCV$-49$($,8zN($r8~>e$5$;$k(B
        !           295: $B$?$a$K$O(B, $B8e<T$,A0<T$h$j9bB.$K<B9T$G$-$J$1$l$P$J$i$J$$(B. $B$3$NHf3S$OF~NO(B
        !           296: $BB?9`<0=89g(B $F$ $B$N@-<A(B, $B$"$k$$$OMQ$$$k(B order $B$N@-<A$K$h$C$F0[$J$k$,(B, $B0l(B
        !           297: $BHLE*$K$O<!$N$h$&$J$3$H$,8@$($k(B.
        !           298: \begin{itemize}
        !           299: \item $V(Id(F))$ $B$NM><!85$,Bg$-$$>l9g(B
        !           300:
        !           301: $B%0%l%V%J4pDl7W;;$K8=$l$k78?t$,(B
        !           302: $BD9Bg$K$J$k798~$,Bg$-$/(B, $BFC$K(B, $V(Id(F))$ $B$,M-8B=89g$K$J$k>l9g$K(B, $F$ $B$N(B
        !           303: $B%0%l%V%J4pDl$r<-=q<0=g=x$G7W;;$9$k>l9g$K?S$@$7$$(B. $B$=$N$h$&$J>l9g$G$b(B,
        !           304: $B:G=*E*$J%0%l%V%J4pDl$N78?t(B, $B85$N8D?t$O>.$5$$>l9g$,B?$/(B, 2 $B$D$N%F%9%H(B
        !           305: $B$bHf3SE*MF0W$G$"$k(B.
        !           306:
        !           307: \item $V(Id(F))$ $B$NM><!85$,>.$5$$>l9g(B
        !           308:
        !           309: $BB?9`<0$N9`?t$,A}Bg$9$k>l9g$,B?$/(B, $B$=$N$h$&$J>l9g$K$O(B, $B8e<T$,$=$N$^$^M>(B
        !           310: $BJ,$J%3%9%H$K$D$J$,$k(B.
        !           311: \end{itemize}
        !           312: $B$3$N$h$&$K(B, $B8z2L$,4|BT$G$-$J$$>l9g$b$"$jF@$k$,(B, $B$=$N$h$&$J>l9g$G$b(B
        !           313: $B9b!9(B 2 $BG\DxEY$N;~4V$G7W;;$O=*N;$9$k$?$a(B, $B>o$K(B trace lifting $B$rMQ$$$k(B
        !           314: $B$N$,0BA4$G$"$m$&(B.
        !           315:
        !           316: $B0J>e$N5DO@$K$*$$$F$O(B, $p$ $B$H$7$F$O7W;;5!$,Ds6!$9$k(B 1 $B%o!<%I0JFb$N@0?t(B
        !           317: $B$rMQ$$$k$3$H$r2>Dj$7$F$$$k(B. $B$3$l$O(B, 1 $B%o!<%I0JFb$N@0?t$KBP$9$k2C8:>h=|(B
        !           318: $B$,DL>o$O5!3#L?Na$H$7$FDs6!$5$l$F$$$F(B, $B9bB.$K<B9T$5$l$k$+$i$G$"$k(B. $B$^$?(B,
        !           319: $B78?t$,K!(B $p$ $B$G0lMM$KJ,I[$7$F$$$k$H2>Dj$9$l$P(B, $p$ $B$,Bg$-$$Dx(B, $p$ $B$,(B
        !           320: $BF,78?t$N$I$l$+$r3d$j@Z$k3NN($O>.$5$/$J$k$H4|BT$G$-$k(B. $B$h$C$F(B, $B<B:]$N7W(B
        !           321: $B;;$G$O(B $p$ $B$H$7$F(B 1 $B%o!<%I$NHO0OFb$G$J$k$Y$/Bg$-$$@0?t$rA*$V$N$,$h$$(B.
        !           322:
        !           323: \section{$B@F<!2=(B $B$H(B trace lifting $B$NAH9g$;(B}
        !           324:
        !           325: trace lifting $B$K$h$j(B,  $BITI,MWBP$KBP$9$k(B S $BB?9`<0$N7W;;%3%9%H$r(B, $BM-8BBN(B
        !           326: $B>e$N%0%l%V%J4pDl7W;;$*$h$S(B, $B%0%l%V%J4pDl8uJd@8@.8e$N%0%l%V%J4pDl%F%9%H(B
        !           327: $B$HF~NOB?9`<0$N%a%s%P%7%C%W%F%9%H$KCV$-49$($k$3$H$,$G$-$?(B. $B$7$+$7(B, $B<B:](B
        !           328: $B$K@F<!2=$7$?>l9g$K$O@8$8$J$$$h$&$JCf4V78?tKDD%$,(B, sugar strategy  $B$NE,(B
        !           329: $BMQ$K$h$j@8$8$k>l9g$,$7$P$7$P8+$i$l$k(B. $BK\@a$G$O(B, $B$3$N:$Fq$r9nI~$9$k$?$a(B
        !           330: $B$NJ}K!$K$D$$$F=R$Y$k(B.\\
        !           331: $B$3$N$h$&$J78?tKDD%$r4JC1$JNc$G<($9(B.
        !           332:
        !           333: \begin{ex}
        !           334: $I = Id(-3x_1-3x_2-5,-3x_1x_0^2-8x_0-6,4x_0^2+(-2x_1^3-7)x_0-3x_3x_1^2-2,-x_0^4-x_0^2+3x_1x_0-4x_1)$
        !           335: \end{ex}
        !           336: $I$ $B$N(B $x_0>x_1>x_2>x_3$ $B$J$k<-=q<0=g=x$N$b$H$G$N%0%l%V%J4pDl(B $GB(I)$ $B$O(B, \\
        !           337: $GB(I) = \{f_3(x_3), f_2(x_2,x_3), f_1(x_1,x_3), f_0(x_0,x_3) \}$\\
        !           338: $f_3=286978140000x_3^6-30735638450064x_3^5+139368108773718x_3^4-401122901874078x_3^3\\
        !           339: +3813285736741284x_3^2-17712668879937657x_3+25309718023001309$\\
        !           340: $f_2=-24359129516408255978429894458178435051554483918248x_2\\
        !           341: -9117338725200447183121773483618146011417380000x_3^5\\
        !           342: +945437242481668390348909147393962329546603617488x_3^4\\
        !           343: -1215199713704678902273407299537086048391876350746x_3^3\\
        !           344: +9203891427703221172499174842307408763060278519544x_3^2\\
        !           345: -87128026603776953223695902278763008965980027109460x_3\\
        !           346: +198072128718550346069760390022952204794356946307195$\\
        !           347: $f_1=24359129516408255978429894458178435051554483918248x_1\\
        !           348: -9117338725200447183121773483618146011417380000x_3^5\\
        !           349: +945437242481668390348909147393962329546603617488x_3^4\\
        !           350: -1215199713704678902273407299537086048391876350746x_3^3\\
        !           351: +9203891427703221172499174842307408763060278519544x_3^2\\
        !           352: -87128026603776953223695902278763008965980027109460x_3\\
        !           353: +238670677912564106033810214119916263213614419504275$\\
        !           354: $f_0=-9134673568653095991911210421816913144332931469343x_0\\
        !           355: -334442494143970788481038492015748108482000000x_3^5\\
        !           356: +37671432710327352302696037580172208903376423200x_3^4\\
        !           357: -352356049164307536666247874973386638400872538040x_3^3\\
        !           358: +499969270855985351160909518989653220917608771262x_3^2\\
        !           359: -6841618915067057146509523126510725094238856771432x_3\\
        !           360: +31588951614319486540726259755101613855437086625238$\\
        !           361: $B$3$N7W;;$r(B, $B@F<!2=$r7PM3$7$F9T$C$?>l9g(B, $B8=$l$kCf4V4pDl$N78?t$N%S%C%HD9$NOB(B
        !           362: $B$N:GBgCM$O(B 1489 $B%S%C%H$@$,(B, sugar strategy $B$N$_$rMQ$$$F9T$C$?>l9g$=$N(B
        !           363: $B:GBgCM$O(B 10258121 $B%S%C%H$G$"$C$?(B. $B$3$N$h$&$J>.$5$$LdBj$KBP$7$F$b(B,
        !           364: sugar strategy $B$,$&$^$/F/$+$J$$>l9g$K$OITI,MW$J78?tKDD%$,@8$8$F$7$^$&(B.
        !           365: $B@F<!2=$O@8@.$5$l$k4pDl$N78?tKDD%$,5/$3$i$J$$$h$&$J(B strategy $B$rM?$($k>l(B
        !           366: $B9g$,B?$$$,(B, $BHs@F<!$N>l9g$KHf$Y$FA0$K=R$Y$?ITI,MWBP$N8!=P$K$+$+$i$J$$IT(B
        !           367: $BI,MWBP$rB?$/@8@.$7(B, $BLdBj$,Bg$-$/$J$k$H(B, $B$=$l$i$N(B 0 $B$X$N@55,2=$N%3%9%H(B
        !           368: $B$,Hs>o$KBg$-$/$J$k(B. $B$3$l$i$r9nI~$9$kM-NO$JJ}K!$,(B, $B<!$N%"%k%4%j%:%`$G$"(B
        !           369: $B$k(B.
        !           370: \begin{al}
        !           371: \label{htl}
        !           372: \begin{tabbing}
        !           373: \\
        !           374: homogenized\_trace\_lifting$(F,<)$\\
        !           375: Input : $F \subset \Z[X]$; term order $<$\\
        !           376: Output : $F$ $B$N(B $<$ $B$K4X$9$k%0%l%V%J4pDl(B\\
        !           377:
        !           378: do \= \{\\
        !           379: \> $p \leftarrow$ $BL$;HMQ$NAG?t(B\\
        !           380: \> $G \leftarrow tl\_guess(F^*,<_h,p)$\\
        !           381: \> if \= $G \neq$ nil\\
        !           382: \>    \>$B$+$D(B $G_*$ $B$,(B $<$ $B$K4X$9$k%0%l%V%J4pDl(B\\
        !           383: \>    \>$B$+$D$9$Y$F$N(B $f \in F$ $B$KBP$7(B $NF(f,G_*) = 0$\\
        !           384: \> then return $G_*$\\
        !           385: \}
        !           386: \end{tabbing}
        !           387: \end{al}
        !           388: $<_h$ $B$O(B $BNc(B \ref{horder} $B$G=R$Y$?(B order $B$NA4<!?tIU@F<!2=$rMQ$$$F$$(B
        !           389: $B$k(B. $B$3$NJ}K!$H(B, $BC1$KF~NO$r@F<!2=$7$?$b$N$KBP$7$F(Btrace lifting $B$K$h$j%0(B
        !           390: $B%l%V%J4pDl$r5a$a$F$+$iHs@F<!2=$9$kJ}K!$rHf3S$9$k$H<!$N$h$&$K$J$k(B. $B$$$:(B
        !           391: $B$l$b(B, $B@F<!2=$K$h$jA*Br@oN,$r0BDj$K$7(B, $B$+$D@F<!2=$K$h$jA}2C$7$?ITI,MWBP(B
        !           392: $B$K4X$9$k%3%9%H$O(B trace lifting $B$K$h$j4KOB$5$l$k(B.
        !           393:
        !           394: \begin{itemize}
        !           395: \item $B@F<!2=(B $\Rightarrow$ $B8uJd@8@.(B $\Rightarrow$ $BHs@F<!2=(B $\Rightarrow$ $B%F%9%H(B
        !           396:
        !           397: $BHs@F<!2=$r9T$J$C$?;~E@$G>iD9$J4pDl$r<h$j=|$/$?$a(B, $B%F%9%H$K$+$+$k%3(B
        !           398: $B%9%H$O@F<!2=$r9T$J$o$J$$>l9g$HJQ$o$i$J$$(B.
        !           399:
        !           400: \item $B@F<!2=(B $\Rightarrow$ $B8uJd@8@.(B $\Rightarrow$ $B%F%9%H(B $\Rightarrow$ $BHs@F<!2=(B
        !           401:
        !           402: $B@F<!$J%0%l%V%J4pDl8uJd$N>l9g(B, $B>iD9$J4pDl$,$[$H$s$I$J$/(B, trace lifting $B$K(B
        !           403: $B$h$j%+%C%H$5$l$?BgItJ,$NITI,MWBP$rM-M}?tBN>e$G2~$a$F@55,2=$9$kI,MW$,$"$k(B.
        !           404: \end{itemize}
        !           405: $B$9$J$o$A(B, $BF~NO$,4{$K@F<!$N>l9g$r=|$$$F(B, $BHs@F<!2=8e$K%F%9%H$r9T$J$&J}$,8zN((B
        !           406: $B$,$h$$(B. $B$3$NJ}K!$K$h$j(B, trace lifting $B$N$_$G$O7W;;IT2DG=$@$C$?B?$/$NLdBj(B
        !           407: $B$,7W;;2DG=$K$J$C$?(B.
        !           408:
        !           409: \section{$F_4$ $B%"%k%4%j%:%`(B}
        !           410:
        !           411: $BBe?tJ}Dx<05a2r$K8B$i$:(B, $BBe?t4v2?$K$*$1$kITJQNL$N7W;;$J$I$K$*$$$F$b(B
        !           412: $BG$0UF~NOB?9`<0=89g$+$i$N(B \gr $B4pDl$N7W;;$O(B, $B7W;;NLE*$K$_$F(B dominant
        !           413: step $B$H$J$k$3$H$,B?$$(B. $B$3$N$h$&$J>l9g$N7W;;K!$H$7$F$O(B Buchberger
        !           414: $B%"%k%4%j%:%`$,$[$\M#0l$NJ}K!$G$"$C$?$,(B, $B:G6a(B Faug\`ere $B$K$h$j(B
        !           415: $F_4$ ($B$"$k$$$O(B $F_5$) $B%"%k%4%j%:%`$,Ds0F$5$l(B, $B$=$N9bB.@-$,(B
        !           416: $BCmL\$5$l$F$$$k(B. $BK\@a$G$O(B, $B$3$N%"%k%4%j%:%`$K$D$$$F35@b$9$k(B.
        !           417:
        !           418: \subsection{Symbolic preprocessing}
        !           419:
        !           420: $B%"%k%4%j%:%`(B \ref{buch} $B$r<B9T$9$k>l9g(B, $D$ $B$+$i$I$N85$rA*$s$GMh$k$+(B
        !           421: $B$G(B, $B$=$N8e$N7W;;$N?J9T$NMM;R$,A4$/$3$H$J$k(B, $B$H$$$&$3$H$,(B
        !           422: $B5/$3$k(B. $B$^$?(B, $B:GA1$N85$rA*$s$@$D$b$j$G$b(B, $BFC$KM-M}?tBN>e(B
        !           423: $B$J$I$K$*$$$F(B, $NF(Sp(f,g),G)$ $B$N78?t$,6KC<$KBg$-$/$J$j(B,
        !           424: $B7W;;ITG=$K$J$k$3$H$b5/$3$k(B. $B$=$N$?$a(B, trace lifting,
        !           425: homogenization $B$J$I$N<o!9$N%F%/%K%C%/$N$b$H$G7W;;$,;n$_$i$l$F(B
        !           426: $BMh$?(B.
        !           427: $B$3$3$G(B, Buchberger $B%"%k%4%j%:%`$N3K?4$G$"$k(B $NF(Sp(f,g),G)$
        !           428: $B$K$D$$$F9M;!$9$k(B.
        !           429: $NF(Sp(f,g),G)$ $B$O<!$N$h$&$J<j=g$G7W;;$5$l$k(B.
        !           430:
        !           431: \begin{tabbing}
        !           432: $r \leftarrow af - bg$ ($a, b$ $B$OC19`<0(B) \\
        !           433: while \= ( $r$ $B$N9`(B $t$ $B$r3d$j@Z$k(B $h \in G$ $B$,$"$k(B )\\
        !           434: \> $ r \leftarrow r - ch $\\
        !           435: \> ($r$ $B$K(B $t$ $B$N9`$O$J$$(B)
        !           436: \end{tabbing}
        !           437: $B$3$3$G(B, $r$ $B$r4JLs$9$k$N$KI,MW$J(B $h \in G$ $B$O0l8+<B:]$K4JLs(B
        !           438: $BA`:n$r<B9T$7$J$1$l$PJ,$+$i$J$$$h$&$K8+$($k$,(B, $B>iD9$J85(B
        !           439: ($B$9$J$o$A(B, $B<B:]$K$O4JLs$KMQ$$$i$l$J$$85(B) $B$b5v$;$P(B, $B<!$N$h$&$J(B
        !           440: $BJ}K!$G;vA0$KF@$i$l$k(B.
        !           441:
        !           442: \begin{al} (Symbolic preprocessing)
        !           443: \label{symred}
        !           444: \begin{tabbing}
        !           445: Input : $BB?9`<0(B $f$, $BB?9`<0=89g(B $G$\\
        !           446: Output : $Red=\{ah \mid a :$ $BC19`<0(B, $h \in G \}$ \\
        !           447:
        !           448: $T \leftarrow T(f)$ \\
        !           449: $Red \leftarrow \emptyset$\\
        !           450: while \= $HT(g)|t$ $B$J$k(B $t\in T$, $g \in G$ $B$,B8:_$9$k(B do \{\\
        !           451: \>$Red \leftarrow Red \cup \{t/HT(g)\cdot g\}$\\
        !           452: \>$T \leftarrow (T \setminus \{t\}) \cup T(reductum(t/HT(g)\cdot g)$\\
        !           453: \}\\
        !           454: return $Red$
        !           455: \end{tabbing}
        !           456: \end{al}
        !           457: $B$3$N%"%k%4%j%:%`$GF@$i$l$?(B $Red$ (Reducer) $B$O<!$N@-<A$r$b$D(B:
        !           458:
        !           459: \begin{itemize}
        !           460: \item $\{f\} \cup Red$ $B$N85$N$"$k9`(B $t$ $B$,$"$k(B $g\in G$ $B$KBP$7(B $HT(g)$ $B$G3d$j@Z$l$k$J$i$P(B, $HT(x)=t$ $B$J$k(B $x \in Red$ $B$,$"$k(B.
        !           461: \end{itemize}
        !           462: $B$3$l$h$j(B, $B<!$,8@$($k(B.
        !           463:
        !           464: \begin{itemize}
        !           465: \item $\{f\}$ $B$N(B, $Red$ $B$N85$K$h$k(B $K$ $B78?t$N4JLsA`:n$G$N@55,7A$O(B, $G$ $B$K(B
        !           466: $B4X$9$k@55,7A$H$J$k(B.
        !           467: \end{itemize}
        !           468: $B$3$l$r(B, $B9TNs$N8@MU$G8@$$49$($k$?$a$K<!$N=`Hw$r$9$k(B.
        !           469: $B$^$:(B, $\{f\} \cup Red$ $B$K8=$l$kA4$F$N9`$r(B $T$ $B$H$7(B, $T$ $B$N85$r=g=x$N9b$$(B
        !           470: $B=g$KJB$Y$?$b$N$r(B $t_1 > t_2 > \cdots $ $B$H$9$k(B.
        !           471: $T$ $B$G(B $K$ $B>eD%$i$l$k@~7A6u4V$N85(B $h$ $B$N(B,
        !           472: $(t_1,t_2,\cdots)$ $B$r4pDl$H$9$k9T%Y%/%H%kI=8=$r(B $[h]$, $B9T%Y%/%H%k(B $v$
        !           473: $B$KBP$9$kB?9`<0$r(B $poly(v)$ $B$H=q$/$3$H$K$9$k(B.
        !           474: $$[f] = [f_1 f_2 \cdots]$$
        !           475: $$r_i = [r_{i1} r_{i2} \cdots] \quad (r_i \in Red)$$
        !           476: $B$H$9$k$H$-(B,
        !           477: $$A=\left(
        !           478: \begin{tabular}{ccc}
        !           479: $f_1$ & $f_2$ & $\cdots$ \\
        !           480: $r_{11}$ & $r_{12}$ & $\cdots$ \\
        !           481: $r_{21}$ & $r_{22}$ & $\cdots$ \\
        !           482: & $\cdots$ & \\
        !           483: \end{tabular}
        !           484: \right)$$
        !           485: $B$H$J$i$Y(B, $B$3$l$r(B, $B9T$K4X$9$k4pK\JQ7A$K$h$j<!$N>r7o$rK~$?$99TNs(B
        !           486: $B$ $B$KJQ7A$9$k(B.
        !           487:
        !           488: \begin{itemize}
        !           489: \item $poly(B_i)$ $B$,(B 0 $B$G$J$$$H$-(B, $poly(B_k) (k\neq i)$ $B$O(B $HT(poly(B_i))$
        !           490: $B$r4^$^$J$$(B.
        !           491: \end{itemize}
        !           492:
        !           493: $$B=\left(
        !           494: \begin{tabular}{ccccccc}
        !           495: 1 & 0 & ? & ?        & ? & 0 & $\cdots$ \\
        !           496: 0 & 1 & ? & ?        & ? & 0 & $\cdots$ \\
        !           497: 0 & 0 & 0 & $\cdots$ & 0 & 1 & $\cdots$ \\
        !           498:   &   &   & $\cdots$ &   &   &        \\
        !           499: 0 & 0 & 0 & $\cdots$ & 0 & 0 & $\cdots$
        !           500: \end{tabular}
        !           501: \right)$$
        !           502: $B$3$N$H$-(B,
        !           503: $poly(B_i)$ $B$N$&$A(B, $HT(poly(B_i))$ $B$,(B $\{HT(r)\mid r\in Red\}$ $B$K(B
        !           504: $B4^$^$l$J$$$b$N$,(B, $NF(f,G)$ $B$H$J$k(B.
        !           505:
        !           506: \subsection{$F_4$ $B%"%k%4%j%:%`(B}
        !           507:
        !           508: $BA0@a$G$N(B $B@55,7A7W;;$N8@$$BX$($O(B, $BB?9`<0>jM>1i;;7W;;$K$*$$$F$b$7$P$7$P(B
        !           509: $BMQ$$$i$l(B, $BFC$KL\?7$7$$$b$N$G$b$J$$(B. $F_4$ $B%"%k%4%j%:%`$O(B, $BJ#?t$N(B
        !           510: S-$BB?9`<0$r$^$H$a$F9TNs7A<0$G4JLs$9$k(B. $B$=$N$?$a$N(B symbolic preprocessing
        !           511: $B$b(B, $B=PH/E@$,(B, S-$BB?9`<0$K8=$l$k9`$NOB=89g$H$J$k$@$1$G(B, $B4{$K(B
        !           512: $B=R$Y$?%"%k%4%j%:%`$,$=$N$^$^E,MQ$5$l$k(B.
        !           513:
        !           514: \begin{al} (Symbolic preprocessing)
        !           515: \label{multisymred}
        !           516: \begin{tabbing}
        !           517: Input : $BB?9`<0=89g(B $F$, $BB?9`<0=89g(B $G$\\
        !           518: Output : $Red=\{ah \mid a :$ $BC19`<0(B, $h \in G \}$ \\
        !           519:
        !           520: $T \leftarrow \cup_{f\in F}T(f)$ \\
        !           521: $Red \leftarrow \emptyset$\\
        !           522: while \= $HT(g)|t$ $B$J$k(B $t \in T$, $g \in G$ $B$,B8:_$9$k(B do \{\\
        !           523: \>$Red \leftarrow Red \cup \{t/HT(g)\cdot g\}$\\
        !           524: \>$T \leftarrow (T \setminus \{t\}) \cup T(reductum(t/HT(g)\cdot g)$\\
        !           525: \}\\
        !           526: return $Red$
        !           527: \end{tabbing}
        !           528: \end{al}
        !           529: $B9TNs(B $A$ $B$b(B, $BA4$F$N(B S-$BB?9`<0$KBP1~$9$k%Y%/%H%k$*$h$S(B symbolic preprocessing $B$G(B
        !           530: $BF@$i$l$?(B $Red$ $B$KB0$9$kB?9`<0$KBP1~$9$k%Y%/%H%k$r9T$H$9$k9TNs$H$7$F(B
        !           531: $B9=@.$5$l$k(B. $B$3$N9TNs$r(B, $B9T4pK\JQ7A$K$h$j(B, $B<!$N>r7o$rK~$?$99TNs(B $B$ $B$K(B
        !           532: $BJQ7A$9$k(B.
        !           533:
        !           534: \begin{itemize}
        !           535: \item $poly(B_i)$ $B$,(B 0 $B$G$J$$$H$-(B, $poly(B_k) (k\neq i)$ $B$O(B $HT(poly(B_i))$
        !           536: $B$r4^$^$J$$(B.
        !           537: \end{itemize}
        !           538: $B$3$l$O(B, $t_1 > t_2 > \cdots$ $B$r?7$?$JJQ?t$H$_$F(B, $B$3$N=g=x$G(B reduced $B$J(B
        !           539: \gr $B4pDl$r7W;;$7$?7k2L$KBP1~$9$k(B.
        !           540:
        !           541: $$F' = \{h=poly(B_i) \mid h\neq 0, HT(h)\notin \{HT(r)\mid r\in Red\}\}$$
        !           542: $$Red' = \{h=poly(B_i) \mid h\neq 0, HT(h)\in \{HT(r)\mid r\in Red\}\}$$
        !           543: $B$H$*$/(B.
        !           544: \begin{pr}
        !           545: \begin{enumerate}
        !           546: \item $h\in F'$ $B$O(B $G \cup (F'\setminus \{h\})$ $B$K4X$7$F@55,7A(B
        !           547: \item $f\in F$ $B$J$i$P(B $f \tmred{G\cup F'} 0$
        !           548: \end{enumerate}
        !           549: \end{pr}
        !           550: {\bf Proof}\\
        !           551: 1: $h\in F'$ $B$J$i$P(B $T(h) \cap \{HT(r)\mid r\in Red\} = \emptyset$. $B$3$l$O(B,
        !           552: $Red$ $B$N:n$jJ}$h$j(B $h$ $B$,(B $G$ $B$K4X$7$F@55,7A$G$"$k$3$H$r0UL#$9$k(B.
        !           553: $B$b$A$m$s(B $h$ $B$O(B $F'\setminus \{h\}$ $B$K4X$7$F$b@55,7A$G$"$k(B. \\
        !           554: 2: $f\in F$ $B$H$9$k(B. $$NF(f,G) = f-\sum_{r_i\in Red} c_i r_i\quad (c_i\in K)$$
        !           555: $B$H=q$1$k(B. $B$h$C$F(B, $NF(f,G)$ $B$O(B $F \cup Red$ $B$G(B $K$ $B>e@8@.$5$l$k(B
        !           556: $B@~7A6u4V$KB0$9$k(B. $B$3$3$G(B,
        !           557: $F\cup Red$ $B$H(B $F' \cup Red'$ $B$,(B $K$ $B>eF10l$N@~7A6u4V$r@8@.$7(B,
        !           558: $B$+$D(B $NF(f,G)$ $B$K$O(B $Red'$ $B$N85$NF,9`$O8=$l$J$$$+$i(B,
        !           559: $$NF(f,G)=\sum_{f_i\in F'} d_i f_i\quad (d_i \in K)$$
        !           560: $B$H=q$1$k(B.
        !           561: $B$3$N@~7AOB$OD>$A$K(B $F'$ $B$K4X$9$k@55,7A7W;;$H$J$k(B. \qed\\
        !           562: 2. $B$K$h$j(B $F$ $B$H$7$F(B, $B$$$/$D$+$N(B S-$BB?9`<0$N=89g$r$H$j(B,
        !           563: $F'$ $B$r$^$H$a$F(B $G$ $B$KIU$12C$($k$3$H$K$h$j(B, $F$ $B$KB0$9$k(B S-$BB?9`<0(B
        !           564: $B$,(B 0 $B$K4JLs$5$l$k$3$H$,J,$+$k(B. $B$^$?(B, 1. $B$K$h$j(B,
        !           565: $B%"%k%4%j%:%`$NDd;_@-$b8@$($k(B.
        !           566: $F$ $B$H$7$F0l$D$N(B S-$BB?9`<0$r$H$C$?>l9g$,DL>o$N(B Buchberger $B%"%k%4%j%:%`(B
        !           567: $B$G$"$j(B, $B$=$N>l9g$K$O(B, $BA*$SJ}(B (selection strategy) $B$K$h$C$F8zN($K(B
        !           568: $BBg$-$/:9$,$G$k$3$H$O4{$K=R$Y$?(B. $F_4$ $B$K$*$$$F$b(B $F$ $B$NA*$SJ}$,(B
        !           569: $BLdBj$H$J$k$,(B, $BJ#?t85$rA*Br$G$-$k$3$H$G(B, selection strategy $B$N8zN($K(B
        !           570: $BBP$9$k1F6A$,>/$J$/$J$k$3$H$,<B83$K$h$jCN$i$l$F$$$k(B.
        !           571:
        !           572: $BNc$($P(B, $B<!$N$h$&$J(B strategy $B$K$h$j(B, $BB?$/$NNc$,8zN($h$/7W;;$G$-$k(B.
        !           573:
        !           574: \begin{df}
        !           575: S-$BB?9`<0$N(B sugar $B$N:G>.$N$b$N$rA4$FA*$V(B.
        !           576: \end{df}
        !           577: $B$3$3$G(B, $F_4$ $B$N>l9g(B, $B@55,7A7W;;$K$*$$$FDL>o$N(B sugar $B$O0UL#$r;}$?$J$$$N$G(B,
        !           578: $B$"$k(B sugar $B$N(B S-$BB?9`<0$r=8$a$F7W;;$7$?>l9g(B, $B@8@.$5$l$?4pDl$N(B sugar $B$b(B
        !           579: $B$=$NCM$G$"$k$H$7$F(B, $B:F5"E*$K(B sugar $B$NCM$rDj$a$k$3$H$H$9$k(B.
        !           580: $BFC$K(B, $BF~NOB?9`<0=89g$,(B homogeneous $B$N>l9g(B, $B$3$N(B strategy $B$K$h$j(B,
        !           581: $B3F%9%F%C%W$G7W;;$5$l$k4pDl$O(B, $B<!?t$,(B $d$ $B$N>l9g(B, {\bf reduced} $B$J(B \gr
        !           582: $B4pDl$N$&$A$N(B, $d$ $B<!$N85A4$F$H$J$k(B. $B$3$l$O(B, homogeneous ideal $B$N(B
        !           583: $B>l9g(B,
        !           584:
        !           585: \begin{enumerate}
        !           586: \item $d$ $B<!$N4pDl$r@8@.$9$k$?$a$N(B S-$BB?9`<0$OA4$F(B $d-1$ $B<!0J2<$N(B
        !           587: $B4pDl$+$i:n$i$l$k(B.
        !           588: \item $d$ $B<!$N@F<!B?9`<0$O(B, $d+1$ $B<!0J>e$N4pDl$G$O4JLs$5$l$J$$(B.
        !           589: \end{enumerate}
        !           590:
        !           591: \subsection{Modular $B7W;;$K$h$k@~7AJ}Dx<0$N5a2r(B}
        !           592:
        !           593: $F_4$ $B$K$*$$$F$O(B, selection strategy $B$K=>$C$F9=@.$5$l$?9TNs$r(B,
        !           594: $B:84pK\JQ7A$9$k$H$$$&A`:n$N7+$jJV$7$G4pDl$r@8@.$7$F$$$/(B.
        !           595: $B$3$3$G(B, $B:84pK\JQ7A$O(B, $B@~7AJ}Dx<05a2r$H$_$J$9$3$H$,$G$-$k(B.
        !           596: $B$9$J$o$A(B,
        !           597:
        !           598: \begin{enumerate}
        !           599: \item $B9TNs(B $A$ $B$+$i@~7AFHN)$J9T$rA4$FH4$-$@$7$F(B $A'$ $B$r:n$k(B.
        !           600: \item $A'$ $B$NNs$r:8$+$i=g$K8+$F(B, $B$=$l$^$G<h$j=P$7$?Ns$H@~7AFHN)$J(B
        !           601: $BNs$rH4$-=P$9(B, $B$H$$$&A`:n$r7+$jJV$7$F@5J}9TNs(B $A''$ $B$r:n$k(B.
        !           602: \item $A'$ $B$G;D$C$?Ns$r=8$a$F(B $B''$ $B$H$9$k(B.
        !           603: \item $A''X=B''$ $B$J$k@~7AJ}Dx<0$r2r$/(B.
        !           604: \item $X$ $B$+$i(B, $A'$ $B$N9T4pK\JQ7A$N7k2L$r9=@.$9$k(B.
        !           605: \end{enumerate}
        !           606: $B85$NBN>e$G9M$($k8B$j(B, $B$3$l$OC1$J$k8@$$BX$($K2a$.$J$$$,(B, $BNc$($PM-M}?tBN(B
        !           607: $B>e$N>l9g(B, $\det(A'')\neq 0$ $B$J$k(B $A''$ $B$r(B modular $B7W;;$K$h$j?dB,$7$FH4(B
        !           608: $B$-$@$7(B, $A''X=B''$ $B$N2r8uJd$r(B modular $B7W;;$J$I$K$h$j9=@.$7(B,
        !           609:
        !           610: \begin{itemize}
        !           611: \item $A$ $B$N3F9T$K(B, $BBh(B 5 $B9`$N7k2L$rBeF~$7$F(B 0 $B$K$J$k$3$H$r(B
        !           612: $B3N$+$a$k(B.
        !           613: \end{itemize}
        !           614: $B$H$$$&%A%'%C%/$K$h$j(B modular $B7W;;$N7k2L$,(B, $BM-M}?tBN>e$G$N9T4pK\(B
        !           615: $BJQ7A$N7k2L$HEy$7$$$3$H(B, $BFC$K(B $A$ $B$r9=@.$9$kB?9`<0(B
        !           616: $B$GD%$i$l$F$$$k$3$H(B, $B@~7AJ}Dx<0$N2r$N0l0U@-$K$h$j8@$($k(B.
        !           617: $B$3$N$h$&$J2r8uJd$rM?$($k$b$N$H$7$F(B, $BCf9q>jM>DjM}$*$h$S(B Hensel $B9=@.(B
        !           618: $B$,$"$k(B. $BCf9q>jM>DjM}$rMQ$$$kJ}K!$O(B, $BK!(B $p$ $B$,M-M}?t>e$NA]$-=P$7$H(B
        !           619: $B0[$J$k$b$N$rM?$($J$$8B$j(B, $B<+L@$JJ}K!$G@:EY$r$"$2$F$$$-(B, $B@0?t(B-$BM-M}?t(B
        !           620: $BJQ49$N7k2L$,(B stable $B$K$J$C$?$i(B $A$ $B$KBeF~$7$F%A%'%C%/$H$$$&J}K!$G$"$k(B.
        !           621: $B$^$?(B, Hensel $B9=@.$O(B $B%"%k%4%j%:%`(B \ref{lineq} $B$=$N$b$N$G$"$k(B.
        !           622: Faug\`ere $B$K$h$l$P(B, $F_4$ $B$K$*$$$F$O(B $B$ $B$,Bg$-$/$J$k$?$a(B, $B$ $B$NNs?t(B
        !           623: $B$,(B $A$ $B$N%5%$%:$r1[$($k>l9g$K$OCf9q>jM>DjM}$rMQ$$$?$[$&$,$h$$$H$N$3$H$G$"$k(B.
        !           624: $B$$$:$l$K$;$h(B, modular $B7W;;$K$h$kJ}K!$,8zN($r>e$2$k>l9g$H$$$&$N$O(B,
        !           625: $det(A'')$ $B$KHf$Y$F2r$N78?t$,>.$5$$>l9g$G$"$k(B. $B$3$l$O0lHL$K4|BT(B
        !           626: $B$G$-$k$3$H$G$O$J$$$,(B, $BA0@a$G=R$Y$?$h$&$K(B, homogeneous $B$N>l9g$K(B $F_4$
        !           627: $B$,(B reduced $B$J(B \gr $B4pDl$N0lIt$r@8@.$9$k(B, $B$H$$$&$3$H$+$i(B, reduced $B$K(B
        !           628: $B$7$?>l9g$K78?t$,>.$5$/$J$k$h$&$JLdBj$G$O(B modular $B7W;;$,8zN($r8~>e(B
        !           629: $B$5$;$k$3$H$,4|BT$G$-$k(B.
        !           630:
        !           631: \subsection{$B<B83(B}
        !           632:
        !           633: \cite{REP} $B$G$O(B, 4 $BJQ?t$NBe?tJ}Dx<07O(B (odd order $BJ}Dx<0(B) $B$N%0%l%V%J4pDl7W;;(B
        !           634: $B$r(B Buchberger $B%"%k%4%j%:%`$K$h$j9T$C$?(B. $B$3$N7W;;$K8=$l$kCf4V4pDl$K$*$$(B
        !           635: $B$F(B, 16 $B<!$N4pDl$r@~7A7A<0$H$_$F(B, inter reduction $B$7$F$_$?7k2L(B, $B78?t$,(B
        !           636: $B6KC<$K>.$5$/$J$k$3$H$,$o$+$k(B. $B$b$H$b$H(B, Buchberger $B%"%k%4%j%:%`$G(B odd
        !           637: order $BJ}Dx<0$r7W;;$9$k>l9g(B, $B:G8e$K78?t$,BgJQ>.$5$$4pDl$,2?K\$+=P$F=*N;(B
        !           638: $B$9$k(B. $BFC$K(B, $B:G=i$K8=$l$k(B, $B78?t$N>.$5$$4pDl$,(B, 16 $B<!$N4pDl$N$&$A:G8e$N(B
        !           639: $B$b$N$G$"$C$?$?$a(B, $B$=$N4pDl$rMQ$$$F0l$DA0$N4pDl$r4JLs$7$?$H$3$m(B, $B78?t$,(B
        !           640: $B>.$5$/$J$C$?$?$a(B, $B$=$NA`:n$r4pDlA4$F$KE,MQ$7$?$H$3$m(B, 16 $B<!$N4pDlA4$F(B
        !           641: $B$N78?t$,(B, inter reduction $B$K$h$j>.$5$/$G$-$k$3$H$,J,$+$C$?$N$G$"$k(B.
        !           642: $B4{$K=R$Y$?$h$&$K(B, $B$3$N$h$&$J>l9g$K$O(B, modular $B7W;;$K$h$k2r8uJd$N7W;;$,(B
        !           643: $BM-8z$H$J$k(B. $B$7$+$7(B, 15 $B<!$N4pDl$r(B inter reduction $B$7$?$H$3$m(B, $B78?t$NBg(B
        !           644: $B$-$5$O$[$H$s$IJQ$o$i$:(B, $BBg$-$$$^$^$G$"$C$?(B. $B0J>e$N$h$&$JGX7J$N$b$H$K(B,
        !           645: $B8=:_$N<BAu$G$N(B McKay $BLdBj$KBP$9$k(B Buchberger$B%"%k%4%j%:%`7W;;(B
        !           646: (homogenization+trace lifting) $B$*$h$S(B $F_4$ $B$NHf3S$r<($9(B.
        !           647:
        !           648: \begin{table}[hbtp]
        !           649: \caption{$B7W;;;~4V$NHf3S(B}
        !           650: \begin{center}
        !           651: \begin{tabular}{|c||c|c|c|c|c|} \hline
        !           652:        & total & GaussElim & ChRem & IntRat& Check \\ \hline
        !           653: Buchberger & 264710 & --- & ---        & ---   & ---   \\ \hline
        !           654: $F_4$ homo     & 32880 &  6437 & 6300  & 5763  & 13340 \\ \hline
        !           655: $F_4$ non homo & 39970 & 4832  & 6143  & 18240 & 9950  \\ \hline
        !           656: \end{tabular}
        !           657: \end{center}
        !           658: \end{table}
        !           659:
        !           660: \begin{table}[hbtp]
        !           661: \caption{$B3F<!?t$N9TNs$N%5%$%:(B}
        !           662: \begin{center}
        !           663: \begin{tabular}{|c||c|c|c|c|c|c|} \hline
        !           664:        & 10 & 11 & 12 & 13 & 14 & 15 \\ \hline
        !           665: $F_4$ homo &(56,334) & (119,441) & (182,545) & (362,774) & (671,1009) & (1195,1359) \\ \hline
        !           666: $F_4$ non homo &(62,339) & (128,448) & (137,461) & (227,571) & (307,621) & (955,1149) \\ \hline
        !           667: \end{tabular}
        !           668:
        !           669: \begin{tabular}{|c||c|c|c|c|c|c|} \hline
        !           670: & 16 & 17 & 18 & 19 & 20 & 21 \\ \hline
        !           671: $F_4$ homo &(836,688) &(2323,1761) &(895,964)  &(204,271) &(446,515) &(308,374) \\ \hline
        !           672: $F_4$ non homo & (555,508) & (2022,1763) & --- & --- & --- & --- \\ \hline
        !           673: \end{tabular}
        !           674:
        !           675: \begin{tabular}{|c||c|c|c|c|} \hline
        !           676:  & 22 & 23 & 24 & 25 \\ \hline
        !           677: $F_4$ homo & --- & --- & --- & --- \\ \hline
        !           678: $F_4$ non homo & (799,868)& (300,367) & (398,467) & (361,427) \\ \hline
        !           679: \end{tabular}
        !           680: \end{center}
        !           681: \end{table}
        !           682:
        !           683: \begin{table}[hbtp]
        !           684: \caption{$B3F<!?t$N4pDl$N7W;;;~4V(B}
        !           685: \begin{center}
        !           686: \begin{tabular}{|c||c|c|c|c|c|c|} \hline
        !           687:        & 10 & 11 & 12 & 13 & 14 & 15 \\ \hline
        !           688: Buchberger & 2.3 & 11 & 43 & 164 & 1214 & 32512 \\ \hline
        !           689: $F_4$ homo & 1.8 & 10 & 45 & 357 & 2574 & 26519\\ \hline
        !           690: $F_4$ non homo & 2.2 & 12& 28 & 166& 1064 & 35906\\ \hline
        !           691: \end{tabular}
        !           692:
        !           693: \begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|} \hline
        !           694: & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 \\ \hline
        !           695: Buchberger & 205234 & 10300 & 4530 & --- & 10700 & --- & --- & --- & --- & --- \\ \hline
        !           696: $F_4$ homo & 1340 & 1097 & 359 & 45 & 208 & 150 & --- & --- & --- & --- \\ \hline
        !           697: $F_4$ non homo & 937 & 902 & --- & --- & --- & --- & 341& 132 & 186 & 164 \\ \hline
        !           698: \end{tabular}
        !           699: \end{center}
        !           700: \end{table}
        !           701:
        !           702: \begin{figure}[htbp]
        !           703: \epsfxsize=15cm
        !           704: \epsffile{ps/blenall.ps}
        !           705: \caption{$BCf4V4pDl$N:GBg78?t$N%S%C%HD9(B}
        !           706: \label{nftime}
        !           707: \end{figure}
        !           708:
        !           709: $B$^$:(B, total $B;~4V$,(B 1/8 $BDxEY$K8:$C$F$$$k$3$H$KCmL\$7$?$$(B. $B$3$l$O(B, $B4pDl$N(B
        !           710: $B7W;;;~4V$NFbLu$r$_$l$P$o$+$k$h$&$K(B, Buchberger $B%"%k%4%j%:%`$K$h$k7W;;$G(B
        !           711: $BA4BN$N7W;;;~4V$NBgItJ,$r@j$a$F$$$?(B 16 $B<!$N7W;;$,(B 1/100 $BDxEY$N;~4V$G=*$C$F(B
        !           712: $B$$$k$?$a$G$"$k(B. $B$3$l$O(B, $B:GBg78?t$N%S%C%HD9$,(B reduced $B$J4pDl$GHs>o$K>.$5$/(B
        !           713: $B$J$k$3$H$KBP1~$7$F$$$k(B. $B$=$l0J>e$N<!?t$K$D$$$F$O(B, $B>.$5$$78?t$r;}$D(B
        !           714: $BB?9`<0$K$h$k4JLs2=$G:Q$`$3$H$,9bB.2=$NM}M3$G$"$k(B.
        !           715:
        !           716: \subsection{$B9M;!(B}
        !           717:
        !           718: $F_4$ $B$OK\<AE*$K$O(B Buchberger $B%"%k%4%j%:%`$N2~NI$H9M$($i$l$k$,(B, $B<!$N$h$&$J(B
        !           719: $BD9=j$r;}$D(B.
        !           720:
        !           721: \begin{itemize}
        !           722: \item $B9TNs$NA]$-=P$7Cf$O(B, $B9`$N=g=xHf3S$,C1$J$k(B index $B$NHf3S$K$J$k(B.
        !           723: \item $BCf4V4pDl$r(B reduced $B$"$k$$$O$=$l$K6a$$7A$KJ]$D$?$a(B, $B$=$N8e$N(B
        !           724: $BA]$-=P$77W;;$,8zN(2=$9$k(B. ($B!VBP3Q2=!W$5$l$?9TNs$K$h$k4JLs2=(B vs. $B!V;03Q2=!W(B
        !           725: $B$5$i$?9TNs$K$h$k4JLs2=(B)
        !           726: \item reduced $B$J4pDl$N78?t$,>.$5$/$J$k>l9g$K$O(B, modular $B7W;;$K$h$k(B
        !           727: $B8zN(2=$,4|BT$G$-$k(B. $B$?$@$7(B, $B$3$N>l9g$K$O(B, $B9TNs$N3F9T$N(B 0 $B4JLs%A%'%C%/(B
        !           728: $B$,I,?\$G$"$k(B.
        !           729: \end{itemize}
        !           730: $B8zN($K4X$7$F$$$($P(B, Risa/Asir $B$G$N8=>u$O(B, Faug\`ere $B$N(B home page
        !           731:
        !           732: \centerline{{\tt http://posso.lib6.fr/\til jcf/bench.html}}
        !           733: \noi
        !           734: $B$K$"$k%G!<%?$K5Z$V$Y$/$b$J$$(B.
        !           735: $B$?$H$($P(B, McKay $B$G(B, P6-200MHz PC $B>e$G(B 54 $BIC$HJs9p$5$l$F$$$k(B. $B$7$+$7(B,
        !           736: Faug\`ere\cite{F} $B$K(B,
        !           737: Moreover, since big integer computations could be done by means of p-adic
        !           738: or multi modular arithmetics it means that the cost of an integer computation is roughly
        !           739:
        !           740: \centerline{time of modular computation * size of the output coeffs}
        !           741: \noi
        !           742: $B$H=q$+$l$F$$$k$3$H$+$i(B, $BCf4V4pDl$KBP$9$k@5Ev@-%A%'%C%/$I$3$m$+(B, $BC1$J$k(B
        !           743: modular \gr $B4pDl7W;;$r(B, $BCf9q>jM>DjM}$K$h$k7k2L$,(B stable $B$K$J$k$^$G7+$jJV$7$F(B
        !           744: $B$$$k$@$1(B, $B$H$$$&2DG=@-$b<N$F@Z$l$J$$(B. $BH`$,$b$&>/$7<BAu$rL@$i$+$K$7$F$/$l$k(B
        !           745: $B$3$H$rK>$s$G$$$k(B.
        !           746: Faug\`ere $B$O(B,
        !           747: \begin{enumerate}
        !           748: \item Buchberger $B%"%k%4%j%:%`$K$*$1$k(B selection strategy $B$HHf$Y$F(B,
        !           749: $F_4$ $B$G$O(B ``make no choice''
        !           750: \item non homogeneous case $B$N5sF0$r8+$l$P(B, $F_4$ $B$O(B Buchberger $B%"%k%4%j%:%`(B
        !           751: $B$G$O$J$$(B.
        !           752: \end{enumerate}
        !           753: $B$H=q$$$F$$$k$,(B, 1. $B$K4X$7$F$O(B, critcal pair $B$N(Bsubset $B$r$I$&A*$V$+$G(B,
        !           754: $B8zN($KBg$-$/:9$,=P$k$3$H$O(B, McKay $B$NNc$+$iL@$i$+$G$"$k(B. $B$^$?(B, 2. $B$K4X(B
        !           755: $B$7$F$O(B, $B%"%k%4%j%:%`$N4pK\9=B$$OL@$i$+$K(B Buchberger$B%"%k%4%j%:%`$G$"$j(B
        !           756: $B5?Ld$G$"$k(B. $B$H$O$$$((B, $B=>Mh$N(B Buchberger$B%"%k%4%j%:%`$h$j8zN($h$/7W;;$G(B
        !           757: $B$-$k>l9g$,$"$k$3$H$O3N$+$G$"$j(B, $B3FIt$N2~NI$r4^$a$F(B, $B$h$j8zN($h$$<BAu$r(B
        !           758: $BL\;X$9$3$H$,<BMQ>e=EMW$G$"$k$H9M$($i$l$k(B.
        !           759: