[BACK]Return to effgr.tex CVS log [TXT][DIR] Up to [local] / OpenXM / doc / compalg

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

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

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>