Return to effgr.tex CVS log

Up to [local] / OpenXM / doc / compalg

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

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