Return to fglm.tex CVS log

Up to [local] / OpenXM / doc / compalg

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

1.1     ! noro        1: \chapter{Change of ordering}
        !             2:
        !             3: $BA0@a$G$O(B, $B<g$H$7$F(B Buchberger $B%"%k%4%j%:%`$N8zN(2=$K$D$$$F=R$Y$?(B.
        !             4: $B$7$+$7(B, $B%0%l%V%J4pDl$N7W;;K!$O(B Buchberger $B%"%k%4%j%:%`$@$1$H$O8B$i$J$$(B.
        !             5: $BK\@a$G$O(B, $B4{$K2?$i$+$N(B order $B$K4X$7$F%0%l%V%J4pDl$K$J$C$F$$$kB?9`<0(B
        !             6: $B=89g$rF~NO$H$7$F(B, $BB>$N(B order $B$N%0%l%V%J4pDl$r5a$a$kJ}K!$K$D$$$F=R$Y$k(B.
        !             7:
        !             8: \section{FGLM $B%"%k%4%j%:%`(B}
        !             9:
        !            10: $I \subset K[X]$ $B$r(B 0 $B<!85%$%G%"%k$H$7(B, $I$ $B$N$"$k(B order $<_1$ $B$K4X$9$k(B
        !            11: $BHoLs%0%l%V%J4pDl(B $G_1$ $B$,4{$KF@$i$l$F$$$k$H$9$k(B. $B$3$N$H$-(B, $BB>$N(B order $<$
        !            12: $B$K4X$9$k(B $I$ $B$N%0%l%V%J4pDl(B $G$ $B$r(B, $B<g$H$7$F@~7ABe?t$K$h$j5a$a$k$N$,(B FGLM
        !            13: $B%"%k%4%j%:%`$G$"$k(B.
        !            14:
        !            15: \begin{lm}
        !            16: $<$ $B$r(B admissible order, $F = GB_<(I)$ $B$H$9$k(B.
        !            17: $T = \{t_1,\cdots,t_l\} \subset T(X)$ $B$r9`$N=89g$H$9$k(B.
        !            18: $a_i$ $B$rL$Dj78?t$H$7(B,
        !            19: $$E = \displaystyle{\sum_{i=1}^l a_i NF_<(t_i,F)}$$
        !            20: $B$H$*$/(B. $E$ $B$N(B $X$ $B$K4X$9$k78?t$N=89g$r(B $C$ $B$H$9$l$P(B,
        !            21: $Eq = \{ f = 0 \mid f \in C\}$ $B$O(B $a_i$ $B$K4X$9$k@~7AJ}Dx<0$H$J$k(B. $B$3$N;~(B
        !            22: \begin{center}
        !            23: $Eq$ $B$,<+L@$G$J$$2r$r;}$D(B $\Leftrightarrow$ $T$ $B$,(B $K[X]/I$ $B$K$*$$$F(B
        !            24: $K$-$B@~7A=>B0(B
        !            25: \end{center}
        !            26: \end{lm}
        !            27:
        !            28: \begin{al} (FGLM $B%"%k%4%j%:%`(B\cite{FGLM})
        !            29: \label{fglm}
        !            30: \begin{tabbing}
        !            31: FGLM$(F,<_1,<)$\\
        !            32: Input : \= order $<_1$, $<$; $F \subset K[X]$ \st $F = GB_{<_1}(I)$ $B$+$D(B
        !            33: $\dim(I)=0$\\
        !            34: Output : $F$ $B$N(B $<$ $B$K4X$9$k%0%l%V%J4pDl(B\\
        !            35: ($C_2$)\= \kill
        !            36: $G \leftarrow \emptyset$\\
        !            37: $h \leftarrow 1$\\
        !            38: $B \leftarrow \{h\}$\\
        !            39: $H \leftarrow \emptyset$\\
        !            40: do \{\\
        !            41: \> $N \leftarrow \{u \mid u > h$ $B$+$D$9$Y$F$N(B $m \in H$ $B$KBP$7(B $m {\not|} u\}$\\
        !            42: (0)\> if $N = \emptyset$ then return $G$\\
        !            43: (1)\> $h_1 \leftarrow \min(N)$\\
        !            44: \> $a_t$ : $t \in B$ $B$KBP1~$9$kL$Dj78?t(B\\
        !            45: \> $a_{h_1} \leftarrow 1$\\
        !            46: (2)\> $E \leftarrow \displaystyle{NF_{<_1}(h_1,F)+\sum_{t \in B} a_t NF_{<_1}(t,F)}$\\
        !            47: \> $C \leftarrow$ $E$ $B$N(B $X$ $B$K4X$9$k78?t$N=89g(B\\
        !            48: \> if \= $B@~7AJ}Dx<0(B $\{ f = 0 \mid f \in C\}$ $B$,2r(B
        !            49:     $\{a_t = c_t \mid c_t \in K\}$ $B$r;}$D(B\\
        !            50: \> then \\
        !            51: \> \>$G \leftarrow G \cup \{\displaystyle{h_1+\sum_{t \in B} c_t t}\}$\\
        !            52: \> \>$H \leftarrow H \cup \{h_1\}$\\
        !            53: \> else $B \leftarrow \{h_1\} \cup B$\\
        !            54: \> $h \leftarrow h_1$\\
        !            55: \}\\
        !            56: \end{tabbing}
        !            57: \end{al}
        !            58:
        !            59: \begin{lm}
        !            60: \label{fglml1}
        !            61: (0) $B$K$*$$$F(B, $B= \{u \mid u \le h$ $B$+$D$9$Y$F$N(B $m \in H$ $B$KBP$7(B $m {\not|} u\}$.
        !            62: \end{lm}
        !            63: \proof $B%k!<%W$K4X$9$k5"G<K!$G<($9(B. $B:G=i$K%k!<%W$KF~$C$?;~E@$G$O(B
        !            64: $B@.N)$7$F$$$k(B. $B$"$k;~E@$G@.N)$7$F$$$k$H$9$k(B. $B$=$N;~E@$+$i%k!<%W$,0l2s(B
        !            65: $B2s$C$?;~E@$N(B (0) $B$K$*$$$F@.N)$9$k$3$H$r<($9(B.
        !            66: $B<($=$&$H$9$k;~E@$N0l$DA0$N;~E@$G$N(B $N$, $B$, $h$ $B$r(B $N_0$, $B_0$, $h_0$ $B$H=q$/(B.
        !            67: $h = \min(N_0)$ $B$G(B, $B = B_0 \cup \{h\}$ $B$^$?$O(B $H = H_0 \cup \{h\}$ $B$G$"$k(B. \\
        !            68: \underline{$B = B_0 \cup \{h\}$ $B$N;~(B}\, $H = H_0$ $B$h$j(B,
        !            69: $B1&JU(B $= B_0 \cup \{u \mid$ $h_0 < u \le h$ $B$+$D$9$Y$F$N(B $m \in H_0$ $B$K(B
        !            70: $BBP$7(B $m{\not|} u\}= B_0 \cup \{h\}$.\\
        !            71: \underline{$H = H_0 \cup \{h\}$ $B$N;~(B}\,
        !            72: $B1&JU(B $= B_0 \cup
        !            73: (\{u \mid h_0 < u \le h$ $B$+$D$9$Y$F$N(B $m \in H_0$ $B$KBP$7(B $m {\not|} u\}
        !            74: \cap \{u \mid h {\not|} u \}) = B_0 \cup (\{h\} \cap \{u \mid h {\not|} u \}) = B_0$.\\
        !            75: $B$h$C$F(B, $B$$$:$l$N>l9g$K$b1&JU(B = $B$ $B$H$J$k(B. \qed
        !            76:
        !            77: \begin{lm}
        !            78: \label{fglml2}
        !            79: (1) $B$K$*$$$F(B, $h_1 \in x_1B \cup \cdots \cup x_nB$.
        !            80: \end{lm}
        !            81: \proof $h_1>1$ $B$h$j$"$k(B $k$ $B$,B8:_$7$F(B $h_1=x_kh'$ $B$H=q$1$k(B.
        !            82: $B$b$7(B $h' \in N$ $B$J$i$P(B $h_1 = \min(N)$ $B$KH?$9$k$+$i(B $h' \in B$. \qed
        !            83:
        !            84: \begin{pr}
        !            85: $B%"%k%4%j%:%`(B \ref{fglm} $B$O(B $GB_<(F)$ $B$r=PNO$9$k(B.
        !            86: \end{pr}
        !            87: \proof $BJdBj(B \ref{fglml2}$B$h$j(B, (1) $B$K$*$1$k(B $h$ $B$N8uJd$O(B $BM-8B=89g(B
        !            88: $x_1B \cup \cdots \cup x_nB$ $B$N85$@$+$i(B $\min(N)$ $B$rM?$($kA*Br%"%k%4%j(B
        !            89: $B%:%`$,B8:_$9$k(B. \\
        !            90: \underline{$BDd;_@-(B} $B$^$:(B, (2) $B$,2r$r;}$?$J$$$3$H$H(B, $\{h_1\} \cup B$ $B$,(B
        !            91: $K[X]/I$ $B$G(B $K$ $B>e0l<!FHN)$G$"$k$3$H$,F1CM$G$"$k$3$H$KCm0U$9$k(B. $B$h$C$F(B,
        !            92: $|B|$ $B$O(B$\dim_K K[X]/I$ $B$r1[$($i$l$J$$(B. $B$^$?(B, $H$ $B$N85$O(B, $B$I$N85$bB>$N(B
        !            93: $B85$r3d$i$J$$$+$i(B, $B7O(B \ref{noether} $B$h$j$d$O$jM-8B=89g(B. $B$h$C$F%"%k%4%j(B
        !            94: $B%:%`$ODd;_$9$k(B.\\
        !            95: \underline{$G = GB_<(F)$} $f \in I$ $B$H$7(B, $t=HT_<(F)$ $B$H$9$k(B.
        !            96: $f$ $B$O(B $G$ $B$K4X$7$FHoLs$H$7$F$h$$(B. $H = \{h_1,\cdots,h_m\}$ \quad
        !            97: ($h_1<\cdots<h_m$) $B$H$9$k(B. $B$^$?(B, $(1)$ $B$K$h$jA*Br$5$l$k85$r=g$KJB$Y$?(B
        !            98: $B$b$N$r(B $t_1<t_2<\cdots$$B$H$9$k(B. $B$b$7(B, $B$9$Y$F$N(B $h \in H$ $B$KBP$7(B $h
        !            99: {\not|} t$ $B$J$i$P(B, $BDd;_$N>r7o$h$j$"$k(B $k$$B$,$"$C$F(B, $t_k<t\le t_{k+1}$.
        !           100: $B2>Dj$K$h$j(B, $k+1$ $BHVL\$KA*$P$l$k85$O(B$t$ $B$G$J$1$l$P$J$i$J$$$+$i(B
        !           101: $t=t_{k+1}$. $t' \in T(f) \setminus \{t\}$$B$H$9$l$P(B, $t'<t$ $B$+$DA4$F$N(B
        !           102: $h \in H$ $B$KBP$7(B $h {\not|} t'$. $B$3$l$h$j(B$t' \le t_k$. $B$h$C$FJdBj(B
        !           103: \ref{fglml1} $B$h$j(B $t=t_{k+1}$ $B$,A*Br$5$l$F$$$k;~E@$G(B $t'\in B$.  $B$h$C(B
        !           104: $B$F$3$N;~E@$G(B $f$ $B$O@~7AJ}Dx<0$N2r$H$J$j(B, $t\in H$ $B$H$J$k$,$3$l$OL7=b(B.\qed
        !           105:
        !           106: FGLM $B%"%k%4%j%:%`$r7W;;5!>e$G<BAu$9$k>l9g(B, $BFC$K(B (2)$B$NItJ,$N<BAu$K(B
        !           107: $B9)IW$,I,MW$H$J$k(B. $BMWE@$r$^$H$a$k$H(B,
        !           108:
        !           109: \begin{enumerate}
        !           110: \item $B@55,7A$N7W;;$O(B, $B3F9`$K$D$-$?$@0lEY$@$19T$$(B, $B7k2L$OI=$K$7$FJ];}$9$k(B.
        !           111: \item $BKh2sFHN)$J@~7AJ}Dx<0$H$7$F2r$/$N$G$O$J$/(B, $B7k2L$,8e$G;H$($k$h$&$J(B
        !           112: $B9)IW$r$9$k(B.
        !           113: \end{enumerate}
        !           114:
        !           115: 1. $B$K4XO"$7$F(B, $B<!$N$h$&$J@~7A<LA|$r9M$($k$3$H$G(B, $B@55,7A7W;;$N8zN($r>e(B
        !           116: $B$2$k$3$H$,$G$-$k(B.
        !           117:
        !           118: \begin{df}
        !           119: $B3F(B $i (1\le i\le n)$ $B$KBP$7(B, $\phi_i \in End(K[X]/I)$ $B$r(B
        !           120: $$\phi_i : f \bmod I \mapsto x_if \bmod I$$
        !           121: $B$GDj5A$9$k(B. $H_1 = \{HT_{<_1}(g)\mid g \in G_1\}$,
        !           122: $MB_1 = \{u \in T \mid$  $B$9$Y$F$N(B $m \in H_1$ $B$KBP$7(B $m {\not|} u\}$
        !           123: $B$H$*$1$P(B $MB_1$ $B$O(B $K[X]/I$ $B$N(B $K$-$B4pDl$h$j(B,
        !           124: $\{NF_{<_1}(x_iu,G_1)\mid u \in MB_1\}$ $B$rA4$F7W;;$9$k$3$H$G(B,
        !           125: $\phi_i$ $B$,I=8=$G$-$k(B.
        !           126: \end{df}
        !           127:
        !           128: $B$"$i$+$8$a(B, $\phi_i$ $B$r7W;;$7$F$*$1$P(B, $NF(x_it,G_1) = \phi_i(NF(t,G_1))$
        !           129: $B$h$j(B, $B4{$KF@$i$l$F$$$k$O$:$N(B $NF(t,G_1)$ $B$NA|$H$7$F$"$i$?$J9`$N@55,7A$,(B
        !           130: $B7W;;$G$-$k(B.
        !           131:
        !           132: \begin{re}
        !           133: $B0lHL$K$O(B, FGLM $B%"%k%4%j%:%`$O(B 0 $B<!85%$%G%"%k$N>l9g$K$N$_E,MQ2DG=$@$,(B,
        !           134: $BL\E*$N(B order $B$,A4<!?tHf3S$r4^$`>l9g$J$I(B, $BG$0U$N(B $s \in T$ $B$KBP$7(B
        !           135: $\{t \in T \mid t < s\}$ $B$,M-8B=89g$N>l9g$K$O(B, $BG$0U$N%$%G%"%k$KE,MQ$G$-$k(B.
        !           136: $B$7$+$7(B, $B8zN($O0lHL$K(B 0 $B<!85$N>l9g$KHf$Y$F4|BT$G$-$J$$(B.
        !           137: \end{re}
        !           138:
        !           139: \section{Modular change of ordering}
        !           140:
        !           141: FGLM $B$O(B, $BL\E*$N9`$KE~C#$9$k$^$G9TNs$N(B Gauss $B>C5n$r7+$jJV$9J}K!$H$$$($k(B.
        !           142: $B$3$N(B Gauss $B>C5n$OM-M}?tBN>e$G9T$J$o$l$k$?$a(B, $B7k2L$N%0%l%V%J4pDl$N85$N(B
        !           143: $B78?t$KHf$Y$FESCf$N78?tKDD%$,7c$7$/$J$k>l9g$,$7$P$7$P@8$:$k(B. $B$3$l$O(B,
        !           144: $B<!$NNc$G<($5$l$k(B.
        !           145:
        !           146: \begin{ex}
        !           147: $A \in GL(n,\Q)$ $B$H$9$k(B. $V \in \Q^n$ $B$KBP$7(B $B=AV$ $B$H$9$k$H(B,
        !           148: $B@~7AJ}Dx<0(B $AX = B$ $B$O(B $X = V$ $B$rM#0l$N2r$H$9$k(B. $B$3$NJ}Dx<0(B
        !           149: $B$r(B Gauss $B>C5n$G2r$/>l9g(B, $B$=$l$O(B $A$ $B$K$N$_CmL\$7$F9T$J$o$l(B,
        !           150: $B$ $B$NCM$K:81&$5$l$J$$(B. $B$9$J$o$A(B, $B2r(B $V$ $B$N@.J,$,>.$5$$@0?t(B
        !           151: $B$N>l9g$G$bBg$-$$>l9g$G$b2r$/<j4V$OJQ$o$i$J$$$3$H$K$J$k(B.
        !           152: \end{ex}
        !           153:
        !           154: \subsection{Modular $B7W;;$H@~7ABe?t$K$h$k%0%l%V%J4pDl8uJd@8@.(B}
        !           155: $B$3$3$G>R2p$9$k%"%k%4%j%:%`$O(B, modular $B7W;;$r1~MQ$7$F(B, $B7k2L$N78?t$NBg$-(B
        !           156: $B$5$NDxEY$N%3%9%H$G%0%l%V%J4pDl$r7W;;$9$k$b$N$G$"$k(B\cite{NY}\cite{NY2}.
        !           157: $B%"%k%4%j%:%`(B \ref{mfglm} $B$G$O(B, $BM-8BBN>e$N%0%l%V%J4pDl7W;;$K$h$j(B, $BM-M}(B
        !           158: $B?tBN>e$N%0%l%V%J4pDl$N3F85$K8=$l$k9`$r?dB,$7(B, $BL$Dj78?tK!$G(B, $B$=$l$i$N9`(B
        !           159: $B$r<B:]$K$b$D(B $I=Id(F)$ $B$N85$r5a$a$k(B.
        !           160:
        !           161: \begin{al}
        !           162: \label{mfglm}
        !           163: \begin{tabbing}
        !           164: \\
        !           165: candidate\_by\_linear\_algebra$(F,p,<_1,<)$\\
        !           166: Input : \= order $<_1$, $<$\\
        !           167: \> $F \subset \Z[X]$ \st $F = GB_{<_1}(Id(F))$\\
        !           168: \> $F$ $B$N3F85$N(B $<_1$ $B$K4X$9$k<g78?t$r3d$i$J$$(B $p$ \\
        !           169: Output : $F$ $B$N(B $<$ $B$K4X$9$k%0%l%V%J4pDl8uJd$^$?$O(B {\bf nil}\\
        !           170: ($C_2$)\= \kill
        !           171: $\overline{G} \leftarrow$ $GB_<(Id(\phi_p(F)))$ ($BHoLs%0%l%V%J4pDl(B) \\
        !           172: $G \leftarrow \emptyset$\\
        !           173: for \= each $h \in \overline{G}$ do \{\\
        !           174: \> $a_t$ : $t \in T(h)$ $B$KBP1~$9$kL$Dj78?t(B\\
        !           175: \> $a_t \leftarrow 1$ ($t = ht_{<}(h)$ $B$KBP$7$F(B)\\
        !           176: \> $H \leftarrow \displaystyle{\sum_{t \in T(h)} a_t NF_{<_1}(t,F)}$\\
        !           177: \> $C \leftarrow$ $H$ $B$N(B $X$ $B$K4X$9$k78?t$N=89g(B\\
        !           178: \> if \= $B@~7AJ}Dx<0(B $E_h = \{ f = 0 \mid f \in C\}$ $B$,2r(B
        !           179:     $S_h = \{a_t = c_t \mid c_t \in \Q\}$ $B$r;}$D(B\\
        !           180: \> then $G \leftarrow G \cup \{\displaystyle{d\sum_{t \in T(h)} c_t t}\}$\\
        !           181: \> {\rm ($d$ : $c_t$ $B$NJ,Jl$N(B LCM)}\\
        !           182: \> else return {\bf nil}\\
        !           183: \}\\
        !           184: return $G$
        !           185: \end{tabbing}
        !           186: \end{al}
        !           187:
        !           188: \begin{pr}
        !           189: $B%"%k%4%j%:%`(B \ref{mfglm} $B$O(B, $BM-8B8D$N(B $p$ $B$r=|$$$F(B $GB_<(F)$ $B$r(B
        !           190: $BM?$($k(B.
        !           191: \end{pr}
        !           192: \proof trace lifting $B$N>l9g$HF1MM$K(B, $BM-8BBN>e$G$N%0%l%V%J4pDl$N3F(B
        !           193: $B85$K8=$l$k9`$,(B, $BM-M}?tBN>e$G$N$=$l$H0lCW$7$F$$$l$P(B, $BA4$F$N@~7AJ}Dx<0$O(B
        !           194: $B2r$r;}$A(B, $G = GB_<(F)$ $B$H$J$k(B. $B$=$&$G$J$$(B $p$ $B$OM-8B8D$7$+$J$$$?$a(B,
        !           195: $B$=$l$i$r=|$$$F$O(B, $B$3$N%"%k%4%j%:%`$O(B $GB_<(F)$ $B$rM?$($k(B. \qed
        !           196:
        !           197: \begin{re}
        !           198: $B@~7AJ}Dx<0$,A4It2r$1$?$H$7$F$b(B, $B7k2L$,(B $Id(F)$ $B$N%0%l%V%J4pDl$K$J$C$F(B
        !           199: $B$$$kJ]>Z$O8=;~E@$G$O$J$$$N$G(B, $B$3$NL?Bj$OIT==J,$G$"$k(B. $B<B$O(B, $B<!$G=R$Y$k(B
        !           200: $B7k2L$K$h$j(B, $B%"%k%4%j%:%`(B \ref{mfglm} $B$,(B {\bf nil} $B$G$J$$B?9`<0=89g$r(B
        !           201: $BJV$;$P(B, $B$=$l$O$?$@$A$K(B $Id(F)$ $B$N%0%l%V%J4pDl$H$J$C$F$$$k$3$H$,J,$+$k(B.
        !           202: $B$3$l$K$D$$$F$O(B, $B@~7AJ}Dx<0$N(B, $B7k2L$NBg$-$5$K1~$8$?7W;;NL$rI,MW$H$9$k(B
        !           203: $B5a2rK!$H$H$b$K(B, $B8e$G=R$Y$k(B.
        !           204: \end{re}
        !           205:
        !           206: \subsection{$B%0%l%V%J4pDl8uJd$,%0%l%V%J4pDl$H$J$k>r7o(B}
        !           207: $B$3$3$G$O(B, change of ordering $B$N>l9g$K$O(B,
        !           208: trace lifting $B$N>l9g$KI,MW$@$C$?%0%l%V%J4pDl%F%9%H$H%a%s%P%7%C%W%F%9%H(B
        !           209: $B$,ITI,MW$K$J$k$3$H$r<($9(B. $F \subset \Z[X]$ $B$H$9$k(B.
        !           210:
        !           211: \begin{as}
        !           212: \label{nf}
        !           213: $BM-M}?tBN>e$HM-8BBN>e$N7W;;$,0[$i$J$$$h$&<!$N2>Dj$r$*$/(B.
        !           214: \begin{enumerate}
        !           215: \item $BITI,MWBP$N8!=P4p=`$OF,9`$N$_$G9T$&(B.
        !           216: \item $B@55,7A7W;;$K$*$$$F(B, $B@55,2=$KMQ$$$k85(B (reducer) $B$NA*Br$O(B, $B@55,2=$5$l$k(B
        !           217: $BB?9`<0$N9`$*$h$S(B reducer $B$NF,9`$N=89g$K$N$_0MB8$9$k(B.
        !           218: \end{enumerate}
        !           219: \end{as}
        !           220:
        !           221: \begin{df}
        !           222: {\rm (compatibile $B$JAG?t(B)}
        !           223: $BAG?t(B $p$ $B$,(B $F$ $B$K4X$7(B compatible $B$H$O(B,
        !           224: $$\phi_p(Id(F)\cap\Z[X]) (=\phi_p(Id(F)\cap\Z_{(p)}[X])) = Id(\phi_p(F))$$
        !           225: $B$J$k$3$H(B.
        !           226: \end{df}
        !           227:
        !           228: \begin{df}
        !           229: $BAG?t(B $p$ $B$,(B $(F,<)$ $B$K4X$7$F(B strongly compatible $B$H$O(B
        !           230: $p$ $B$,(B $F$ $B$K4X$7$F(B compatible $B$G(B
        !           231: $$E_<(Id(F)) = E_<(Id(\phi_p(F))$$
        !           232: $B$J$k$3$H(B.
        !           233: \end{df}
        !           234:
        !           235: \begin{df}(permissible $B$JAG?t(B)
        !           236: $BAG?t(B $p$ $B$,(B $(F,<)$ $B$K$D$$$F(B permissible $B$H$O(B
        !           237: $B3F(B $f \in F$ $B$KBP$7(B \valid{p}{f}{<} $B$J$k$3$H(B.
        !           238: \end{df}
        !           239:
        !           240: \begin{df}
        !           241: $f \in \Q[X]$ $B$,(B $p$ $B$K4X$7(B stable $B$H$O(B $f \in \Z_{(p)}[X]$ $B$J$k$3$H(B.
        !           242: \end{df}
        !           243:
        !           244: \begin{df}
        !           245: {\rm (modular $B%0%l%V%J4pDl$N5UA|(B)}
        !           246: $G \subset Id(F)\cap \Z[X]$ $B$,(B $F$ $B$N(B $<$ $B$K4X$9$k(B
        !           247: $p$-compatible $B$J%0%l%V%J4pDl8uJd$H$O(B
        !           248: $p$ $B$,(B $(G,<)$ $B$K$D$$$F(B permissible $B$G(B $\phi_p(G)$ $B$,(B$Id(\phi_p(F))$ $B$N(B $<$
        !           249: $B$K4X$9$k%0%l%V%J4pDl$J$k$H$-$r$$$&(B.
        !           250: \end{df}
        !           251:
        !           252: \begin{re}
        !           253: compatibility $B$O(B order $B$KFHN)$J35G0$G$"$k(B.
        !           254: \end{re}
        !           255:
        !           256: \begin{lm}
        !           257: \label{valid}
        !           258: $G \subset \Z[X]$, $p$ $B$r(B $(G,<)$ $B$K$D$$$F(B permissible $B$JAG?t(B,
        !           259: $f \in \Z[X]$ $B$H$9$k(B. $B$3$N$H$-(B
        !           260: $B2>Dj(B \ref{nf} $B$N$b$H$G(B
        !           261: $$NF(\phi_p(f),\phi_p(G)) = \phi_p(NF(f,G)).$$
        !           262: \end{lm}
        !           263: \proof $NF(f,G)$ $B$O<!$N(B recurrence $B$G7W;;$5$l$k(B.
        !           264: $$f_0 \leftarrow f,
        !           265: f_i \leftarrow f_{i-1} - \alpha_i t_i g_{k_i}$$
        !           266: $B$3$3$G(B, $\alpha_i\in {\bf \Q}$, $t_i$ : a term, $g_{k_i}\in G$.
        !           267: $B$9$k$H(B, $p$ $B$,(B $(G,<)$ $B$KBP$7$F(B permissible $B$h$j(B $\alpha_i \in \Z_{(p)}$.
        !           268: $B$h$C$F(B $BA4$F$N(B $i$ $B$KBP$7(B $f_i \in \Z_{(p)}[X]$ $B$G(B, $B$3$N(B recurrence $B$K(B
        !           269: $\phi_p$ $B$rE,MQ$7$F<!$rF@$k(B.
        !           270: $$\phi_p(f_i) = \phi_p(f_{i-1}) - \phi_p(\alpha_i) t_i \phi_p(g_{k_i}).$$
        !           271: $B$b$7(B $\phi_p(\alpha_i) \neq 0$ $B$J$i$P(B $\phi_p(f_{i-1}) \neq 0$ $B$G(B,
        !           272: $$\phi_p(f_i) \leftarrow \phi_p(f_{i-1}) - \phi_p(\alpha_i) t_i \phi_p(g_{k_i})$$
        !           273: $B$O(B $\phi_p(G)$ $B$K$h$kF,9`>C5n$G$"$k(B.
        !           274: $B$b$7(B $\phi_p(\alpha_i) = 0$ $B$J$i$P(B $\phi_p(f_i) = \phi_p(f_{i-1})$ $B$G(B
        !           275: $$\{\phi_p(f_i)\mid i=0\, {\rm or}\, \phi_p(\alpha_i)\neq 0\}$$
        !           276: $B$J$kNs$O(B
        !           277: $NF(\phi_p(f),\phi_p(G))$ $B$N7W;;$KBP1~$9$k(B.
        !           278: $B$b$7(B$\phi_p(f_i) = 0$ $B$J$k(B $i$ $B$,B8:_$9$l$PA|$OESCf$G@Z$l$k$,(B
        !           279: $$NF(\phi_p(f),\phi_p(G)) = \phi_p(NF(f,G)) = 0$$
        !           280: $B$@$+$i<gD%$,@.N)$9$k(B.
        !           281: \qed
        !           282: \medskip
        !           283:
        !           284: \begin{th}
        !           285: \label{comp}
        !           286: $G \subset Id(F)\cap\Z[X]$ $B$r(B $Id(F)$ $B$N(B $<$ $B$K4X$9$k%0%l%V%J4pDl$H$9$k(B.
        !           287: $B$b$7(B $p$ $B$,(B $(G,<)$ $B$K4X$7$F(B permissible $B$+$D(B
        !           288: $\phi_p(G) \subset Id(\phi_p(F))$ $B$J$i$P(B $p$ $B$O(B $F$ $B$K4X$7$F(B compatible $B$G$"$k(B.
        !           289: $B99$K(B, $\phi_p(G)$ $B$O(B $Id(\phi_p(F))$ $B$N%0%l%V%J4pDl$G(B
        !           290: $p$ $B$O(B $(F,<)$ $B$K$D$$$F(B strongly compatible $B$G$"$k(B.
        !           291: \end{th}
        !           292: \proof
        !           293: $h \in Id(F) \cap \Z[X]$ $B$H$9$k(B. $G$ $B$,(B $Id(F)$ $B$N%0%l%V%J4pDl$@$+$i(B,
        !           294: $NF(h,G)=0$ $B$h$j(B $h = \sum_{g\in G} a_g g$ $B$H=q$1$k(B. $B$3$3$G(B $a_g \in \Q[X]$.
        !           295: $B99$K(B $p$ $B$,(B $(G,<)$ $B$K$D$$$F(B permissible $B$h$j(B,
        !           296: $a_g$ $B$O(B $p$ $B$K$D$$$F(B stable $B$G(B, $B2>Dj(B $\phi_p(g)\in Id(\phi_d(F))$ $B$h$j(B
        !           297: $$\phi_p(h)=\sum_{g\in G} \phi_p(a_g) \phi_p(g).$$
        !           298: $B$h$C$F(B $\phi_p(h)\in Id(\phi_p(F))$.
        !           299: $B8N$K(B $\phi_p(Id(F)\cap \Z[X])\subset Id(\phi_p(F))$. \\
        !           300: $B5U$K(B $\overline{h} \in Id(\phi_p(F))$ $B$O(B
        !           301: $$\overline{h} = \sum_{f\in F} \overline{a}_f \phi_p(f)$$
        !           302: $B$H=q$1$k(B. $B$3$3$G(B $\overline{a}_f \in GF(p)[X]$.
        !           303: $B$9$k$H(B, $\phi_p(a_f)=\overline{a}_f$ $B$J$k(B $a_f$ $B$rA*$s$G(B
        !           304: $h=\sum_{f\in F} a_f f$ $B$H$*$1$P(B $\phi_p(h)=\overline{h}$.
        !           305: $B$3$l$+$i(B $\phi_p(Id(F)\cap \Z[X])=Id(\phi_p(F))$. \\
        !           306: $B:G8e$K(B $\phi(G)$ $B$,(B $Id(\phi_p(F))$ $B$N%0%l%V%J4pDl$H$J$k$3$H$r<($9(B.
        !           307: $B>e$G=R$Y$?$3$H$+$i(B,
        !           308: $\overline{h} \in Id(\phi_p(F))$ $B$KBP$7(B,
        !           309: $h \in Id(F)\cap \Z[X]$ $B$,B8:_$7$F(B $\overline{h}=\phi_p(h)$.
        !           310: $B$9$k$H(B, $BJdBj(B \ref{valid} $B$h$j(B
        !           311: $$NF(\overline{h},\phi_p(G))=\phi_p(NF(h,G))=0.$$
        !           312: $B=>$C$F(B, $\phi_p(G)$ $B$O(B $Id(\phi_p(F))$ $B$N%0%l%V%J4pDl(B.
        !           313: strong compatibility $B$O(B $E_<(Id(F))$ $B$,(B $E_<(G)$
        !           314: $B$G@8@.$5$l$k$3$H$+$iJ,$+$k(B.
        !           315: \qed \\
        !           316: $B$3$NDjM}$G(B, $\phi_p(G) \subset Id(\phi_p(F))$ $B$O(B
        !           317: $Id(\phi_p(F))$ $B$N%0%l%V%J4pDl$K$h$j%A%'%C%/$G$-$k(B.
        !           318: $B$h$C$F(B, $p$ $B$N(B compatibility $B$N%A%'%C%/$OM-M}?tBN>e(B, $BM-8BBN>e$N(B
        !           319: $BG$0U$N(B order $B$G$N%0%l%V%J4pDl$r7W;;$9$k$3$H$G9T$&$3$H$,$G$-$k(B.
        !           320: $B$b$7(B, $BF~NO$,4{$K$"$k(B order $B$G$N%0%l%V%J4pDl$J$i(B compatibility $B$N%A%'%C%/(B
        !           321: $B$O6K$a$F4JC1$G$"$k(B.
        !           322:
        !           323: \begin{co}
        !           324: \label{compco}
        !           325: $G \subset \Z[X]$ $B$,(B $<$ $B$K4X$9$k(B $Id(G)$ $B$N%0%l%V%J4pDl$H$9$k(B.
        !           326: $B$b$7(B $p$ $B$,(B $(G,<)$ $B$KBP$7(B permissible $B$J$i$P(B
        !           327: $\phi_p(G)$ $B$O(B $Id(\phi_p(G))$ $B$N%0%l%V%J4pDl$G(B
        !           328: $p$ $B$O(B $(G,<)$ $B$KBP$7(B strongly compatible.
        !           329: \end{co}
        !           330: $B<!$NDjM}$O(B, $B%0%l%V%J4pDl8uJd$,<B:]$K%0%l%V%J4pDl$K$J$k$?$a$N==J,>r7o$rM?$($k(B.
        !           331: $B$9$J$o$A(B, $B2f!9$,5a$a$k$b$N$G$"$k(B.
        !           332:
        !           333: \begin{th}
        !           334: \label{candi}
        !           335: $p$ $B$,(B $F$ $B$K$D$$$F(B compatible $B$G(B $G$ $B$,(B $<$ $B$K4X$7$F(B $p$-compatible $B$J%0%l%V%J(B
        !           336: $B4pDl8uJd$J$i$P(B, $G$ $B$O(B $<$ $B$K4X$9$k(B $Id(F)$ $B$N%0%l%V%J4pDl$G$"$k(B.
        !           337: \end{th}
        !           338: \proof $BA4$F$N(B $f \in Id(F)$ $B$,(B $<$ $B$K4X$7$F(B $G$ $B$K$h$j(B 0 $B$K@55,2=(B
        !           339: $B$5$l$k$3$H$r<($;$P$h$$(B. $f$ $B$O(B $G$ $B$K$D$$$FHoLs$H$7$F$h$$(B. $B$b$7(B $f
        !           340: \neq 0$ $B$J$i$P(B, $BE,Ev$JM-M}?t$r$+$1$F(B, $f \in Id(F)\backslash \{0\}$ $B$,(B
        !           341: $G$ $B$K$D$$$FHoLs$G(B $f$ $B$N78?t$N@0?t(B GCD ($cont(f)$ $B$H=q$/(B) $B$,(B 1 $B$KEy$7(B
        !           342: $B$$(B, $B$H$7$F$h$$(B. $B$9$k$H(B $\phi_p(f) \neq 0$. $B$5$b$J$/$P(B
        !           343: $cont(f)$ $B$O0x;R(B $p$ $B$r;}$D$3$H$K$J$k(B.
        !           344: $p$ $B$O(B $F$ $B$K$D$-(B compatible $B$@$+$i(B $\phi_p(f) \in Id(\phi_p(F))$.
        !           345: $B$9$k$H(B $\phi_p(f)$ $B$O(B $<$ $B$K4X$7(B, $\phi_p(G)$ $B$K$h$j(B 0 $B$K@55,2=$5$l$J$1$l$P(B
        !           346: $B$J$i$J$$(B. $B$7$+$7(B $f$ $B$O(B $G$ $B$K$D$$$FHoLs$@$+$i(B
        !           347: $\phi_p(G)$ $B$NF,9`$N=89g$O(B $G$ $B$N$=$l$HEy$7$$(B. $B$h$C$F(B
        !           348: $\phi_p(f)$ $B$O(B $\phi_p(G)$ $B$K$D$$$FHoLs$H$J$j(B, $\phi_p(f) = 0$. $B$3$l$O(B
        !           349: $BL7=b(B. \qed
        !           350: \medskip
        !           351: $B<!$NDjM}$OA0DjM}$N@:L)2=$G$"$k(B. $B$9$J$o$A(B, $B>:=g$K7W;;$5$l$?ItJ,E*$J(B
        !           352: $p$-compatible $B$J%0%l%V%J4pDl8uJd$,<B:]$K%0%l%V%J4pDl$N0lIt$H$J$C$F(B
        !           353: $B$$$k$3$H$rJ]>Z$9$k(B. $B$3$l$O(B, $BESCf$^$G$N7k2L$r:FMxMQ$G$-$k$H$$$&E@$G(B
        !           354: $BM-MQ$G$"$k(B. $B$^$?(B, $B8e$G=R$Y$k$h$&$K(B, $B%0%l%V%J4pDl$N$"$kFCDj$N85(B,
        !           355: $BNc$($P(B, $B=g=x:G>.$N85$N$_$r5a$a$?$$(B, $B$"$k$$$O(B elimination $B8e$N7k2L$N$_(B
        !           356: $B$r5a$a$?$$>l9g$K$bM-MQ$G$"$k(B.
        !           357:
        !           358: \begin{th}
        !           359: $p$ $B$,(B $F$ $B$K$D$$$F(B compatible $B$H$9$k(B.
        !           360: $\overline{G}\subset GF(p)[X], \overline{G} = GB_<(Id(\phi_p(F))$ $B$H$7(B
        !           361: $\overline{g}_1<\cdots<\overline{g}_s$ $B$J$k(B $\overline{g}_i$ $B$K$h$j(B
        !           362: $\overline{G}=\{\overline{g}_1,\cdots,\overline{g}_s\}$ $B$H=q$/(B.
        !           363: $B99$K(B, $B$"$k@5?t(B $t\leq s$ $B$KBP$7(B,
        !           364: $g_i \in Id(F) \cap \Z_{(p)}[X]$ ($1 \le i \le t$) $B$,B8:_$7$F(B
        !           365: $\phi_p(g_i) = \overline{g}_i$ $B$+$D(B $g_i$ $B$O(B $\{g_1,\cdots,g_{i-1}\}$ $B$K$D$$$F(B
        !           366: $BHoLs$H$9$k(B.
        !           367: $B$3$N$H$-(B, $g_1,\cdots,g_t$ $B$O(B $GB_<(Id(F))$ $B$N:G=i$N(B $t$ $B8D$N85$K0lCW$9$k(B.
        !           368: \end{th}
        !           369: $B>ZL@N,(B ($B5"G<K!$K$h$k(B.)\\
        !           370: $B0J>e=R$Y$?$3$H$K$h$j(B, $B<!$N$h$&$J0lHLE*$J(B change of ordering $B%"%k%4%j%:%`(B
        !           371: $B$,F@$i$l$k(B.
        !           372:
        !           373: \begin{pro}
        !           374: \begin{tabbing}
        !           375: \\
        !           376: candidate$(F,p,<)$\\
        !           377: Input : \= $F \subset Z[X]$\\
        !           378: \> $BAG?t(B p\\
        !           379: \> order $<$\\
        !           380: Output : $F$ $B$N(B $p$-compatible $B$J%0%l%V%J4pDl8uJd$^$?$P(B {\bf nil}\\
        !           381: {\rm ($B3F(B $F$ $B$KBP$7(B, {\bf nil} $B$rJV$9(B $p$ $B$N8D?t$OM-8B8D$G$J$1$l$P$J$i$J$$(B.)}\\
        !           382: \end{tabbing}
        !           383: \end{pro}
        !           384:
        !           385: \begin{al}(compatibility check $B$K$h$k%F%9%H$N>JN,(B)
        !           386: \label{bconv}
        !           387: \begin{tabbing}
        !           388: gr\"obner\_by\_change-of-ordering$(F,<)$\\
        !           389: Input : \= $F \subset \Z[X]$, order $<$\\
        !           390: Output : $Id(F)$ $B$N(B $<$ $B$K4X$9$k%0%l%V%J4pDl(B $G$\\
        !           391: $G_0 \leftarrow$ $F$ $B$N(B, $B$"$k(B order $<_0$ $B$K4X$9$k%0%l%V%J4pDl(B; $G_0 \subset \Z[X]$\\
        !           392: {\bf again:}\\
        !           393: for\= \kill
        !           394: \> $p \leftarrow (G_0,<_0)$ $B$K4X$7$F(B permissible $B$JL$;HMQ$NAG?t(B \\
        !           395: \> $G \leftarrow$ candidate($G_0$,$p$,$<$)\\
        !           396: \> If $G$ = {\bf nil} goto {\bf again:}\\
        !           397: \> else return $G$
        !           398: \end{tabbing}
        !           399: \end{al}
        !           400: candidate() $B$K$*$$$F$O(B,  $p$-compatible $B$J%0%l%V%J4pDl8uJd$rJV$9(B
        !           401: $BG$0U$N%"%k%4%j%:%`$,;HMQ2DG=$G$"$k(B. $B$3$l$^$G=R$Y$?$b$N$G$O(B,
        !           402: \begin{itemize}
        !           403: \item tl\_guess()
        !           404: \item $B@F<!2=(B + tl\_guess() + $BHs@F<!2=(B
        !           405: \item candidate\_by\_linear\_algebra()
        !           406: \end{itemize}
        !           407: $B$,E,9g$9$k(B. $B$3$l$i$N$&$A(B, $BA0<T(B 2 $B$D$K$D$$$F$OL@$i$+$@$,(B, $B:G8e$N$b$N$K(B
        !           408: $B$D$$$F$O8!>Z$rMW$9$k(B. $B$3$l$K$D$$$F<!@a$G=R$Y$k(B.
        !           409:
        !           410: \subsection{candidate\_by\_linear\_algebra()}
        !           411:
        !           412: \begin{lm}
        !           413: \label{munique}
        !           414: $B%"%k%4%j%:%`(B \ref{mfglm} $B$K$*$$$F(B $C$ $B$KB0$9$kB?9`<0$O(B $p$ $B$K$D$$$F(B stable
        !           415: $B$G(B, $E_{h,p}=\{\phi_p(c)=0 \mid c \in C\}$ $B$O0l0U2r$r;}$D(B.
        !           416: \end{lm}
        !           417: \proof
        !           418: $p$ $B$,(B $(F,<_1)$ $B$K4X$7(B permissible $B$h$j(B $NF_{<_1}(t,F)$ $B$O(B $p$ $B$K$D$$$F(B
        !           419: stable. $B$h$C$F(B $c \in C$ $B$b(B $p$ $B$K$D$$$F(B stable.
        !           420: $$S_{h,p}=\{a_t=\overline{c}_t \mid \overline{c}_t \in GF(p)\}$$
        !           421: $B$,(B $E_{h,p}$ $B$N2r$H$9$k(B.
        !           422: $$\overline{h}=\displaystyle{\sum_{t \in T(h)} \overline{c}_t t}$$
        !           423: $B$H$*$/(B. $B$9$k$H(B,
        !           424: $$0=\displaystyle{\sum_{t \in T(h)} \overline{c}_t \phi_p(NF_{<_1}(t,F)})=
        !           425: NF_{<_1}(\overline{h},\phi_p(F)).$$
        !           426: $B$h$C$F(B $\overline{h} \in Id(\phi_p(F))$ $B$h$j(B $NF_<(\overline{h},\overline{G})=0$.
        !           427: $B$9$k$H(B $\overline{G}$ $B$,HoLs%0%l%V%J4pDl$G(B $T(\overline{h})\subset T(h)$
        !           428: $B$h$j(B $\overline{h}=h$ $B$,@.$jN)$D(B.
        !           429: $B$3$l$O(B, $B2r$,0l0UE*$G(B $h$ $B$K0lCW$9$k$3$H$r0UL#$9$k(B. \qed
        !           430: \medskip
        !           431:
        !           432: \begin{co}
        !           433: \label{sqmat}
        !           434: $n$ $B$rITDj85(B $a_t$ $B$N8D?t$H$9$k$H(B, $E_h$ $B$+$i<!$N@-<A$r$b$D(B
        !           435: subsystem $E'_h$ $B$rA*$V$3$H$,$G$-$k(B.
        !           436: \begin{itemize}
        !           437: \item $E'_h$ $B$O(B $n$ $B8D$NJ}Dx<0$+$i$J$k(B.
        !           438: \item $\phi_p(E'_h)$ $B$O(B $GF(p)$ $B>e$G0l0U2r$r$b$D(B.
        !           439: \end{itemize}
        !           440: $B$3$l$+$i<!$N$3$H$,J,$+$k(B.
        !           441: \begin{itemize}
        !           442: \item $E'_h$ $B$O(B $\Q$\, $B>e0l0U2r$r;}$A(B, $B2r$O(B $p$ $B$K$D$$$F(B stable.
        !           443: \item $E_h$ $B$,2r$r$b$F$P(B, $B$=$l$O(B $E'_h$ $B$N0l0U2r$K0lCW$9$k(B.
        !           444: \end{itemize}
        !           445: \end{co}
        !           446:
        !           447: \begin{th}
        !           448: $B%"%k%4%j%:%`(B \ref{mfglm} $B$,B?9`<0=89g(B $G$ $B$rJV$;$P(B,
        !           449: $G$ $B$O(B $F$ $B$N(B $<$ $B$K4X$7$F(B $p$-compatible $B$J%0%l%V%J4pDl8uJd$G$"$k(B.
        !           450: \end{th}
        !           451: \proof
        !           452: $B3F(B $g \in G$ $B$KBP$7(B
        !           453: $$g = \displaystyle{\sum_{t \in T(h)} c_t t}$$
        !           454: $B$H=q$1(B, $\{c_t/c\}$\, ($c = c_{hc_<(g)}$) $B$,(B $E_h$ $B$N2r$H$J$k$h$&$J(B
        !           455: $h \in \overline{G}$ $B$,B8:_$9$k(B. $B$9$k$H(B,
        !           456: $$0 = c\displaystyle{\sum_{t \in T(h)} c_t/c NF_{<_1}(t,F)}
        !           457: = NF_{<_1}(g,F).$$
        !           458: $B8N$K(B $g \in Id(F)$.
        !           459: $B7O(B \ref{sqmat} $B$K$h$j(B $p$ $B$O(B $(G,<)$ $B$K$D$$$F(B permissible $B$G(B
        !           460: $\phi_p(g)$ = $\phi_p(c) h$ $B$h$j(B
        !           461: $\phi_p(G)$ $B$O(B $\overline{G}$ $B$N%0%l%V%J4pDl$G$"$k(B.
        !           462: \qed\\
        !           463: \medskip
        !           464: $B>e$NJdBj$rMQ$$$F(B $E_h$ $B$r<!$N<j=g$G2r$/(B.
        !           465:
        !           466: \begin{enumerate}
        !           467: \item $E'_h$ $B$rA*$V(B.
        !           468: \item $S \leftarrow$ $E'_h$ $B$N0l0U2r(B.
        !           469: \item $B$b$7(B $S$ $B$,(B $E_h$ $B$rK~$?$;$P(B $S$ $B$O(B $E_h$ $B$N0l0U2r(B, $B$5$b$J$/$P(B
        !           470: $E_h$ $B$O2r$r;}$?$J$$(B.
        !           471: \end{enumerate}
        !           472: $E_h$ $B$O(B $E'_h$ $B$r(B $GF(p)$ $B>e$G2r$/2>Dj$GF@$i$l$k(B.
        !           473: $B0J2<$G$O(B, $E'_h$ $B$r2r$/J}K!$K$D$$$F=R$Y$k(B. $B$3$l$O<!$N$h$&$K(B
        !           474: $BDj<02=$G$-$k(B.
        !           475:
        !           476: \begin{prob}
        !           477: $M$, $B$ $B$r$=$l$>$l(B $n\times n$, $n\times 1$ $B@0?t9TNs$H$7(B,
        !           478: $X$ $B$r(B, $BL$Dj78?t$r@.J,$H$9$k(B $n\times 1$ $B9TNs$H$9$k(B.
        !           479: $\det(\phi_p(M))\neq 0$ $B$N$b$H$G(B,
        !           480: $MX=B$ $B$r2r$1(B.
        !           481: \end{prob}
        !           482: $M$, $B$ $B$O(B, $B0lHL$K(B, $BD9Bg$J@0?t$r@.J,$K;}$DL)9TNs$H$J$k(B. $B$7$+$7(B,
        !           483: $B$b$H$b$H$NF~NOB?9`<0$N78?t$,>.$5$$>l9g(B, $B%0%l%V%J4pDl$N85$N78?t(B
        !           484: $B$9$J$o$A(B $MX=B$ $B$N2r(B $X$ $B$OHf3SE*>.$5$$>l9g$,B?$$(B. $B$3$N$h$&$J>l9g$K(B
        !           485: $B$3$NLdBj$r(B Gauss $B>C5n$G2r$/$3$H$O$3$N@a$N:G=i$NNc$G=R$Y$?$h$&$K(B
        !           486: $BHs8zN(E*$G$"$k(B. $B$3$N$h$&$J>l9g$KM-8z$J$N$,(B, Hensel $B9=@.(B, $BCf9q>jM>DjM}(B
        !           487: $B$J$I$K$h$k(B modular $B7W;;$G$"$k(B. $B$3$3$G$O(B Hensel $B9=@.$K$h$kJ}K!$r(B
        !           488: $B>R2p$9$k(B.
        !           489:
        !           490: \begin{al}
        !           491: \label{lineq}
        !           492: \begin{tabbing}
        !           493: \\
        !           494: solve\_linear\_equation\_by\_hensel$(M,B,p)$\\
        !           495: ($C_2$)\= \kill
        !           496: Input : \= $n\times n$ $B9TNs(B $M$, $n\times 1$ $B9TNs(B $B$\\
        !           497: \> $\phi_p(\det(M))\neq 0$ $B$J$kAG?t(B\\
        !           498: Output : $MX=B$ $B$J$k(B $n\times 1$ matrix $X$\\
        !           499: $R \leftarrow \phi_p(M)^{-1}$\\
        !           500: $c \leftarrow B$\\
        !           501: $x \leftarrow 0$\\
        !           502: $q \leftarrow 1$\\
        !           503: $count \leftarrow 0$\\
        !           504: do \{\\
        !           505: (1)\> $t \leftarrow \phi_p^{-1}(R \phi_p(c))$\\
        !           506: (2)\> $x \leftarrow x + qt$\\
        !           507: \> $c \leftarrow (c-Mt)/p$\\
        !           508: \> $q \leftarrow qp$\\
        !           509: \> $count \leftarrow count+1$\\
        !           510: \> {\rm ($\phi_p^{-1}$ $B$O(B $[-p/2,p/2]$ $B$K@55,2=$5$l$?5UA|(B, $(c-Mt)/p$ $B$O@0=|(B.)}\\
        !           511: \> if \= $count = {\bf Predetermined\_Constant}$ then \{\\
        !           512: \> \> $count \leftarrow 0$\\
        !           513: \> \> $X \leftarrow$ inttorat$(x,q)$\\
        !           514: \> \> if \= $X \neq$ {\bf nil} $B$+$D(B $MX=B$ then return $X$\\
        !           515: \> \}\\
        !           516: \}
        !           517: \end{tabbing}
        !           518: \end{al}
        !           519:
        !           520: \begin{al}
        !           521: \label{intrat}
        !           522: \begin{tabbing}
        !           523: \\
        !           524: inttoat$(x,q)$\\
        !           525: ($C_2$)\= \kill
        !           526: Input : $q>x$, $\GCD(x,q)=1$ $B$J$k@5@0?t(B $x$, $q$ \\
        !           527: Output : $bx \equiv a \bmod q$ $B$+$D(B
        !           528: $|a|,|b| \le \sqrt{q\over 2}$ $B$J$kM-M}?t(B $a/b$ $B$^$?$O(B {\bf nil}\\
        !           529: if $x \le \sqrt{q\over 2}$ then return $x$\\
        !           530: $f_1 \leftarrow q$, $f_2 = x$,
        !           531: $a_1 \leftarrow 0$, $a_2 \leftarrow 1$\\
        !           532: $i \leftarrow 1$\\
        !           533: do \= \{\\
        !           534: \> if \= $|f_i| \le \sqrt{q\over 2}$ then \\
        !           535: \>\> if $|a_i| \le \sqrt{q\over 2}$ then return $f_i/a_i$\\
        !           536: \>\> else return {\bf nil}\\
        !           537: \> $f_i - q_i f_{i+1} < f_{i+1}$ $B$J$k(B $q_i$ $B$r5a$a$k(B\\
        !           538: \> $f_{i+2} \leftarrow f_i - q_i f_{i+1}$\\
        !           539: \> $a_{i+2} \leftarrow a_i - q_i a_{i+1}$\\
        !           540: \> $i \leftarrow i+1$\\
        !           541: \}
        !           542: \end{tabbing}
        !           543:
        !           544: \end{al}
        !           545: \begin{lm}(\cite{WANG2}\cite{DIXON})
        !           546: \label{intratlm}
        !           547: $x$, $q$ $B$r(B $q>x>1$, $\GCD(x,q)=1$ $B$J$k@5@0?t$H$9$k(B. $B$3$N$H$-(B,
        !           548: $|a|,|b|\le\sqrt{q/2}$, $\GCD(a,b)=1$ $B$J$k@0?t(B $a,b$ $(b>0)$ $B$*$h$S@0?t(B
        !           549: $c$ $B$,$"$C$F(B $ax+cq=b$ $B$H$J$k$J$i$P(B, $(a,b,c)$ $B$O(B $(q,x)$ $B$KBP$9$k3HD%(B
        !           550: Euclid $B8_=|K!$K$h$jF@$i$l$k(B.
        !           551: \end{lm}
        !           552: [$BN,>Z(B]
        !           553: $x>1$ $B$h$j(B $a \neq b$ $B$H$7$F$h$$(B.
        !           554: $ax+cq=b$ $B$h$j(B ${x \over q}+{c \over a} = {b \over aq}.$ $B$3$3$G(B
        !           555: $$|{b \over {aq}}| = |{{ab} \over {a^2q}}| < {1 \over {2a^2}}$$
        !           556: $B$h$j(B
        !           557: $$|{x \over q}+{c \over a}| < {1 \over {2a^2}}.$$$B$h$C$F(B, $-c/a$ $B$O(B
        !           558: $x/q$ $B$N<g6a;wJ,?t$N0l$D(B. ($BO"J,?t$N@-<A$K$h$k(B. \cite[Section 24]{TAKAGI} $B;2>H(B.)
        !           559: $\GCD(a,b)=1$ $B$h$j(B $\GCD(a,c)=1$ $B$G$"$j(B, $b>0$ $B$KBP$7$F(B $(a,c)$ $B$O0l0U(B
        !           560: $BE*$K7h$^$k(B. $B$h$C$F(B, $(a,b,c)$ $B$O(B $(q,x)$ $B$KBP$9$k3HD%(B Euclid $B8_=|K!$N(B
        !           561: $B78?t$H$7$FF@$i$l$k(B. \qed
        !           562:
        !           563: \begin{lm}
        !           564: \label{lineqlm}
        !           565: (1) $B$K$*$$$F(B $Mx \equiv B \bmod q$ $B$+$D(B $c = (B-Mx)/q$.
        !           566: \end{lm}
        !           567: \proof
        !           568: $B5"G<K!$K$h$j<($9(B. $count = 0$ $B$N$H$-L@$i$+(B. $count = m$
        !           569: $B$^$G8@$($?$H$9$k(B. $B$3$N$H$-(B, (2) $B$G(B
        !           570: $Mt \equiv c \bmod p$ $B$h$j(B $M(x+qt) \equiv Mx+q(B-Mx)/q \bmod qp$.
        !           571: $B$9$J$o$A(B $M(x+qt) \equiv B \bmod qp$. $B$^$?(B,
        !           572: $(c-Mt)/p = ((B-Mx)-qMt)/qp = (B-M(x+qt))/qp$ $B$h$j(B $count = m+1$
        !           573: $B$G$b8@$($k(B. \qed
        !           574:
        !           575: \begin{pr}
        !           576: $B%"%k%4%j%:%`(B \ref{lineq} $B$O(B $MX=B$ $B$N2r(B $X$ $B$r=PNO$9$k(B.
        !           577: \end{pr}
        !           578: \proof
        !           579: $BJdBj(B \ref{lineqlm} $B$h$j(B, $count=m$ $B$N$H$-(B (1) $B$K$*$$$F(B $Mx \equiv B
        !           580: \bmod p^m$. $\det(M) \neq 0$ $B$h$j(B $x$ $B$OK!(B $p^m$ $B$G0l0UE*$G$"$k(B. $B0lJ}(B
        !           581: $MX=B$ $B$OM-M}?tBN>e0l0UE*$K2r$r;}$D(B. $B$3$N2r$r(B$X=N/D$ ($D$ $B$O@0?t(B, $N$
        !           582: $B$O@0?t%Y%/%H%k(B) $B$H=q$/$H$-(B, $Dr \equiv 1 \bmod p^m$$B$J$k@0?t(B $r$ $B$r$H$l(B
        !           583: $B$P(B $M(rN) \equiv B \bmod p^n$. $B$h$C$F(B $rN \equiv x \bmod p^m$.
        !           584: $D$, $N$ $B$N3F@.J,$,(B
        !           585: $A$ $B$r1[$($J$$$H$-(B, $p^m > 2A^2$ $B$J$k(B $m$ $B$r$H$l$P(B, $BJdBj(B \ref{intratlm}
        !           586: $B$h$j(B $rN$ $B$9$J$o$A(B $x$ $B$+$i%"%k%4%j%:%`(B \ref{intrat} $B$K$h$j(B
        !           587: $N/D$ $B$,I|85$5$l$k(B.
        !           588: \qed\\
        !           589: {\bf Predetermined\_Constant} $B$O$"$k@5@0?t$G(B, $BM-M}?t$K0z$-La$7$F%A%'%C(B
        !           590: $B%/$r9T$&IQEY$r@)8f$9$k(B. $B%"%k%4%j%:%`(B \ref{lineq} $B$K$*$$$F(B $c$ $B$O(B
        !           591: $nMAX(\|M\|_\infty,\|B\|_\infty)$$B$G2!$($i$l$k$3$H$,$o$+$k(B. $B$3$l$O(B, $B3F(B
        !           592: $B%9%F%C%W$,$"$k(B constant $B;~4VFb$G7W;;$G$-$k$3$H$r<($9(B. $B$^$?(B, $B2r$NJ,JlJ,(B
        !           593: $B;R$,(B $A$ $B$G2!$($i$l$F$$$l$P(B, $q > 2A^2$ $B$K$J$C$?CJ3,$G2r$rI|85$G$-(B
        !           594: $B$k(B. $B$3$l$O(B, $B2r$NBg$-$5$K1~$8$?<j4V$G7W;;$G$-$k$3$H$r0UL#$9$k(B. $B$3$l$KBP(B
        !           595: $B$7$F(B, $B78?tKDD%$r2!$($?(B Gauss $B>C5nK!$G$"$k(B fraction-free $BK!$K$h$C$F$b(B,
        !           596: $B2r$NBg$-$5$K$+$+$o$i$:(B, $B78?t9TNs$N9TNs<0$r7W;;$7$F$7$^$&$H$$$&E@$G(B,
        !           597: Gauss $B>C5nK!$O(B, $B$3$NLdBj$r2r$/$?$a$K$OITE,@Z$G$"$k(B.
        !           598:
        !           599: \section{$B%?%$%_%s%0%G!<%?(B}
        !           600:
        !           601: $BK\@a$G$O(B, $B0J2<$N$h$&$J%Y%s%A%^!<%/LdBj$K4X$7(B, $BK\>O$G=R$Y$?MM!9$J(B
        !           602: change of ordering $B%"%k%4%j%:%`$N8zN($NHf3S$r<($9(B. $B$^$?(B, $BL?Bj(B
        !           603: \ref{RUR} $B$G?($l$?(B RUR $B$N%b%8%e%i7W;;$rF1$8LdBj$KE,MQ$7(B,
        !           604: $B$=$NM%0L@-$r<B837k2L$K$h$j<($9(B.  $B7WB,$O(B, PC (FreeBSD, 300MHz Pentium
        !           605: II, 512MB of memory) $B$G9T$C$?(B. $BC10L$OIC(B. garbage collection $B;~4V$O=|$$(B
        !           606: $B$F$"$k(B.
        !           607: \begin{tabbing}
        !           608: $MMM\;\;$ \= \kill
        !           609: $C(n)$ \> The cyclic n-roots system of n variables. (Faugere {\it et al.},1993).\\
        !           610:        \> $\{f_1,\cdots,f_n\}$ where
        !           611:          $f_k=
        !           612: \displaystyle{\sum_{i=1}^n\prod_{j=i}^{k+j-1}c_{j \bmod n}-\delta_{k,n}}$.
        !           613: ($\delta$ is the Kronecker symbol.) \\
        !           614: \> The variables and ordering : $c_n \succ c_{n-1} \succ \cdots \succ c_1$\\
        !           615: $K(n)$ \> The Katsura system of n+1 variables. \\
        !           616:       \> $\{u_l - \sum_{i=-n}^n u_i u_{l-i} (l = 0,\cdots, n-1),
        !           617:            \sum_{l=-n}^n u_l - 1\}$\\
        !           618:       \> The variables and ordering : $u_0 \succ u_1 \succ \cdots \succ u_n$.\\
        !           619:       \> Conditions : $u_{-l} = u_l$ and $u_l = 0 (|l| > n)$. \\
        !           620: $R(n)$ \> {\tt e7} in Rouillier (1996). \\
        !           621:       \> $\{-1/2+\sum_{i=1}^n(-1)^{i+1}x_i^k (k=2, \cdots, n+1) \}$\\
        !           622:       \> The variables and ordering : $x_n \succ x_{n-1} \succ \cdots \succ x_1$.\\
        !           623: $D(3)$ \> {\tt e8} in Rouillier (1996). \\
        !           624:        \> $\{f_0,f_1,f_2,\cdots,f_7\}$\\
        !           625:        \> {\scriptsize $f_0=-420y^2-280zy-168uy-140vy-120sy-210ty-105ay+12600y-13440$}\\
        !           626:        \> {\scriptsize $f_1=-840zy-630z^2-420uz-360vz-315sz-504tz-280az+18900z-20160$}\\
        !           627:        \> {\scriptsize $f_2=-630ty-504tz-360tu-315tv-280ts-420t^2-252at+12600t-13440$}\\
        !           628:        \> {\scriptsize $f_3=-5544uy-4620uz-3465u^2-3080vu-2772su-3960tu-2520au+103950u-110880$}\\
        !           629:        \> {\scriptsize $f_4=-4620vy-3960vz-3080vu-2772v^2-2520sv-3465tv-2310av+83160v-88704$}\\
        !           630:        \> {\scriptsize $f_5=-51480sy-45045sz-36036su-32760sv-30030s^2-40040ts-27720as+900900s-960960$}\\
        !           631:        \> {\scriptsize $f_6=-45045ay-40040az-32760au-30030av-27720as-36036at-25740a^2+772200a-823680$}\\
        !           632:        \> {\scriptsize $f_7=-40040by-36036bz-30030bu-27720bv-25740bs-32760bt-24024ba+675675b-720720$}\\
        !           633:        \normalsize
        !           634:          \> The variables and ordering : $b \succ a \succ s \succ v \succ u \succ t \succ z \succ y$.\\
        !           635: $Rose$ \> The Rose system.\\
        !           636: %      \> $\{u_4^4-20/7a_{46}^2, a_{46}^2u_3^4+7/10a_{46}u_3^4+7/48u_3^4-50/27a_{46}^2-35/27a_{46}-49/216,$\\
        !           637: %      \> $a_{46}^5u_4^3+7/5a_{46}^4u_4^3+609/1000a_{46}^3u_4^3+49/1250a_{46}^2u_4^3$\\
        !           638: %      \> $-27391/800000a_{46}u_4^3-1029/160000u_4^3+3/7a_{46}^5u_3u_4^2+3/5a_{46}^6u_3u_4^2$\\
        !           639: %      \> $+63/200a_{46}^3u_3u_4^2+147/2000a_{46}^2u_3u_4^2+4137/800000a_{46}u_3u_4^2$\\
        !           640: %      \> $-7/20a_{46}^4u_3^2u_4-77/125a_{46}^3u_3^2u_4-23863/60000a_{46}^2u_3^2u_4$\\
        !           641: %      \> $-1078/9375a_{46}u_3^2u_4-24353/1920000u_3^2u_4-3/20a_{46}^4u_3^3-21/100a_{46}^3u_3^3$\\
        !           642: %      \> $-91/800a_{46}^2u_3^3-5887/200000a_{46}u_3^3-343/128000u_3^3 \}$\\
        !           643:     \> $O_1$ : $u_3 \succ u_4 \succ a_{46}$, $O_2$ : $u_3 \succ a_{46} \succ u_4$.\\
        !           644: $Liu$ \> The Liu system.\\
        !           645:       \> $\{y(z-t)-x+a, z(t-x)-y+a, t(x-y)-z+a, x(y-z)-t+a\}$\\
        !           646:       \> The variables and ordering : $x \succ y \succ z \succ t \succ a$.\\
        !           647: $Fate$ \> The Fateman system, appeared on NetNews. \\
        !           648:        \> $\{s^3+2r^3+2q^3+2p^3$, $s^5+2r^5+2q^5+2p^5$,\\
        !           649:        \> $-s^5+(r+q+p)s^4+(r^2+(2q+2p)r+q^2+2pq+p^2)s^3+(r^3+q^3+p^3)s^2$\\
        !           650:        \> $+(3r^4+(2q+2p)r^3+(4q^3+4p^3)r+3q^4+2pq^3+4p^3q+3p^4)s+(4q+4p)r^4$\\
        !           651:        \> $+(2q^2+4pq+2p^2)r^3+(4q^3+4p^3)r^2+(6q^4+4pq^3+8p^3q+6p^4)r$\\
        !           652:           \> $+4pq^4+2p^2q^3+4p^3q^2+6p^4q\}$\\
        !           653:        \> The variables and ordering : $p \succ q \succ r \succ s$.\\
        !           654: $hC(6)$ \> A homogenization of C(6). \\
        !           655:        \> $(C_6\backslash \{c_1c_2c_3c_4c_5c_6-1\})\cup \{c_1c_2c_3c_4c_5c_6-t^6\}$\\
        !           656:        \> The variables and ordering :
        !           657:           $c_1 \succ c_2 \succ c_3 \succ c_4 \succ c_5 \succ c_6 \succ t$.\\
        !           658: \end{tabbing}
        !           659:
        !           660: \subsection{Change of ordering}
        !           661:
        !           662: $BM=$a7W;;$7$F$"$k(B DRL \gr $B4pDl$+$i=PH/$7$F(B, LEX \gr $B4pDl7W;;$9$k(B. $BMQ$$(B
        !           663: $B$k%"%k%4%j%:%`$O(B, TL (tl\_guess$()$; $B%"%k%4%j%:%`(B \ref{tlguess}), HTL
        !           664: ($B@F<!2=(B+tl\_guess$()$+$BHs@F2=(B), LA (candidate\_by\_linear\_algebra$()$;
        !           665: $B%"%k%4%j%:%`(B \ref{mfglm} (0 $B<!85%7%9%F%`$N$_(B))$B$G$"$k(B. $BI=(B
        !           666: \ref{mcotab} $B$O(B DRL $B$+$i(B LEX $B$X$NJQ49$K$+$+$k;~4V$r$7$a$9(B. {\it DRL}
        !           667: $B$O(B, DRL $B$N7W;;;~4V$r<($9(B. $B%0%l%V%J4pDl%A%'%C%/$r>J$/8z2L$r<($9$?$a$K(B,
        !           668: tl\_ckeck$()$ ($B%"%k%4%j%:%`(B \ref{tlcheck}) $B$N;~4V$b<($9(B.
        !           669:
        !           670: \begin{table}[hbtp]
        !           671: \caption{Modular change of ordering}
        !           672: \label{mcotab}
        !           673: \begin{center}
        !           674: \begin{tabular}{|c||c|c|c|c|c|c|c|} \hline
        !           675:        & $K(5)$ & $K(6)$ & $K(7)$ & $C(6)$ & $C(7)$ & $R(5)$ & $R(6)$ \\ \hline
        !           676: {\it DRL}&0.84 &8.4    &74     &3.1    &1616   &11     &1775   \\ \hline
        !           677: {\it TL}&$\infty$              &$\infty$               &$\infty$ &$\infty$     &$\infty$       &$\infty$       &$\infty$       \\ \hline
        !           678: {\it HTL}      &16     &1402   &$1.6\times 10^5$       &5.6    &$2\times 10^4$ &383    &$2.1\times 10^5$       \\ \hline
        !           679: {\it LA}       &4.7    &158    &6813   &4      &435    &9.5            &258            \\ \hline
        !           680: tl\_check      &2.3    &177    &$1.3\times 10^4$       &1.1    &2172   &3      &40             \\ \hline
        !           681: \end{tabular}
        !           682:
        !           683: \begin{tabular}{|c||c|c|c||c|c|c|} \hline
        !           684:        & $D(3)$ & $RoseO_1$ & $RoseO_2$ & $Liu$ & $Fate$ & $hC(6)$ \\ \hline
        !           685: {\it DRL}      &30     &0.19   &0.15   &0.06   &0.5    &7.2    \\ \hline
        !           686: {\it TL}       & $\infty$      &1.7    &354    &$\infty$       &4      &25     \\ \hline
        !           687: {\it HTL}      &$4.1\times 10^4$       &1.7    &36     &18     &4      &25     \\ \hline
        !           688: {\it LA}       &585    &3.3    &12     & --- & --- & --- \\ \hline
        !           689: tl\_check      &575            &0.6    &13     &17             &26     &24     \\ \hline
        !           690: \end{tabular}
        !           691: \end{center}
        !           692: \end{table}
        !           693: $B@0?t78?tB?9`<0$KBP$7(B, $B$=$N(B {\bf maginitude} $B$r(B, $B78?t$N%S%C%HD9$NOB$GDj5A$9$k(B.
        !           694: {\it TL} $B$H(B {\it HTL} $B$N:9$r8+$k$?$a$K(B,
        !           695: $BI=(B \ref{magnitude} $B$G(B, $B7W;;ESCf$K$*$1$k:GBg(B magnitude $B$r<($9(B.
        !           696:
        !           697: \begin{table}[hbtp]
        !           698: \caption{Maximal magnitude}
        !           699: \label{magnitude}
        !           700: \begin{center}
        !           701: \begin{tabular}{|c||c|c|c|c|c|c|} \hline
        !           702:        & $C(6)$ & $K(5)$ & $K(6)$ & $RoseO_1$ & $RoseO_2$ & Liu \\ \hline
        !           703: {\it TL}& $>$ 735380 & $> 2407737 $ & $>$ 57368231 & 69764 & 947321 & $>$ 327330 \\ \hline
        !           704: {\it HTL}& 1992 & 44187 & 422732 & 37220 & 70018 & 21095 \\ \hline
        !           705: \end{tabular}
        !           706: \end{center}
        !           707: \end{table}
        !           708: $BI=$h$jL@$i$+$K(B, {\it TL} $B$OHs@F<!B?9`<0$KBP$9$k%0%l%V%J4pDl7W;;$KIT8~$-(B
        !           709: $B$G$"$k$3$H$,$o$+$k(B. $B$5$i$K(B, $BI=(B \ref{mcotab} $B$O(B {\it HTL} $B$KBP$9$k(B
        !           710: {\it LA} $B$NM%0L@-$r<($7$F$$$k(B. $B$3$l$O(B, Buchberger $B%"%k%4%j%:%`$,(B
        !           711: Euclid $B$N8_=|K!$KBP1~$7$F$$$F(B, $BCf4V78?tKDD%$G8zN($,:81&$5$l$k$N(B
        !           712: $B$KBP$7(B, modular $B%"%k%4%j%:%`$N8zN($O7k2L$NBg$-$5$N$_$K0MB8$9$k(B
        !           713: $B$3$H$K$h$k(B.
        !           714:
        !           715: \subsection{RUR}
        !           716:
        !           717: RUR $B$N(B modular $B7W;;$N%?%$%_%s%0%G!<%?$r<($9(B. $B7W;;4D6-$OA0@a$HF1MM$G$"(B
        !           718: $B$k(B. $B$3$3$G$O(B, $BM=$a(B modular $B7W;;$K$h$j(B separating element$B$r5a$a$F$"(B
        !           719: $B$k(B. $B$3$l$i$rMQ$$$F(B, $B$=$l$>$l<!$N$h$&$JB?9`<0$rE:2C$7$?%$%G%"%k$KBP$7(B,
        !           720: $w$ $B$K4X$9$k(B RUR $B7W;;$r9T$&(B.
        !           721:
        !           722: \begin{tabbing}
        !           723: $MMM\;\;$ \= \kill
        !           724: $C(6)$ \> $w-(c_1+3c_2+9c_3+27c_4+81c_5+243c_6)$\\
        !           725: $C(7)$ \> $w-(c_1+3c_2+9c_3+27c_4+81c_5+243c_6+729c_7)$\\
        !           726: $K(n)$ \> $w-u_n$\\
        !           727: $R(5)$ \> $w-(x_1-3x_2-2x_3+3x_4+2x_5)$\\
        !           728: $R(6)$ \> $w-(x_1-3x_2-2x_3+3x_4+2x_5-4x_6)$\\
        !           729: $D(3)$ \> $w-y$
        !           730: \end{tabbing}
        !           731: %\begin{table}[hbtp]
        !           732: %\label{mrurdata}
        !           733: %\caption{$BF~NO%$%G%"%k$K4X$9$k%G!<%?(B}
        !           734: %\begin{center}
        !           735: %\begin{tabular}{|c||c|c|c|c||c|c|c|c|c|} \hline
        !           736: %      & $K(5)$        & $K(6)$        & $K(7)$        & $K(8)$        & $C(6)$& $C(7)$        & $R(5)$ & $R(6)$ & $D(3)$ \\ \hline
        !           737: %$\dim_{\Q} R/I$       & 32    & 64    & 128   & 256   & 156   & 924   &144    &576    & 128 \\ \hline
        !           738: %DRL GB& 0.8   & 7.2   & 68    & 798   & 3.1   & 1616  & 11    & 1775  & 30    \\ \hline
        !           739: %\end{tabular}
        !           740: %\end{center}
        !           741: %\end{table}
        !           742: \begin{table}[hbtp]
        !           743: \label{mrurtab}
        !           744: \caption{$B7W;;;~4V(B ($BIC(B)}
        !           745: \begin{center}
        !           746: \begin{tabular}{|c|c|c|c||c|c|c|c|c|} \hline
        !           747:        & $K(6)$& $K(7)$& $K(8)$& $C(6)$& $C(7)$& $R(5)$ & $R(6)$ & $D(3)$ \\ \hline
        !           748: Total  & 7.4   & 69    & 1209  & 4.6   & 1643  & 52    & 8768  & 67    \\ \hline
        !           749: Quick test& 0.4        & 3.2   & 26    & 0.5   & 57    & 6.5   & 384   & 3.1   \\ \hline
        !           750: Normal form& 1.1       & 12    & 308   & 1.4   & 762   & 15    & 2861  & 7.3   \\ \hline
        !           751: Linear equation& 4.1   & 43    & 775   & 1.4   & 641   & 22    & 3841  & 45    \\ \hline
        !           752: Garbage collection& 1.7        & 10    & 100   & 1.2   & 181   & 7.8   & 1681  & 11    \\ \hline
        !           753: \end{tabular}
        !           754: \end{center}
        !           755: \end{table}
        !           756:
        !           757: %\begin{table}[hbtp]
        !           758: %\label{maxblen}
        !           759: %\caption{Maximal bit length of coefficients in LEX basis and the RUR}
        !           760: %\begin{center}
        !           761: %\begin{tabular}{|c||c|c|c|c|c|} \hline
        !           762: %& $K(5)$ & $K(6)$     & $K(7)$        & $K(8)$ & $D(3)$ \\ \hline
        !           763: %LEX & 1421 & 6704 & 36181 & --- & 6589 \\ \hline
        !           764: %RUR & 120 & 249 & 592 & 1258 & 821 \\ \hline
        !           765: %\end{tabular}
        !           766: %\end{center}
        !           767: %\end{table}
        !           768: $BI=$G(B, Quick Test $B$O(B modular $B7W;;$G(B $w$$B$,(B separating element $B$H$J$k$3$H(B
        !           769: $B$r%A%'%C%/$9$k;~4V(B, Normal Form $B$O(B, $B@~7AJ}Dx<0$r@8@.$9$k$?$a$N(B,
        !           770: monomial $B$N@55,7A$N7W;;(B, Linear Equation $B$O(B, $B@~7AJ}Dx<05a2r$N;~4V$G$"(B
        !           771: $B$k(B. $BI=(B \ref{mcotab} $B$HHf3S$9$l$P(B, $B$"$kJQ?t$,(B separating element $B$H$J$C(B
        !           772: $B$F$$$k$h$&$JLdBj$G$O(B, RUR $B7W;;$N8zN($,Hs>o$K$h$$$3$H$,J,$+$k(B. $B$3$NM}M3(B
        !           773: $B$O(B, RUR $B$K8=$l$k78?t$N(B bit $BD9$,(B, LEX $B4pDl$N$=$l$KHf$Y$FHs>o$K>.$5$$(B($BNc(B
        !           774: $B$($P(B $K(7)$ $B$G$O(B 60 $BJ,$N(B 1 $BDxEY(B) $B$3$H$H(B, $B@~7AJ}Dx<0$N5a2r$,(B, $B7k2L$NBg(B
        !           775: $B$-$5$K1~$8$?<j4V$G$G$-$k$3$H$+$iJ,$+$k(B.
        !           776: