Return to effgr.tex CVS log

Up to [local] / OpenXM / doc / compalg

Updated the description of F_4.
Added references on the knapsack factorization algorithm.

%$OpenXM: OpenXM/doc/compalg/effgr.tex,v 1.4 2001/02/27 08:07:24 noro Exp $
\chapter{$B%0%l%V%J4pDl7W;;$N8zN(2=(B}

$BBh(B \ref{chapgr} $B>O$G%0%l%V%J4pDl$r7W;;$9$k%"%k%4%j%:%`$G$"$k(B 
Buchberger $B%"%k%4%j%:%`$N:G$b86;OE*$J7A$r<($7$?(B. $B$7$+$7(B, $B$=$3$G=R$Y$?(B
$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
$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
$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
$B$&$JA*$SJ}$rMQ$$$F$b(B, $B:G=*7k2L$G$"$k%0%l%V%J4pDl$N0l0U@-$OJ]>Z$5$l$F$$(B
$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
$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
$B$9$k(B.

\begin{nt}
$B0J2<$G(B, $B<!$N$h$&$J5-K!$rMQ$$$k(B. 

\noi
$p$ : $BAG?t(B.\\
$GF(p)$ : $p$ $B85BN(B.\\
$\Z_{(p)}$ = $\{a/b \mid a \in \Z; b \in \Z \setminus p\Z\} \subset \Q$ :
$\Z$\, $B$N(B $p\Z$ $B$K$*$1$k6I=j2=(B.\\
$X = \{x_1,\cdots,x_n\}$ : $BITDj85(B.\\
$\phi_p$ : $\Z_{(p)}[X]$ $B$+$i(B $GF(p)[X]$ $B$X$NI8=`E*<M1F(B.
$\phi_p(a/b) = \phi_p(a)/\phi_p(b)$. ($a \in \Z$, $b\in \Z\setminus p\Z$.)\\
$<$, $<_0$, $<_1$, $<_i$ : term order.\\
$HT_<(f)$ : $f$ $B$N(B $<$ $B$K4X$9$kF,9`(B.\\
$HC_<(f)$ : $f$ $B$N(B $<$ $B$K4X$9$kF,78?t(B.\\
$T(f)$ : $f$ $B$K8=$l$k9`A4BN$N=89g(B.\\
$GB_<(S)$ : $S$ $B$N(B $<$ $B$K4X$9$kHoLs%0%l%V%J4pDl(B.\\
$f_1,\cdots,f_m$ : $\Z[X]$ $B$N85(B.\\
$NF_<(f,G)$ : $f$ $B$N(B $G$ $B$K4X$9$k@55,7A$N0l$D(B.\\
$Init_<(I)$ : \{$HT_<(f)\mid f\in I$\} $B$G@8@.$5$l$k%$%G%"%k(B.\\
$Useless\_Pairs(D)$ : $BITI,MWBP$N8!=P(B.\\
$Select\_Pair(D)$ : $BBP$NA*Br(B\\
$Sp(C)$ : $BB?9`<0BP$N(B S-$BB?9`<0$N7W;;(B
\end{nt}

\section{$BITI,MWBP$N8!=P(B}
Buchberger $B%"%k%4%j%:%`$K$*$$$F(B, $B@55,2=$K$h$j(B 0 $B$K$J$kBP$rITI,MWBP$H8F(B
$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
$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
$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
$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
$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
$B$*$$$F8=$l$F$$$k(B. $B$3$NL?Bj$r(B, Taylor $B4pDl$KE,MQ$9$l$P(B, Taylor $B4pDl$N$&(B
$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
$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
$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
$B$+$l$kBP$b$"$jF@$k(B. $B$3$l$i$K$D$$$F=R$Y$k(B. 

\subsection{$B>iD9$J4pDl$N=|5n(B}
Taylor $B4pDl$+$i>iD9$J4pDl$r<h$j=|$/$?$a$N4pK\E*$JF;6q$O(B, $B4pDl4V$N<!$N(B
$B<+L@$J91Ey<0$G$"$k(B.
$$ {T_{ijk}\over T_{ij}} S_{ij} + {T_{ijk}\over T_{jk}} S_{jk} +
{T_{ijk}\over T_{ki}} S_{ki} = 0 $$
$B$3$N91Ey<0$K$*$$$F(B, $B$$$:$l$+$N78?t$,(B 1 $B$G$"$l$P(B, $B$=$N9`$KBP1~$9$k4pDl(B
$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
$B9T$/$,(B, $B$3$N:](B, $BAj8_$K0MB8$79g$&4pDl$r8m$C$F<h$j=|$/$3$H$rHr$1$k$?$a(B, 
$B4pDl4V$KA4=g=x$rF~$l(B, $B$"$k4pDl$,$=$l$h$j=g=x$NDc$$4pDl$K$h$j@8@.$5$l$F(B
$B$$$k>l9g$K$N$_(B, $B$=$N4pDl$r<h$j=|$/$3$H$H$9$k(B. 

\begin{df}
$\{S_{ij}\mid i < j\}$ $B$K$*$1$kA4=g=x$r<!$N$h$&$KDj5A$9$k(B. 

\noi
$S_{ij} < S_{kl} \Leftrightarrow$\\
$T_{ij} < T_{kl}$ $B$^$?$O(B\\
($T_{ij} = T_{kl}$ $B$+$D(B ($j < l$ $B$^$?$O(B ($j = l$ $B$+$D(B $i < k$)))
\end{df}

\begin{df}
$BBP(B $(i,j)$ $B$K4X$9$k;0$D$N@-<A$r<!$N$h$&$KDj5A$9$k(B. 

\noi
$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}$

\noi
$F(i,j) \Leftrightarrow$ $B$"$k(B $k < i$ $B$,B8:_$7$F(B $T_{kj} = T_{ij}$

\noi
$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}$
\end{df}

\noi
$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
$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
$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, 
$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
$B$J$jN)$D(B. 

\begin{pr}(Gebauer and M\"oller{\rm\cite{GEB}})
Taylor $B4pDl$O(B,  $\{S_{ij} \mid \neg M(i,j), \neg F(i,j), \neg B(i,j)\}$
$B$G@8@.$5$l$k(B. 
\end{pr}

\begin{re}
$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
$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, 
$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, 
$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
$B4XO"$G(B, $B%"%k%4%j%:%`$N?J9T$K=EBg$J1F6A$r5Z$\$9>l9g$,$"$k(B. 
\end{re}

\subsection{0 $B$K@55,2=$5$l$kBP$N=|5n(B}
$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
$B$,$"$jF@$k(B. 

\begin{pr}(Buchberger)\\
$\GCD(HT(f),HT(g))=1$ $B$J$i$P(B  $Sp(f,g) \tmred{\{f,g\}} 0$ 
\end{pr}
\proof
$f = \sum_i f_i$, $g = \sum_i g_i$ ($f_i, g_i \in M; f_1 > f_2 >
\cdots, g_1 > g_2 > \cdots$; $B$"$kE:;z0J9_$O(B 0 $B$H$7$F$*$/(B) $B$H$9$k(B. 
$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
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 
$k$ $B$,B8:_$7$F(B \\ $Sp(f,g) \tmred{\{f,g\}} R_m =
(g_1+\cdots+g_k)(f_{m-k+1}+\cdots)-(f_1+\cdots+f_{m-k})(g_{k+1}+\cdots)$\\
$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. 
$\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
$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}$.
$B$9$k$H(B, \\
$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)$\\
$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. 
$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

\noi
$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
$BBP$r=|5n$9$k$3$H$,$G$-$k(B. 

\section{$B@55,2=BP$NA*Br@oN,(B}
$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, 
$B%"%k%4%j%:%`$N@5Ev@-$K$O$J$s$i1F6A$7$J$$$,(B, $B<B:]$N7W;;8zN($KBg$-$/1F6A(B
$B$rM?$($k(B. Buchberger $B$K$h$jDs0F$5$l$?@oN,$O<!$N$b$N$G$"$k(B.

\begin{df}
{\bf normal strategy}\\
$T_{ij}$ $B$,:G>.$JBP$+$iA*Br$9$k@oN,$r$$$&(B. 
\end{df}

\noi
$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
$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
$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
$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
$BHf3S$r9T$o$J$$=g=x$G?S$@$7$$(B. 

\begin{df}
{\bf $B@F<!2=(B}\\
$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]$
$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. 
$B0J2<(B, $f$ $B$NA4<!?t$r(B $\tdeg(f)$ $B$H=q$/(B. 
$$f^* = t^{\tdeg(f)}f(x_1/t,\cdots,x_n/t)$$
$$g_* = g|_{t=1}$$$B$G$"$k(B. $BB?9`<0=89g(B $F \subset R$, $G \subset R_h$ $B$K(B
$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.

$B$3$N$H$-(B, $R$ $B$N(B order $<$ $B$KBP$7$F(B, $R_h$ $B$N(B order $<_h$ $B$,(B
\begin{center}
(H) $BG$0U$N@F<!B?9`<0(B $g \in R_h$ $B$KBP$7(B, 
$HT(g)_* = HT(g_*)$
\end{center}
$B$rK~$?$9$H$-(B, $<_h$ $B$r(B $<$ $B$N@F<!2=$H8F$V$3$H$K$9$k(B. 
\end{df}

\begin{ex}
\label{horder}
$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
$B$G$"$k$,(B, $BDj5A$K$h$j(B, 

\begin{center}
$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$
\end{center}
$B$J$k(B $<_h$ $B$b(B $<$ $B$N@F<!2=$G$"$k(B. 
\end{ex}

\begin{pr}
\label{hcomp}
$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, 
$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, 
$G_*$ $B$O(B $Id(F)$ $B$N%0%l%V%J4pDl$H$J$k(B. 
\end{pr}
$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
$BA4<!?tHf3SF~$j$N(B $<_h$ $B$N$b$H$G(B normal strategy $B$G7W;;$7$?8eHs@F<!2=$9(B
$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
$B%9%`!<%:$K?J9T$9$k$3$H$,7P83E*$KCN$i$l$F$$$?(B. $B78?tBN$,M-8BBN$N>l9g$K$O(B, 
$B8e$G=R$Y$k(B, $BITI,MWBP$KBP$9$k@55,7A7W;;$G@8$8$k78?tKDD%$NLdBj$,@8$8$J$$(B
$B$?$a(B, $BM-8BBN>e$G$N%0%l%V%J4pDl7W;;$K$O@F<!2=$OM-MQ$G$"$k(B.

\begin{df}
{\bf sugar strategy}\\
$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
$s_f$ (sugar) $B$rBP1~$5$;$k(B. 

\begin{enumerate}
\item $BF~NOB?9`<0(B $f$ $B$KBP$7$F$O(B, $s_f = \tdeg(f)$
\item $m$ $B$,(B monomial $B$N;~(B $s_{mf} = \tdeg(m)+s_f$
\item $s_{f+g} = \max(s_f,s_g)$
\end{enumerate}
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
strategy $B$GBP$rA*Br$9$k@oN,$r$$$&(B. 
\end{df}
Giovini $B$i(B{\rm\cite{SUGAR}}$B$K$h$jDs0F$5$l$?$3$N@oN,$O(B, $BF~NOB?9`<0=89g(B
$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
$B@F<!2=8e$N<!?t$KBP1~$7$F$$$k(B. 

\section{Trace lifting}

sugar strategy $B$K$h$j(B, $B>/$J$/$H$b78?tBN$,M-8BBN$N>l9g$K$O(B, $B==J,$J8zN((B
$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
$B=P4p=`$K$+$+$i$J$$ITI,MWBP$N(B S $BB?9`<0$N@55,2=7W;;$K$+$+$k%3%9%H$,Bg$-(B
$B$$>l9g$,$7$P$7$P$"$k(B. 
$B$=$N$?$a(B, $B<!$N$h$&$J%"%k%4%j%:%`(B ({\bf trace lifting})
$B$,Ds0F$5$l$?(B \cite{TRAV}.

\begin{al}
\label{tl}
\begin{tabbing}
\\
trace\_lifting$(F,<)$\\
Input : $F \subset \Z[X]$; term order $<$\\
Output : $F$ $B$N(B $<$ $B$K4X$9$k%0%l%V%J4pDl(B\\

do \= \{\\
\> $p \leftarrow$ $BL$;HMQ$NAG?t(B\\
\> $G \leftarrow tl\_guess(F,<,p)$\\
\> if \= $G \neq$ {\bf nil} $B$+$D(B tl\_check$(F,G,<) =1$ \\
\> then return $G$\\
\}
\end{tabbing}
\end{al}

\begin{al}
\label{tlguess}
\begin{tabbing}
\\
tl\_guess$(F,<,p)$\\
Input : $F \subset \Z[X]$; term order $<$; $BAG?t(B $p$\\
Output : $F$ $B$N%0%l%V%J4pDl8uJd$^$?$O(B {\bf nil}\\

if \= $B$"$k(B $f \in F$ $B$,B8:_$7$F(B $\phi_p(HC(f))=0$ then return {\bf nil}\\
$G \leftarrow F$\\
$G_p \leftarrow \{\phi_p(f) \mid f \in G\}$\\
$D \leftarrow \{\{f,g\} \mid f,g \in G; f \neq g\}$\\
do \= \{\\
\> $D \leftarrow D \setminus Useless\_Pairs(D)$\\
\> if \= $D = \emptyset$ then return $G$\\
\> else \{ \= $C \leftarrow Select\_Pair(D)$\\
\>         \> $D \leftarrow D \setminus \{C\}$\\
\> \}\\
\> $s \leftarrow Sp(C)$\\
\> $t_p = NF(\phi_p(s),G_p)$\\
\> if \= $t_p \neq 0$ then \{\\
\>    \> $t \leftarrow NF(s,G)$\\
\>    \> if $\phi_p(HC(f)) = 0$ then return {\bf nil}\\
\>    \> $D \leftarrow D \cup \{\{f,t\} \mid f \in G\}$\\
\>    \> $G \leftarrow G \cup  \{t\}$\\
\>    \> $G_p \leftarrow G_p \cup  \{t_p\}$\\
\> \}\\
\}
\end{tabbing}
\end{al}

\noi
$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
$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
$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 
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
$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
$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.
\begin{al}
\label{tlcheck}
\begin{tabbing}
\\
tl\_check$(F,G,<)$\\
Input : $BB?9`<0=89g(B $F, G \subset \Z[X] \st G \subset Id(F)$; order $<$\\
Output :\= $B$b$7(B $G$ $B$,(B $<$ $B$K4X$9$k(B $F$ $B$N%0%l%V%J4pDl$J$i(B 1\\
        \> $B$=$&$G$J$1$l$P(B 0\\
if \= $G$ $B$,(B $<$ $B$K4X$7$F%0%l%V%J4pDl$G$J$$(B then return 0\\
if $B$9$Y$F$N(B $f \in F$ $B$KBP$7(B $NF_<(f,G) = 0$ then return 1 else return 0
\end{tabbing}
\end{al}
$B<B:](B, $B%"%k%4%j%:%`(B \ref{tlguess} $B$N=PNO(B $G$ $B$KBP$7(B, $G \subset Id(F)$ 
$B$O9=@.K!$h$j>o$K@.$jN)$D$+$i(B, \ref{tlcheck} $B$,(B 1 $B$rJV$;$P(B $Id(G) =
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
$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 
$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
$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
$BAG?t$O$"$i$+$8$a7hDj$9$k$3$H$O$G$-$J$$$,(B, $BITET9g$JAG?t$OM-8B8D$G$"$j(B, 
$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,
\begin{center}
$BITI,MWBP$KBP$9$k(B S $BB?9`<0$N7W;;%3%9%H(B\\
$\Downarrow$\\
$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
$B%a%s%P%7%C%W%F%9%H(B
\end{center}
$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
$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
$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
$BHLE*$K$O<!$N$h$&$J$3$H$,8@$($k(B. 
\begin{itemize}
\item $V(Id(F))$ $B$NM><!85$,Bg$-$$>l9g(B

$B%0%l%V%J4pDl7W;;$K8=$l$k78?t$,(B
$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
$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, 
$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
$B$bHf3SE*MF0W$G$"$k(B. 

\item $V(Id(F))$ $B$NM><!85$,>.$5$$>l9g(B

$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
$BJ,$J%3%9%H$K$D$J$,$k(B. 
\end{itemize}
$B$3$N$h$&$K(B, $B8z2L$,4|BT$G$-$J$$>l9g$b$"$jF@$k$,(B, $B$=$N$h$&$J>l9g$G$b(B
$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
$B$N$,0BA4$G$"$m$&(B. 

$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
$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
$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, 
$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
$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
$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. 

\section{$B@F<!2=(B $B$H(B trace lifting $B$NAH9g$;(B}

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
$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
$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
$B$K@F<!2=$7$?>l9g$K$O@8$8$J$$$h$&$JCf4V78?tKDD%$,(B, sugar strategy  $B$NE,(B
$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
$B$NJ}K!$K$D$$$F=R$Y$k(B.\\
$B$3$N$h$&$J78?tKDD%$r4JC1$JNc$G<($9(B. 

\begin{ex}
$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)$
\end{ex}
$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, \\
$GB(I) = \{f_3(x_3), f_2(x_2,x_3), f_1(x_1,x_3), f_0(x_0,x_3) \}$\\
$f_3=286978140000x_3^6-30735638450064x_3^5+139368108773718x_3^4-401122901874078x_3^3\\
+3813285736741284x_3^2-17712668879937657x_3+25309718023001309$\\
$f_2=-24359129516408255978429894458178435051554483918248x_2\\
-9117338725200447183121773483618146011417380000x_3^5\\
+945437242481668390348909147393962329546603617488x_3^4\\
-1215199713704678902273407299537086048391876350746x_3^3\\
+9203891427703221172499174842307408763060278519544x_3^2\\
-87128026603776953223695902278763008965980027109460x_3\\
+198072128718550346069760390022952204794356946307195$\\
$f_1=24359129516408255978429894458178435051554483918248x_1\\
-9117338725200447183121773483618146011417380000x_3^5\\
+945437242481668390348909147393962329546603617488x_3^4\\
-1215199713704678902273407299537086048391876350746x_3^3\\
+9203891427703221172499174842307408763060278519544x_3^2\\
-87128026603776953223695902278763008965980027109460x_3\\
+238670677912564106033810214119916263213614419504275$\\
$f_0=-9134673568653095991911210421816913144332931469343x_0\\
-334442494143970788481038492015748108482000000x_3^5\\
+37671432710327352302696037580172208903376423200x_3^4\\
-352356049164307536666247874973386638400872538040x_3^3\\
+499969270855985351160909518989653220917608771262x_3^2\\
-6841618915067057146509523126510725094238856771432x_3\\
+31588951614319486540726259755101613855437086625238$\\
$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
$B$N:GBgCM$O(B 1489 $B%S%C%H$@$,(B, sugar strategy $B$N$_$rMQ$$$F9T$C$?>l9g$=$N(B
$B:GBgCM$O(B 10258121 $B%S%C%H$G$"$C$?(B. $B$3$N$h$&$J>.$5$$LdBj$KBP$7$F$b(B,
sugar strategy $B$,$&$^$/F/$+$J$$>l9g$K$OITI,MW$J78?tKDD%$,@8$8$F$7$^$&(B. 
$B@F<!2=$O@8@.$5$l$k4pDl$N78?tKDD%$,5/$3$i$J$$$h$&$J(B strategy $B$rM?$($k>l(B
$B9g$,B?$$$,(B, $BHs@F<!$N>l9g$KHf$Y$FA0$K=R$Y$?ITI,MWBP$N8!=P$K$+$+$i$J$$IT(B
$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
$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
$B$k(B.
\begin{al}
\label{htl}
\begin{tabbing}
\\
homogenized\_trace\_lifting$(F,<)$\\
Input : $F \subset \Z[X]$; term order $<$\\
Output : $F$ $B$N(B $<$ $B$K4X$9$k%0%l%V%J4pDl(B\\

do \= \{\\
\> $p \leftarrow$ $BL$;HMQ$NAG?t(B\\
\> $G \leftarrow tl\_guess(F^*,<_h,p)$\\
\> if \= $G \neq$ nil\\
\>    \>$B$+$D(B $G_*$ $B$,(B $<$ $B$K4X$9$k%0%l%V%J4pDl(B\\
\>    \>$B$+$D$9$Y$F$N(B $f \in F$ $B$KBP$7(B $NF(f,G_*) = 0$\\
\> then return $G_*$\\
\}
\end{tabbing}
\end{al}
$<_h$ $B$O(B $BNc(B \ref{horder} $B$G=R$Y$?(B order $B$NA4<!?tIU@F<!2=$rMQ$$$F$$(B
$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
$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
$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
$B$K4X$9$k%3%9%H$O(B trace lifting $B$K$h$j4KOB$5$l$k(B.

\begin{itemize}
\item $B@F<!2=(B $\Rightarrow$ $B8uJd@8@.(B $\Rightarrow$ $BHs@F<!2=(B $\Rightarrow$ $B%F%9%H(B

$BHs@F<!2=$r9T$J$C$?;~E@$G>iD9$J4pDl$r<h$j=|$/$?$a(B, $B%F%9%H$K$+$+$k%3(B
$B%9%H$O@F<!2=$r9T$J$o$J$$>l9g$HJQ$o$i$J$$(B.

\item $B@F<!2=(B $\Rightarrow$ $B8uJd@8@.(B $\Rightarrow$ $B%F%9%H(B $\Rightarrow$ $BHs@F<!2=(B

$B@F<!$J%0%l%V%J4pDl8uJd$N>l9g(B, $B>iD9$J4pDl$,$[$H$s$I$J$/(B, trace lifting $B$K(B
$B$h$j%+%C%H$5$l$?BgItJ,$NITI,MWBP$rM-M}?tBN>e$G2~$a$F@55,2=$9$kI,MW$,$"$k(B. 
\end{itemize}
$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
$B$,$h$$(B. $B$3$NJ}K!$K$h$j(B, trace lifting $B$N$_$G$O7W;;IT2DG=$@$C$?B?$/$NLdBj(B
$B$,7W;;2DG=$K$J$C$?(B. 

\section{$F_4$ $B%"%k%4%j%:%`(B}

$BBe?tJ}Dx<05a2r$K8B$i$:(B, $BBe?t4v2?$K$*$1$kITJQNL$N7W;;$J$I$K$*$$$F$b(B
$BG$0UF~NOB?9`<0=89g$+$i$N%0%l%V%J4pDl$N7W;;$O(B, $B7W;;NLE*$K$_$F(B dominant
step $B$H$J$k$3$H$,B?$$(B. $B$3$N$h$&$J>l9g$N7W;;K!$H$7$F$O(B Buchberger
$B%"%k%4%j%:%`$,$[$\M#0l$NJ}K!$G$"$C$?$,(B, $B:G6a(B Faug\`ere $B$K$h$j(B
$F_4$ ($B$"$k$$$O(B $F_5$) $B%"%k%4%j%:%`$,Ds0F$5$l(B, $B$=$N9bB.@-$,(B
$BCmL\$5$l$F$$$k(B. $BK\@a$G$O(B, $B$3$N%"%k%4%j%:%`$K$D$$$F35@b$9$k(B. 

\subsection{Symbolic preprocessing}

$B%"%k%4%j%:%`(B \ref{buch} $B$r<B9T$9$k>l9g(B, $D$ $B$+$i$I$N85$rA*$s$GMh$k$+(B
$B$G(B, $B$=$N8e$N7W;;$N?J9T$NMM;R$,A4$/$3$H$J$k(B, $B$H$$$&$3$H$,(B
$B5/$3$k(B. $B$^$?(B, $B:GA1$N85$rA*$s$@$D$b$j$G$b(B, $BFC$KM-M}?tBN>e(B
$B$J$I$K$*$$$F(B, $NF(Sp(f,g),G)$ $B$N78?t$,6KC<$KBg$-$/$J$j(B, 
$B7W;;ITG=$K$J$k$3$H$b5/$3$k(B. $B$=$N$?$a(B, trace lifting,
homogenization $B$J$I$N<o!9$N%F%/%K%C%/$N$b$H$G7W;;$,;n$_$i$l$F(B
$BMh$?(B. 
$B$3$3$G(B, Buchberger $B%"%k%4%j%:%`$N3K?4$G$"$k(B $NF(Sp(f,g),G)$
$B$K$D$$$F9M;!$9$k(B. 
$NF(Sp(f,g),G)$ $B$O<!$N$h$&$J<j=g$G7W;;$5$l$k(B. 

\begin{tabbing}
$r \leftarrow af - bg$ ($a, b$ $B$OC19`<0(B) \\
while \= ( $r$ $B$N9`(B $t$ $B$r3d$j@Z$k(B $h \in G$ $B$,$"$k(B )\\
\> $ r \leftarrow r - ch $\\
\> ($r$ $B$K(B $t$ $B$N9`$O$J$$(B)
\end{tabbing}
$B$3$3$G(B, $r$ $B$r4JLs$9$k$N$KI,MW$J(B $h \in G$ $B$O0l8+<B:]$K4JLs(B
$BA`:n$r<B9T$7$J$1$l$PJ,$+$i$J$$$h$&$K8+$($k$,(B, $B>iD9$J85(B
($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
$BJ}K!$G;vA0$KF@$i$l$k(B. 

\begin{al} (Symbolic preprocessing)
\label{symred}
\begin{tabbing}
Input : $BB?9`<0(B $f$, $BB?9`<0=89g(B $G$\\
Output : $Red=\{ah \mid a :$ $BC19`<0(B, $h \in G \}$ \\

$T \leftarrow T(f)$ \\
$Red \leftarrow \emptyset$\\
while \= $HT(g)|t$ $B$J$k(B $t\in T$, $g \in G$ $B$,B8:_$9$k(B do \{\\
\>$Red \leftarrow Red \cup \{t/HT(g)\cdot g\}$\\
\>$T \leftarrow (T \setminus \{t\}) \cup T(reductum(t/HT(g)\cdot g)$\\
\}\\
return $Red$
\end{tabbing}
\end{al}
$B$3$N%"%k%4%j%:%`$GF@$i$l$?(B $Red$ (Reducer) $B$O<!$N@-<A$r$b$D(B:

\begin{itemize}
\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.
\end{itemize}
$B$3$l$h$j(B, $B<!$,8@$($k(B. 

\begin{itemize}
\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
$B4X$9$k@55,7A$H$J$k(B.
\end{itemize}
$B$3$l$r(B, $B9TNs$N8@MU$G8@$$49$($k$?$a$K<!$N=`Hw$r$9$k(B. 
$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
$B=g$KJB$Y$?$b$N$r(B $t_1 > t_2 > \cdots $ $B$H$9$k(B. 
$T$ $B$G(B $K$ $B>eD%$i$l$k@~7A6u4V$N85(B $h$ $B$N(B, 
$(t_1,t_2,\cdots)$ $B$r4pDl$H$9$k9T%Y%/%H%kI=8=$r(B $[h]$, $B9T%Y%/%H%k(B $v$
$B$KBP$9$kB?9`<0$r(B $poly(v)$ $B$H=q$/$3$H$K$9$k(B. 
$$[f] = [f_1 f_2 \cdots]$$
$$r_i = [r_{i1} r_{i2} \cdots] \quad (r_i \in Red)$$
$B$H$9$k$H$-(B, 
$$A=\left(
\begin{tabular}{ccc}
$f_1$ & $f_2$ & $\cdots$ \\
$r_{11}$ & $r_{12}$ & $\cdots$ \\
$r_{21}$ & $r_{22}$ & $\cdots$ \\
& $\cdots$ & \\
\end{tabular}
\right)$$
$B$H$J$i$Y(B, $B$3$l$r(B, $B9T$K4X$9$k4pK\JQ7A$K$h$j<!$N>r7o$rK~$?$99TNs(B
$B$ $B$KJQ7A$9$k(B. 

\begin{itemize}
\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))$
$B$r4^$^$J$$(B. 
\end{itemize}

$$B=\left(
\begin{tabular}{ccccccc}
1 & 0 & ? & ?        & ? & 0 & $\cdots$ \\
0 & 1 & ? & ?        & ? & 0 & $\cdots$ \\
0 & 0 & 0 & $\cdots$ & 0 & 1 & $\cdots$ \\
  &   &   & $\cdots$ &   &   &        \\
0 & 0 & 0 & $\cdots$ & 0 & 0 & $\cdots$ 
\end{tabular}
\right)$$
$B$3$N$H$-(B, 
$poly(B_i)$ $B$N$&$A(B, $HT(poly(B_i))$ $B$,(B $\{HT(r)\mid r\in Red\}$ $B$K(B
$B4^$^$l$J$$$b$N$,(B, $NF(f,G)$ $B$H$J$k(B. 

\subsection{$F_4$ $B%"%k%4%j%:%`(B}

$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
$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 
S-$BB?9`<0$r$^$H$a$F9TNs7A<0$G4JLs$9$k(B. $B$=$N$?$a$N(B symbolic preprocessing
$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
$B=R$Y$?%"%k%4%j%:%`$,$=$N$^$^E,MQ$5$l$k(B. 

\begin{al} (Symbolic preprocessing)
\label{multisymred}
\begin{tabbing}
Input : $BB?9`<0=89g(B $F$, $BB?9`<0=89g(B $G$\\
Output : $Red=\{ah \mid a :$ $BC19`<0(B, $h \in G \}$ \\

$T \leftarrow \cup_{f\in F}T(f)$ \\
$Red \leftarrow \emptyset$\\
while \= $HT(g)|t$ $B$J$k(B $t \in T$, $g \in G$ $B$,B8:_$9$k(B do \{\\
\>$Red \leftarrow Red \cup \{t/HT(g)\cdot g\}$\\
\>$T \leftarrow (T \setminus \{t\}) \cup T(reductum(t/HT(g)\cdot g)$\\
\}\\
return $Red$
\end{tabbing}
\end{al}
$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
$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
$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
$BJQ7A$9$k(B. 

\begin{itemize}
\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))$
$B$r4^$^$J$$(B. 
\end{itemize}
$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 
$B%0%l%V%J4pDl$r7W;;$7$?7k2L$KBP1~$9$k(B. 

$$F' = \{h=poly(B_i) \mid h\neq 0, HT(h)\notin \{HT(r)\mid r\in Red\}\}$$
$$Red' = \{h=poly(B_i) \mid h\neq 0, HT(h)\in \{HT(r)\mid r\in Red\}\}$$
$B$H$*$/(B. 
\begin{pr}
\begin{enumerate}
\item $h\in F'$ $B$O(B $G \cup (F'\setminus \{h\})$ $B$K4X$7$F@55,7A(B
\item $f\in F$ $B$J$i$P(B $f \tmred{G\cup F'} 0$
\end{enumerate}
\end{pr}
{\bf Proof}\\
1: $h\in F'$ $B$J$i$P(B $T(h) \cap \{HT(r)\mid r\in Red\} = \emptyset$. $B$3$l$O(B, 
$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. 
$B$b$A$m$s(B $h$ $B$O(B $F'\setminus \{h\}$ $B$K4X$7$F$b@55,7A$G$"$k(B. \\
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)$$
$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
$B@~7A6u4V$KB0$9$k(B. $B$3$3$G(B, 
$F\cup Red$ $B$H(B $F' \cup Red'$ $B$,(B $K$ $B>eF10l$N@~7A6u4V$r@8@.$7(B, 
$B$+$D(B $NF(f,G)$ $B$K$O(B $Red'$ $B$N85$NF,9`$O8=$l$J$$$+$i(B, 
$$NF(f,G)=\sum_{f_i\in F'} d_i f_i\quad (d_i \in K)$$
$B$H=q$1$k(B. 
$B$3$N@~7AOB$OD>$A$K(B $F'$ $B$K4X$9$k@55,7A7W;;$H$J$k(B. \qed\\
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, 
$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
$B$,(B 0 $B$K4JLs$5$l$k$3$H$,J,$+$k(B. $B$^$?(B, 1. $B$K$h$j(B, 
$B%"%k%4%j%:%`$NDd;_@-$b8@$($k(B. 
$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
$B$G$"$j(B, $B$=$N>l9g$K$O(B, $BA*$SJ}(B (selection strategy) $B$K$h$C$F8zN($K(B
$BBg$-$/:9$,$G$k$3$H$O4{$K=R$Y$?(B. $F_4$ $B$K$*$$$F$b(B $F$ $B$NA*$SJ}$,(B
$BLdBj$H$J$k$,(B, $BJ#?t85$rA*Br$G$-$k$3$H$G(B, selection strategy $B$N8zN($K(B
$BBP$9$k1F6A$,>/$J$/$J$k$3$H$,<B83$K$h$jCN$i$l$F$$$k(B. 

$BNc$($P(B, $B<!$N$h$&$J(B strategy $B$K$h$j(B, $BB?$/$NNc$,8zN($h$/7W;;$G$-$k(B. 

\begin{df}
S-$BB?9`<0$N(B sugar $B$N:G>.$N$b$N$rA4$FA*$V(B.
\end{df}
$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, 
$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
$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. 
$BFC$K(B, $BF~NOB?9`<0=89g$,(B homogeneous $B$N>l9g(B, $B$3$N(B strategy $B$K$h$j(B, 
$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
$B4pDl$N$&$A$N(B, $d$ $B<!$N85A4$F$H$J$k(B. $B$3$l$O(B, homogeneous ideal $B$N(B
$B>l9g<!$,@.$jN)$D$3$H$+$iJ,$+$k(B. 

\begin{enumerate}
\item $d$ $B<!$N4pDl$r@8@.$9$k$?$a$N(B S-$BB?9`<0$OA4$F(B $d-1$ $B<!0J2<$N(B
$B4pDl$+$i:n$i$l$k(B. 
\item $d$ $B<!$N@F<!B?9`<0$O(B, $d+1$ $B<!0J>e$N4pDl$G$O4JLs$5$l$J$$(B. 
\end{enumerate}

\subsection{Modular $B7W;;$K$h$k@~7AJ}Dx<0$N5a2r(B}

$F_4$ $B$K$*$$$F$O(B, selection strategy $B$K=>$C$F9=@.$5$l$?9TNs$r(B, 
$B:84pK\JQ7A$9$k$H$$$&A`:n$N7+$jJV$7$G4pDl$r@8@.$7$F$$$/(B. 
$B$3$3$G(B, $B:84pK\JQ7A$O(B, $B@~7AJ}Dx<05a2r$H$_$J$9$3$H$,$G$-$k(B. 
$B$9$J$o$A(B, 

\begin{enumerate}
\item $B9TNs(B $A$ $B$+$i@~7AFHN)$J9T$rA4$FH4$-$@$7$F(B $A'$ $B$r:n$k(B. 
\item $A'$ $B$NNs$r:8$+$i=g$K8+$F(B, $B$=$l$^$G<h$j=P$7$?Ns$H@~7AFHN)$J(B
$BNs$rH4$-=P$9(B, $B$H$$$&A`:n$r7+$jJV$7$F@5J}9TNs(B $A''$ $B$r:n$k(B. 
\item $A'$ $B$G;D$C$?Ns$r=8$a$F(B $B''$ $B$H$9$k(B. 
\item $A''X=B''$ $B$J$k@~7AJ}Dx<0$r2r$/(B. 
\item $X$ $B$+$i(B, $A'$ $B$N9T4pK\JQ7A$N7k2L$r9=@.$9$k(B. 
\end{enumerate}
$B85$NBN>e$G9M$($k8B$j(B, $B$3$l$OC1$J$k8@$$BX$($K2a$.$J$$$,(B, $BNc$($PM-M}?tBN(B
$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
$B$-$@$7(B, $A''X=B''$ $B$N2r8uJd$r(B modular $B7W;;$J$I$K$h$j9=@.$7(B, 

\begin{itemize}
\item $A$ $B$N3F9T$K(B, $BBh(B 5 $B9`$N7k2L$rBeF~$7$F(B 0 $B$K$J$k$3$H$r(B
$B3N$+$a$k(B. 
\end{itemize}
$B$H$$$&%A%'%C%/$K$h$j(B modular $B7W;;$N7k2L$,(B, $BM-M}?tBN>e$G$N9T4pK\(B
$BJQ7A$N7k2L$HEy$7$$$3$H(B, $BFC$K(B $A$ $B$r9=@.$9$kB?9`<0(B
$B$GD%$i$l$F$$$k$3$H(B, $B@~7AJ}Dx<0$N2r$N0l0U@-$K$h$j8@$($k(B. 
$B$3$N$h$&$J2r8uJd$rM?$($k$b$N$H$7$F(B, $BCf9q>jM>DjM}$*$h$S(B Hensel $B9=@.(B
$B$,$"$k(B. $BCf9q>jM>DjM}$rMQ$$$kJ}K!$O(B, $BK!(B $p$ $B$,M-M}?t>e$NA]$-=P$7$H(B
$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
$BJQ49$N7k2L$,(B stable $B$K$J$C$?$i(B $A$ $B$KBeF~$7$F%A%'%C%/$H$$$&J}K!$G$"$k(B. 
$B$^$?(B, Hensel $B9=@.$O(B $B%"%k%4%j%:%`(B \ref{lineq} $B$=$N$b$N$G$"$k(B. 
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
$B$,(B $A$ $B$N%5%$%:$r1[$($k>l9g$K$OCf9q>jM>DjM}$rMQ$$$?$[$&$,$h$$$H$N$3$H$G$"$k(B. 
$B$$$:$l$K$;$h(B, modular $B7W;;$K$h$kJ}K!$,8zN($r>e$2$k>l9g$H$$$&$N$O(B, 
$det(A'')$ $B$KHf$Y$F2r$N78?t$,>.$5$$>l9g$G$"$k(B. $B$3$l$O0lHL$K4|BT(B
$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$
$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
$B$7$?>l9g$K78?t$,>.$5$/$J$k$h$&$JLdBj$G$O(B modular $B7W;;$,8zN($r8~>e(B
$B$5$;$k$3$H$,4|BT$G$-$k(B. 

\subsection{$BNc(B}

\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
$B$r(B Buchberger $B%"%k%4%j%:%`$K$h$j9T$C$?(B. $B$3$N7W;;$K8=$l$kCf4V4pDl$K$*$$(B
$B$F(B, 16 $B<!$N4pDl$r@~7A7A<0$H$_$F(B, inter reduction $B$7$F$_$?7k2L(B, $B78?t$,(B
$B6KC<$K>.$5$/$J$k$3$H$,$o$+$k(B. $B$b$H$b$H(B, Buchberger $B%"%k%4%j%:%`$G(B odd
order $BJ}Dx<0$r7W;;$9$k>l9g(B, $B:G8e$K78?t$,BgJQ>.$5$$4pDl$,2?K\$+=P$F=*N;(B
$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
$B$b$N$G$"$C$?$?$a(B, $B$=$N4pDl$rMQ$$$F0l$DA0$N4pDl$r4JLs$7$?$H$3$m(B, $B78?t$,(B
$B>.$5$/$J$C$?(B. $B$=$NA`:n$r4pDlA4$F$KE,MQ$7$?$H$3$m(B, 16 $B<!$N4pDlA4$F$N78(B
$B?t$,(B, inter reduction $B$K$h$j>.$5$/$G$-$k$3$H$,J,$+$C$?$N$G$"$k(B.  $B4{$K(B
$B=R$Y$?$h$&$K(B, $B$3$N$h$&$J>l9g$K$O(B, modular $B7W;;$K$h$k2r8uJd$N7W;;$,M-8z(B
$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
$B$O$[$H$s$IJQ$o$i$:(B, $BBg$-$$$^$^$G$"$C$?(B. $B0J>e$N$h$&$JGX7J$N$b$H$K(B, $B8=:_(B
$B$N<BAu$G$N(B odd order $BJ}Dx<0$KBP$9$k(B Buchberger$B%"%k%4%j%:%`7W;;(B 
(homogenization+trace lifting) $B$*$h$S(B $F_4$ $B$NHf3S$r<($9(B. $BI=$G(B,
GaussElim, ChRem, IntRat, Check $B$O$=$l$>$l(B Gauss $B>C5n(B, $BCf9q>jM>DjM}(B, 
$B@0?t(B-$BM-M}?tJQ49(B, $B7k2L$N%A%'%C%/$K$+$+$C$?;~4V$r<($9(B.

\begin{table}[hbtp]
\caption{$B7W;;;~4V$NHf3S(B}
\begin{center}
\begin{tabular}{|c||c|c|c|c|c|} \hline
	& total & GaussElim & ChRem & IntRat& Check \\ \hline
Buchberger & 264710 & --- & ---	& ---	& ---	\\ \hline
$F_4$ homo 	& 32880 &  6437	& 6300	& 5763	& 13340	\\ \hline
$F_4$ non homo	& 39970	& 4832	& 6143	& 18240	& 9950	\\ \hline
\end{tabular}
\end{center}
\end{table}

\begin{table}[hbtp]
\caption{$B3F<!?t$N9TNs$N%5%$%:(B}
\begin{center}
\begin{tabular}{|c||c|c|c|c|c|c|} \hline
	& 10 & 11 & 12 & 13 & 14 & 15 \\ \hline
$F_4$ homo &(56,334) & (119,441) & (182,545) & (362,774) & (671,1009) & (1195,1359) \\ \hline
$F_4$ non homo &(62,339) & (128,448) & (137,461) & (227,571) & (307,621) & (955,1149) \\ \hline
\end{tabular}

\begin{tabular}{|c||c|c|c|c|c|c|} \hline
& 16 & 17 & 18 & 19 & 20 & 21 \\ \hline
$F_4$ homo &(836,688) &(2323,1761) &(895,964)  &(204,271) &(446,515) &(308,374) \\ \hline
$F_4$ non homo & (555,508) & (2022,1763) & --- & --- & --- & --- \\ \hline
\end{tabular}

\begin{tabular}{|c||c|c|c|c|} \hline
 & 22 & 23 & 24 & 25 \\ \hline
$F_4$ homo & --- & --- & --- & --- \\ \hline
$F_4$ non homo & (799,868)& (300,367) & (398,467) & (361,427) \\ \hline
\end{tabular}
\end{center}
\end{table}

\begin{table}[hbtp]
\caption{$B3F<!?t$N4pDl$N7W;;;~4V(B}
\begin{center}
\begin{tabular}{|c||c|c|c|c|c|c|} \hline
	& 10 & 11 & 12 & 13 & 14 & 15 \\ \hline
Buchberger & 2.3 & 11 & 43 & 164 & 1214 & 32512 \\ \hline
$F_4$ homo & 1.8 & 10 & 45 & 357 & 2574 & 26519\\ \hline
$F_4$ non homo & 2.2 & 12& 28 & 166& 1064 & 35906\\ \hline
\end{tabular}

\begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|} \hline
& 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 \\ \hline
Buchberger & 205234 & 10300 & 4530 & --- & 10700 & --- & --- & --- & --- & --- \\ \hline
$F_4$ homo & 1340 & 1097 & 359 & 45 & 208 & 150 & --- & --- & --- & --- \\ \hline
$F_4$ non homo & 937 & 902 & --- & --- & --- & --- & 341& 132 & 186 & 164 \\ \hline
\end{tabular}
\end{center}
\end{table}

\begin{figure}[htbp]
\epsfxsize=15cm
\epsffile{ps/blenall.ps}
\caption{$BCf4V4pDl$N:GBg78?t$N%S%C%HD9(B}
\label{nftime}
\end{figure}

$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
$B7W;;;~4V$NFbLu$r$_$l$P$o$+$k$h$&$K(B, Buchberger $B%"%k%4%j%:%`$K$h$k7W;;$G(B
$BA4BN$N7W;;;~4V$NBgItJ,$r@j$a$F$$$?(B 16 $B<!$N7W;;$,(B 1/100 $BDxEY$N;~4V$G=*$C$F(B
$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
$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
$BB?9`<0$K$h$k4JLs2=$G:Q$`$3$H$,9bB.2=$NM}M3$G$"$k(B. 

\subsection{$B$^$H$a(B}
$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
$BD9=j$r;}$D(B. 

\begin{itemize}
\item $B9TNs$NA]$-=P$7Cf$O(B, $B9`$N=g=xHf3S$,C1$J$k(B index $B$NHf3S$K$J$k(B. 
\item $BCf4V4pDl$r(B reduced $B$"$k$$$O$=$l$K6a$$7A$KJ]$D$?$a(B, $B$=$N8e$N(B
$BA]$-=P$77W;;$,8zN(2=$9$k(B. ($B!VBP3Q2=!W$5$l$?9TNs$K$h$k4JLs2=(B vs. $B!V;03Q2=!W(B
$B$5$l$?9TNs$K$h$k4JLs2=(B)
\item reduced $B$J4pDl$N78?t$,>.$5$/$J$k>l9g$K$O(B, modular $B7W;;$K$h$k(B
$B8zN(2=$,4|BT$G$-$k(B.

\end{itemize}
$B0lJ}$G(B, 

\begin{itemize}
\item $BB??t$N(B S-$BB?9`<0$*$h$S(B reducer $B$r0lEY$K9TNs$H$7$F07$&$?$a$K(B,
$B5pBg$J%a%b%j$rI,MW$H$9$k>l9g$,$7$P$7$P@8$:$k(B.
\item  $B0lHL$K9TNs$OAB$H$J$k$?$a(B, $BBg5,LOAB9TNs$r8zN($h$/J];}$7(B, $BA]$-=P$9I,MW(B
$B$,$"$k(B.
\item modular $B7W;;$r9T$&>l9g(B, $B9TNs$N3F9T$N(B 0 $B4JLs%A%'%C%/(B
$B$K$h$k%*!<%P!<%X%C%I$,LdBj$H$J$k(B.
\end{itemize}
$B$J$I$N:$Fq$K$h$j(B, $B<BMQE*$J<BAu$r9T$&$K$O(B Buchberger $B%"%k%4%j%:%`$HF1MM(B
$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
$BAu$G$b=>Mh$N(B Buchberger $B%"%k%4%j%:%`$h$j8zN($h$/7W;;$G$-$k>l9g$,$"$k$3(B
$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
$B4|BT$5$l$k(B.