Return to rims2004-noro.tex CVS log

Up to [local] / OpenXM / doc / Papers

Added noro's slides for CA-ALIAS04.

\documentclass[12pt]{jarticle}
\usepackage[FVerb,theorem]{rims02}
\topmargin -0.5in
\oddsidemargin -0in
\evensidemargin -0in
\textheight 9.5in
\textwidth 6in
\IfFileExists{my.sty}{\usepackage{my}}{}
\IfFileExists{graphicx.sty}{\usepackage{graphicx}}{}
\IfFileExists{epsfig.sty}{\usepackage{epsfig}}{}
\title{$BBe?tBN>e$N%$%G%"%k$N%0%l%V%J!<4pDl7W;;$K$D$$$F(B}
\author{$BLnO$(B $B@59T(B \\ ($B?@8MBgM}(B)}
\date{}
\begin{document}
\maketitle
\def\gr{Gr\"obner $B4pDl(B}
\def\st{\, s.t. \,}
\def\noi{\noindent} 
\def\Q{{\bf Q}}
\def\Z{{\bf Z}}
\def\NF{{\rm NF}}
\def\ve{\vfill\eject} 
\newcommand{\tmred}[1]{\smash{\mathop{\hbox{\rightarrowfill}}\limits_{\scriptstyle #1}\limits^{\scriptstyle *}}}

\begin{abstract}
$BK\9F$G$O(B, $BBe?tBN(B, $B$9$J$o$AM-M}?tBN(B $\Q$ $B$NM-8B<!Be?t3HBg$K$*$1$k(B
$B8zN(E*1i;;$r9T$&$?$a$N(B, $BBe?tE*?t$N4JLs$*$h$S5U857W;;$K$D$$$F=R$Y$k(B.
$B$5$i$K(B, $B$=$l$i$rMQ$$$?(B, $BBe?tBN>e$G$N>e$G$N%0%l%V%J!<(B
$B4pDl7W;;$K$D$$$F=R$Y$k(B.
\end{abstract}

\section{$BBe?tBN>e$N1i;;$K$D$$$F(B}


\subsection{$BBe?tBN$N85$NI=8=J}K!(B}

$B$h$/CN$i$l$F$$$k$h$&$K(B, $BG$0U$NBe?tBN(B $F$ $B$O86;O85$r$b$D(B. $B$9$J$o$A(B, $B$"(B
$B$kBe?tE*?t(B $\alpha$ $B$,B8:_$7$F(B $F=\Q(\alpha)$ $B$H=q$1$k(B. $B$h$C$F(B,
$\alpha$ $B$N(B $\Q$ $B>e$N:G>.B?9`<0$r(B $m(t)$ $B$H$9$l$P(B,
$F=\Q[t]/(m(t))$ $B$G$"$j(B, $F$ $B$N85$O0lJQ?tB?9`<0$GI=8=$G$-$k(B. $B$7$+$7(B, 
$B7W;;8zN($r9M$($?>l9g(B, $B86;O85$K$h$kI=8=$O(B, $B78?t%5%$%:$NA}Bg$r>7$-$d$9$$(B
$B$?$aK>$^$7$/$J$$(B. $B$3$N$?$a(B, $F$ $B$rC`<!3HBg$H$7$FM?$($k$N$,8=<BE*$G$"$k(B. 
$B$9$J$o$A(B, 
$$F_0=\Q,\quad F_i = F_{i-1}(\alpha_i)\quad (i=1,\ldots,n),\quad F=F_m$$
$B$G(B, $B3F(B $\alpha_i$ $B$,(B $F_{i-1}$ $B>eBe?tE*$G(B, $F_{i-1}$ $B>e$N:G>.(B
$BB?9`<0$,(B $m_i(t,\alpha_1,\ldots,\alpha_{i-1})$ $B$GM?$($i$l$F$$$k$H$9$k(B
$B$N$G$"$k(B. $m_i$ $B$N4{Ls@-$N%A%'%C%/$K$O$7$P$7$P:$Fq$JB?9`<00x?tJ,2r$,I,(B
$BMW$H$J$k$,(B, $B9,$$(B, knapsack factorization $B%"%k%4%j%:%`$K$h$j(B, $B%A%'%C%/(B
$B2DG=$JB?9`<0$NHO0O$,BgI}$K3HBg$7$?(B.  $B0J2<$G$O(B, $B4{$K4{Ls@-$,J]>Z$5$l$F(B
$B$$$kC`<!3HBg$,M?$($i$l$F$$$k$H$9$k(B. $B%$%G%"%k$N8@MU$G=R$Y$l$P(B,
$$I=\langle m_1(x_1),m_2(x_1,x_2),\ldots,m_n(x_1,\ldots,x_n)\rangle$$
$B$,(B $\Q[X]=\Q[x_1,\ldots,x_n]$ $B$N6KBg%$%G%"%k$H$$$&$3$H$K$J$k(B.

\subsection{$B4JLs2=(B}

$B3F(B $m_i$ $B$O(B,
$$m_i(x_1,\dots,x_i)=c_{d_i} x_i^{d_i}+c_{d_{i-1}}(x_1,\ldots,x_{i-1})x_i^{d_i-1}+\cdots+c_0(x_1,\ldots,x_{i-1})$$
($c_{d_i}\in \Z$, $c_j(x_1,\ldots,x_{i-1})\in \Z[x_1,\ldots,x_{i-1}]$)
$B$H$$$&7A$G$"$k$H$7$F$h$$(B. $B$5$i$K(B, $m_i$ $B$O(B $\langle m_1,\ldots,m_{i-1}\rangle$ $B$K4X$7$F@55,7A(B, $B$9$J$o$A(B $\deg_{x_j}(m_i) < d_j$ ($j=1,\ldots,i-1$)
$B$H$9$k(B. $B$3$N$H$-(B, $G=\{m_1,\ldots,m_n\}$ $B$O(B, 
$x_n > x_{n-1} > \cdots > x_1$ $B$J$k<-=q<0=g=x$K4X$9$k(B $I$ $B$N%0%l%V%J!<4pDl$H$J$C$F$$$k(B.
$Q[X]/I$ $B$N85(B $h(x) \bmod I$ $B$KBP$7(B, 
$h_0 \equiv h \bmod I$, $\deg_{x_i}(h_0) < d_i$ $B$J$k(B $h_0$ $B$O(B
$G$ $B$K4X$9$k@55,7A(B $\NF_G(h)$ $B$KEy$7$$(B. 

$h_0$ $B$O(B, $B%0%l%V%J!<4pDl$r;}$A=P$9$^$G$b$J$/(B, 1 $BJQ?tB?9`<0$N>jM>7W;;$K(B
$B$h$jM?$($i$l$k(B.  $BNc$($P(B, $h$ $B$+$i(B, $m_n, m_{n-1},\ldots,m_1$ $B$H$$$&=g(B
$B$K>jM>$r7W;;$7$F$$$1$PF@$i$l$k(B. $B$b$A$m$s(B, $m_i$ $B$K$h$k>jM>$O(B $x_i$ $B$r(B
$B<gJQ?t$H$7$F7W;;$9$k(B. $B$7$+$7$3$NJ}K!$O(B, $B8zN($+$i8+$?>l9g:G0-$G$"$k(B. $B$J(B
$B$<$J$i(B, $m_i$ $B$K$h$k>jM>$r7W;;$9$k$H(B, $B0lHL$K(B $j<i$ $B$J$k(B $x_j$ $B$K4X$9$k(B
$B<!?t$,>e$,$k(B. $BFC$K(B, $m_2$ $B$^$G$N>jM>$r7W;;$7$?CJ3,$N>jM>$O(B, $x_1$ $B$K4X(B
$B$9$k<!?t$,BgJQ9b$/$J$C$F$$$k2DG=@-$,$"$k(B. $B$=$3$G(B, $i$ $B$,>.$5$$(B $m_i$
$B$K$h$k>jM>7W;;$rM%@h$5$;$kJ}K!$,9M$($i$l$k(B. $B$3$NJ}K!$O(B, $B>e$NJ}K!$h$j(B
$B$O8zN($,$h$$$H9M$($i$l$k$,(B, $B$d$O$j2<$N=g=x$NJQ?t$N<!?t$,5^$K>e$,$k(B
$B$3$H$OK>$^$7$/$J$$(B.

$B$3$N>l9g(B, $B<B$O(B $G$ $B$K$h$kC19`4JLs$rMQ$$$l$P(B, $B8zN($h$/>jM>(B
$B7W;;$r9T$&$3$H$,$G$-$k(B. $B$3$N:](B, $B3F4JLs%9%F%C%W$KMQ$$$k(B $m_i$
$B$H$7$F$O(B, $i$ $B$N>.$5$$$b$N$rM%@h$9$kI,MW$,$"$k(B.

\begin{Exp}\rm
\label{exp:degree7}
$m_1(x_1)=x_1^7-7x_1+3$,\\
$m_2(x_1,x_2)=x_2^6+x_1x_2^5+x_1^2x_2^4+x_1^3x_2^3+x_1^4x_2^2+x_1^5x_2+x_1^6-7$,\\
$m_3(x_1,x_2,x_3)=63x_3^4+((-2x_1^5-5x_1^4-x_1^3-7x_1^2+3x_1+6)x_2^5+(-5x_1^5-5x_1^3-3x_1^2+7x_1)x_2^4+(-x_1^5-5x_1^4+8x_1^2+4x_1-24)x_2^3+(-7x_1^5-3x_1^4+8x_1^3+6x_1^2-28x_1+6)x_2^2+(3x_1^5+7x_1^4+4x_1^3-28x_1^2+14x_1+18)x_2+6x_1^5-24x_1^3+6x_1^2+18x_1+12)x_3^3+((x_1^4-2x_1^3-4x_1^2+5x_1)x_2^5+(x_1^5-2x_1^3+12x_1^2+22x_1)x_2^4+(-2x_1^5-2x_1^4+8x_1^3+20x_1^2+15x_1-12)x_2^3+(-4x_1^5+12x_1^4+20x_1^3+12x_1^2+5x_1+15)x_2^2+(5x_1^5+22x_1^4+15x_1^3+5x_1^2+25x_1-6)x_2-12x_1^3+15x_1^2-6x_1+48)x_3^2+((5x_1^4+2x_1^3+x_1^2+16x_1-18)x_2^5+(5x_1^5+6x_1^4-4x_1^3+18x_1^2-13x_1)x_2^4+(2x_1^5-4x_1^4+16x_1^3-11x_1^2-18x_1+48)x_2^3+(x_1^5+18x_1^4-11x_1^3-6x_1^2+43x_1-6)x_2^2+(16x_1^5-13x_1^4-18x_1^3+43x_1^2+14x_1-48)x_2-18x_1^5+48x_1^3-6x_1^2-48x_1+24)x_3+(4x_1^5-x_1^4+9x_1^3-2x_1^2-16x_1+6)x_2^5+(-x_1^5+6x_1^4+2x_1^3-15x_1^2-x_1+45)x_2^4+(9x_1^5+2x_1^4-22x_1^3-5x_1^2+40x_1)x_2^3+(-2x_1^5-15x_1^4-5x_1^3+33x_1^2-8x_1+84)x_2^2+(-16x_1^5-x_1^4+40x_1^3-8x_1^2+36x_1-6)x_2+6x_1^5+45x_1^4+84x_1^2-6x_1-84$
$B$H$9$k(B. $m_1(\alpha_1)=0$, $m_2(\alpha_1,\alpha_2)=0$, $m_3(\alpha_1,\alpha_2,\alpha_3)=0$ $B$rK~$?$9(B $\alpha_1$, $\alpha_2$, $\alpha_3$ $B$K$h$j(B
$F=\Q(\alpha_1,\alpha_2,\alpha_3)$ $B$H$9$k(B. $(\alpha_1+\alpha_2+\alpha_3)^{20}$
$B$r(B, $m_1,m_2,m_3$ $B$N=g$KMQ$$$kC19`4JLs$K$h$j4JLs$9$k$H(B 0.1 $BIC$G7W;;$G$-$k$,(B,
$B5U=g$G9T$&$H(B 260 $BIC$+$+$k(B. $B$3$N:9$O4JLs$5$l$kBP>]$,Bg$-$/$J$k$H5^B.$K(B
$BA}Bg$9$k(B.
\end{Exp}

\subsection{$B5U857W;;(B}

$B4JLs7W;;$HJB$s$GBe?tBN>e$N8zN(E*7W;;$r:$Fq$K$9$k$b$N$,(B, $B5U857W;;$G$"$k(B. 
$BC13HBg$N>l9g$K$O(B, $B3HD%(B Euclid $B8_=|K!(B, $BNc$($PItJ,=*7k<0%"%k%4%j%:%`$K$h(B
$B$j(B, $B3HBg<!?t(B $d$ $B$K4X$7(B $O(d^2)$ $B$N<j4V$G7W;;$G$-$k(B. $B$3$NJ}K!$O(B, $BC`<!(B
$B3HBg$KBP$7$F$b:F5"E*$KE,MQ$G$-$k$,(B, $B7W;;8zN(>e<o!9$NLdBj$r@8$8$k(B.
\begin{itemize}
\item $BCf4V<0KDD%(B

$h(x_1,\ldots,x_n) \bmod I$ $B$N5U85$r7W;;$9$k>l9g(B,
$B$^$:JQ?t(B $x_n$ $B$K4X$7(B $m_n(x_1,\ldots,x_n)$ $B$H(B
$B3HD%(B Euclid $B8_=|K!$rE,MQ$9$k$H(B, $ah+bm_n=r(x_1,\ldots,x_{n-1})$
$B$H$J$k(B $a$, $b$, $r$ $B$rF@$k(B. $r \bmod I$ $B$N5U85$r(B $s \bmod I$ $B$H$9$l$P(B,
$h \bmod I$ $B$N5U85$O(B $as \bmod I$ $B$H$J$k$,(B, $B7W;;J}K!$K$h$C$F$O(B
$r$ $B$N5U85$,5pBg$K$J$k>l9g$,$"$k(B.

\item $B4JLs2=$H$N4X78(B

$h$ $B$r(B $n-1$ $BJQ?tB?9`<04D>e$N(B 1 $BJQ?tB?9`<0$H8+$J$7$FItJ,=*7k<0(B
$B%"%k%4%j%:%`$rE,MQ$9$l$P(B, $B78?t$N=|;;$O@0=|$H$J$k$,(B, $B$3$l$i$K(B
$B8=$o$l$kJQ?t$KBP$9$k4JLs2=$,9T$o$l$J$$$N$G(B, $B0lHL$KBg$-$JB?9`<0(B
$B$,78?t$K8=$o$l$k(B. $B0lJ}$G(B, $B78?t$N4JLs2=$r5v$;$P(B, $B$=$l$i$rI=8=(B
$B$9$kB?9`<0$,Bg$-$/$J$i$:$K7W;;$G$-$k$,(B, $B=|;;<+?H$,(B
$BBN1i;;$H$J$j(B, $B5U857W;;$,I,MW$H$J$k(B.
\end{itemize}

$B4{$K(B Asir $B$N(B {\tt sp} $B%Q%C%1!<%8$K$*$1$kBe?tBN>e$N0lJQ?tB?9`<0(B
GCD  $B$G$bMQ$$$i$l$F$$$k$h$&$K(B, $BBe?tE*?t$N7W;;$K$O%b%8%e%i!<7W;;$,(B
$BM-8z$G$"$k(B \cite{NORO96}, \cite{HOEI02}.
$B5U85$N%b%8%e%i!<7W;;$K$h$k7W;;K!$H$7$F$O(B, $B<!$N(B 2 $B$D$,M-NO$G$"$k(B.

\begin{itemize}
\item $BCf9q>jM>DjM}(B

$B==J,B?$/$NK!(B $p$ $B$KBP$7(B, $BK!(B $p$ $B$G$N5U85$r7W;;$7$FCf9q>jM>DjM}$K$h$j(B
$B7k9g$7(B, $B@0?t(B-$BM-M}?tJQ49$K$h$j5U85$rF@$kJ}K!$G$"$k(B. $BK!(B $p$ $B$G9M$($k$H(B,
$B78?t4D$,BN$G$O$J$/$J$k$,(B, $BM-8B8D$N(B $p$ $B$r=|$$$FK!(B $p$ $B$G$N5U85$O(B
$B7W;;$G$-$k(B. $B$3$N7W;;$,(B, $B8_=|K!$N$h$&$K(B $O(d^2)$ $B$G7W;;$G$-$k$J$i(B,
1 $B%9%F%C%W$"$?$j(B$O(d^2)$ $B$N<j4V$r(B, $B7k2L$N78?t$NBg$-$5$KHfNc$9$k(B
$B2s?t7+$jJV$9$3$H$G5U85$,7W;;$G$-$k(B.

\item $BL$Dj78?tK!(B + Hensel lifting

$B5U85$rL$Dj78?tK!$K$h$j5a$a$k$3$H$b$G$-$k(B. $B$9$J$o$A(B,
$\bmod I$ $B$G$NC19`<04pDl(B 
$$M=\{x_1^{e_1}\cdots x_n^{e_n} \bmod I \,|\, 0 \le e_i \le d_i-1
(i=1,\ldots,n)\}$$ $B$K$h$j5U85$r(B $u = \sum_{t \in M} a_t t$ $B$HI=$7(B, $hu
\equiv 1 \bmod I$ $B$+$i(B $a_t$ $B$N@~7AJ}Dx<07O$r:n$C$F2r$/J}K!$G$"$k(B. $B$3(B
$B$NJ}K!$O(B, $B3HBg<!?t(B $d=\prod d_i$ $B$K4X$7(B $O(d^3)$ $B$N2rK!$H$J$C$F$7$^$&(B
$B$,(B, $B@~7AJ}Dx<07O$N5a2r$K(B Hensel lifting+$B@0?t(B-$BM-M}?tJQ49$r;H$&$3$H$G(B,
$O(d^3)$ $B$NItJ,$rM-8BBN>e$K$N$_8BDj$G$-$k(B. $B$h$C$F(B, $B$b$77k2L$,Bg$-$$78(B
$B?t$r$b$D>l9g$K$O(B, $B<B:]$N7W;;;~4V$O(B 1 $B%9%F%C%W$"$?$j(B $O(d^2)$ $B$N(B Hensel
lifting $B$K$h$j7hDj$5$l$k(B.  $B$^$?(B, $BCf4V<0$r:n$i$:(B, $\NF_G(th)$ ($t \in
M$) $B$N7W;;$N$_$G@~7AJ}Dx<0$,$G$-$k$3$H$+$i(B, $B>e$G=R$Y$?$h$&$JCf4V<0KDD%(B
$B$dBN=|;;$K$h$kLdBj$O8=$o$l$J$$(B.
\end{itemize}

\section{$BBe?tBN>e$N%0%l%V%J!<4pDl7W;;(B}

\subsection{monic $B2=(B}
Buchberger $B%"%k%4%j%:%`$r$O$8$a$H$9$k%0%l%V%J!<4pDl7W;;%"%k%4%j%:%`$O(B
$BG$0UBN>e$G<B9T2DG=$G$"$k$,(B, $BBN$K$h$C$F$O78?tKDD%$NLdBj$,@8$:$k(B
$B$N$G(B, $B<o!9$NCm0U$,I,MW$H$J$k(B. $F$ $B$,Be?tBN$N>l9g(B, $B78?t$N@Q$N(B
$B4JLs2=(B, $B$*$h$S(B, monic $B2=$K$*$1$kBN=|;;$NLdBj$,$"$j(B, $B>/$/$H$b(B
Risa/Asir $B$K$*$$$F$O(B, $B$3$l$^$GBe?tBN>e$N%0%l%V%J!<4pDl7W;;$O(B
$BDs6!$7$F$3$J$+$C$?(B. $BBe$o$j$K(B, $B<!$K$h$j7W;;$,2DG=$G$"$k(B.
\begin{Th}
$F = \Q[\alpha_1,\ldots,\alpha_l] = \Q[t_1,\ldots,t_l]/I$, $I=\langle m_1(t_1),\ldots,m_l(t_1,\ldots,t_l)\rangle$, $B$H$7(B,
$J =\langle B \rangle \subset R = F[x_1,\ldots,x_n]$
$B$r(B $R$ $B$N??$N%$%G%"%k$H$9$k(B. $<$ $B$r(B $R$ $B$N9`=g=x$H$9$k(B. $R$ $B$N9`=g=x(B $<_F$ $B$r(B $<$ $B$*$h$S(B
$F$ $B$N(B $t_1 < \cdots < t_l$ $B$J$k<-=q<0=g=x$+$i$J$k%V%m%C%/=g=x(B
($t_1^{a_1}\cdots t_l^{a_l} <_F x_1^{b_1}\cdots x_n^{b_n}$) 
$B$H$9$k(B. $B$3$N$H$-(B, $B_F = B \cup \{m_1,\ldots,m_l\}$ $B$N@8@.$9$k%$%G%"%k(B
$B$N(B $<_F$ $B$K4X$9$k(B
$B%0%l%V%J!<4pDl(B $G_F$ $B$N85$N$&$AJQ?t(B $x_1,\ldots,x_n$ $B$r4^$`$b$N$N=89g(B 
$G$ $B$O(B, $J$ $B$N(B $<$ $B$K4X$9$k%0%l%V%J!<4pDl$H$J$k(B. $G_F$ $B$,4JLs(B
$B%0%l%V%J!<4pDl$J$i$P(B, $G$ $B$N85$NF,9`$O(B $t_1,\ldots,t_l$ $B$r4^$^$J$$(B.
\end{Th}
$G_F$ $B$r7W;;$9$k>l9g(B, $B<B:]$N%"%k%4%j%:%`$N<B9T$r4Q;!$9$k$H(B, 
$B@8@.$5$l$kCf4V4pDl$NF,9`$N(B $t$ $BJQ?t$,$@$s$@$s8:$C$F9T$-?k$K>CLG(B
$B$9$k$3$H$,J,$+$k(B. $B$9$J$o$A(B, $BF,9`$N78?t$N5U85$r$+$1$kA`:n$r(B
S-$BB?9`<0$HC19`4JLs$K$h$j9T$C$F$$$k$3$H$K$J$k(B. $B$3$N$3$H$O(B
S-$BB?9`<0$N?t$NA}Bg$r0z$-5/$3$9(B. S-$BB?9`<0$N=hM}$N=g=x$O(B sugar
strategy $B$J$I(B, $B$J$s$i$+$N4p=`$K$h$j5!3#E*$K7h$a$i$l$k$,(B, 
S-$BB?9`<0$,A}$($k$H(B, $BITE,@Z$J=g=x$G=hM}$5$l$k2DG=@-$bA}$((B,
$BITI,MW$J78?tKDD%$r0z$-5/$3$92DG=@-$,$"$k(B. $B$=$3$G(B, $BA0@a$N5U85(B
$B7W;;$rMQ$$$F(B, Buchberger $B%"%k%4%j%:%`$K$*$1$k(B, 0 $B$K4JLs$5$l$J$$(B
$B85$N4pDl$N=hM}$r<!$N$h$&$KJQ99$9$k(B:
\begin{itemize}
\item $BDL>o$N=hM}(B

$S(f,g) \tmred{G} h \neq 0$ $B$J$i$P(B, $G \leftarrow G \cup \{h\}$

\item $BJQ998e$N=hM}(B

$S(f,g) \tmred{G} h(x,t) \neq 0$ $B$J$i$P(B, 
$h(x,\alpha)$ $B$r(B monic $B2=$7$?$b$N(B
$\tilde{h}(x,\alpha)$ $B$r:n$j(B,
$G \leftarrow G \cup \{\tilde{h}(x,t)\}$
\end{itemize}
$B$3$N$h$&$JJQ99$r9T$C$F$b(B $G_F$ $B$,7W;;$G$-$k$3$H$O$"$-$i$+$G(B
$B$"$m$&(B. 

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

monic $B2=$r9T$C$?$H$7$F$b(B, $B<B:]$K$O(B trace $B%"%k%4%j%:%`$rE,MQ$9$k$N$,0B(B
$BA4$G$"$m$&(B. $\bmod p$ $B$G$N(Btrace $B%"%k%4%j%:%`$N@5Ev@-$O(B, $\Q$ $B>e$N4JLs(B
$B2=$K(B $p$ $B$G3d$j@Z$l$kJ,Jl$r$b$DM-M}?t$,8=$o$l$J$$$3$H(B, $B$5$i$K4JLs7k2L(B
$B$N@55,7A$NF,78?t$,(B $p$ $B$G3d$j@Z$l$J$$$3$H$,I,MW$H$J$k(B. $BA0@a$NJQ99$r9T$C(B
$B$?>l9g(B, $B87L)$K$O(B, $BF,78?t$N5U857W;;$K$b(B $p$ $B$G3d$l$kJ,Jl$,8=$o$l$J$$$3(B
$B$H$rMW5a$9$k$3$H$K$J$k$,(B, $B$3$N>r7o$r4K$a$F(B, $B7k2L$r(B monic $B2=$7$?$"$H(B,
$p$ $B$G3d$l$kJ,Jl$,8=$o$l$J$$$3$H(B, $B$H$9$k$3$H$b$G$-$k(B.  $B<B:](B, $B$3$N7k2L(B
$B<+?H$OF~NO%$%G%"%k$N85$G$"$k$3$H$O3N$+$G(B, $B$3$N85$,$"$i$+$8$a%$%G%"%k$N(B
$B@8@.85$N0l$D$G$"$C$?$H9M$($l$P$h$$(B.

trace $B%"%k%4%j%:%`$N<B8=$K$D$$$F$O$$$/$D$+$N%P%j%(!<%7%g%s$,9M$($i$l$k(B.
$B$?$H$($P(B, $\overline{I}=I \bmod p$ $B$,:,4p%$%G%"%k$K$J$k$h$&$J(B $p$ $B$r$H$l$P(B,
$GF(p)[t]/\overline{I}$ $B$,$$$/$D$+$NM-8BBN$ND>OB$KJ,2r$9$k(B. 
$I_p$ $B$r(B, $I$ $B$N78?t$r(B $\Q_{<p>}=\{a/b\,|\, a, b \in Z, p \not{|} b\}$
$B$K@)8B$7$?$b$N$H$7(B, $\phi$ $B$r(B $I_p$ $B$+$i$"$kD>OB@.J,$X$N(B
$B<M1F$H$9$l$P(B, $B$3$l$b(B trace $B%"%k%4%j%:%`$r<B8=$9$k(B. $B$3$l$K$h$j(B,
trace $B$N7W;;$O(B, $BM-8BBN>e$G$NF~NOB?9`<0=89g$N%0%l%V%J!<4pDl7W;;$H(B
$B$J$k$?$a(B, $B7W;;$N<j4V$r8:$i$;$k2DG=@-$,$"$k(B.


\section{Risa/Asir $B>e$G$N<BAu(B}

\subsection{$BC`<!Be?t3HBg(B}

Risa/Asir $B$K$O(B, $BC`<!Be?t3HBg$N85$NI=8=$H$7$F(B, 
$B:F5"I=8=B?9`<0$r%\%G%#It$K$b$D(B {\tt Alg} $B$,$"$j(B, $BBe?tBN>e$N0x?tJ,2r(B
$B$*$h$S:G>.B?9`<07W;;$K4{$KMQ$$$i$l$F$$$k$,(B, $B4JLs7W;;(B, $B5U857W;;$r4^$`(B
$B$[$H$s$I$N4X?t$O(B, {\tt sp} $BCf$K%f!<%64X?t$H$7$F(B
$B=q$+$l$F$$$F9b8zN($OK>$a$J$$(B. $BFC$K(B, $B4{$K=R$Y$?$h$&$J(B, $BC19`4JLs(B
$B$K$h$k4JLs$r9T$&$N$K$OE,$7$F$$$J$$$?$a(B, $BJ,;6I=8=B?9`<0$r%\%G%#It(B
$B$K$b$DC`<!Be?t3HBg$NI=8=$r?7$?$KDj5A$7$?(B.
\begin{verbatim}
typedef struct oDAlg {
        short id;
        char nid;
        char pad;
        struct oDP *nm;
        struct oQ *dn;
} *DAlg;
\end{verbatim}
{\tt DAlg} $B$O%\%G%#It$H$7$F(B, $BJ,;6I=8=B?9`<0$G$"$k(B {\tt nm} $B$*$h$S(B 
$BM-M}?t$G$"$k(B {\tt dn} $B$r$b$D(B.
$BBe?tE*?t$H$7$F$O(B {\tt nm/dn} $B$rI=$9$,(B, {\tt nm} $B$O@0?t78?t$N(B
$BJ,;6I=8=B?9`<0(B, {\tt dn} $B$O@0?t$K8BDj$9$k(B. $B$9$J$o$A(B,
$B%\%G%#It$NM-M}?t78?t$rDLJ,$7$FI=<($9$k$HLsB+$9$k$N$G$"$k(B.
$B$^$?(B, $B78?tBN$G$"$kC`<!3HBgBN$r(B, $B$=$l$r@8@.$9$kBe?tE*?t$N%j%9%H(B
$B$G;XDj$9$k4X?t(B {\tt set\_field()} $B$rMQ0U$7$?(B. $B$3$N8F$S=P$7(B
$B$K$h$j(B, $B4JLs7W;;(B, $B5U857W;;$KI,MW$J(B, $B:G>.B?9`<0%j%9%H$d(B
$BC19`<04pDl$,7W;;$5$l(B, $BFbItE*$K78?tBN>pJs$H$7$F%;%C%H(B
$B$5$l$k(B. 

{\tt DAlg} $B7?$N%*%V%8%'%/%H$O(B, {\tt Alg} $B7?$+$i$NJQ494X?t(B
{\tt algtodalg()} $B$K$h$j@8@.$5$l$k(B. $B$=$N5UJQ49$O(B {\tt dalgtoalg()}
$B$G$"$k(B. 

\subsection{$B%0%l%V%J!<4pDl7W;;(B}

$B8=:_$N;n83E*<BAu$O(B, {\tt nd\_gr} $B$*$h$S(B {\tt nd\_gr\_trace} $B$r(B, $BF~NOB?(B
$B9`<0=89g$K:G>.B?9`<0$rDI2C$7$F<B9T$7(B, $BA0@a$G=R$Y$?$h$&$JJQ99(B (monic $B2=(B) 
$B$r2C$($k(B, $B$H$$$&7A$G9T$C$F$$$k(B. $BF~NO$O(B, {\tt Alg} $B7?$r78?t$K4^$`(B
$BB?9`<0=89g$G$h$$(B. $BNc$($P(B $\langle \sqrt{2}x^2+(\sqrt{2}+\sqrt{3})xy+\sqrt{3}y^2-\sqrt{3},(\sqrt{2}-2\sqrt{3})x^2+2\sqrt{3}xy+2\sqrt{2}x^2+\sqrt{2}+\sqrt{3}\rangle$ $B$N<-=q<0=g=x%0%l%V%J!<4pDl$N7W;;$O<!$N$h$&$K$9$l$P$h$$(B.
\begin{verbatim}
[0] S2=newalg(x^2-2);
(#0)
[1] S3=newalg(x^2-3);
(#1)
[2] F1=S2*x^2+(S2+S3)*x*y+S3*y^2-S3$
F2=(S2-2*S3)*x^2+2*S3*x*y+2*S2*x^2+S2+S3]$
[3] nd_gr_trace([F1,F2],[x,y],1,1,2);
[90*y^4+(-21*#0*#1-246)*y^2+(16*#0*#1+144),
20*x+(15*#0*#1-60)*y^3+(-7*#0*#1+83)*y]
\end{verbatim}
$BFbItE*$K$O(B, $BBe?tE*?t$O(B, $B85$NB?9`<0JQ?t$HF1Ey$K07$o$l(B, $B@55,2=7W;;$OM-M}?tBN(B
$B>e$G9T$o$l$k(B. monic $B2=$N:]$K$N$_(B, $BK\Mh$N78?t$,Be?tE*?t(B ({\tt DAlg $B7?(B}) $B$H(B
$B$7$F<h$j=P$5$l(B, $B5U857W;;$J$I$,9T$o$l$k(B.
$B$3$l$KBP$7(B, $BBe?tE*?t$r40A4$K78?t$K<h$j(B
$B9~$s$G(B, $B78?t$K4X$7$F4{$K=R$Y$?$h$&$J4JLs2=$*$h$S5U857W;;$r9T$&$H$$$&J}(B
$BK!$b9M$($i$l$k(B. $BA0<T$N>l9g(B, $B4JLs2=$,(B $\Q$ $B>e$G9T$o$l$k$N$G(B, $B4{$K<BAu$7(B
$B$F$"$k(B, $B78?t$N(B content $B=|5n$,<+F0E*$KE,MQ$5$l$k(B.  sugar $BCM$K(B, $BBe?tE*?t(B
$B$N<!?t$,H?1G$5$l$k$N$rKI$0$?$a(B, $BBe?tE*?t$KBP1~$9$k(Bweight $B$r(B 0 $B$K@_Dj$7(B
$B$F$$$k(B.  $B$7$+$7(B, $B@F<!2=$K$D$$$F$OIT<+A3$J<BAu$r$;$6$k$rF@$J$$(B.  $B8e<T$O(B
$B<+A3$J<BAu$H$b8@$($k$,(B, content $B=|5n$KAjEv$9$kJ}K!$r?7$?$K9M0F$9$kI,MW(B
$B$,$"$j(B, $B:#8e$N2]Bj$H$7$?(B.

\section{$B%?%$%_%s%0%G!<%?(B}

$B0J2<(B, $BFC$KCG$i$J$$8B$j(B, $B9`=g=x$O(B DRL $B$H$9$k(B.
\begin{Exp}\rm
\label{exp:c7}
\begin{eqnarray*}
Cyc&=&\{f_1,f_2,f_3,f_4,f_5,f_6,f_7\}\\
f_1&=&\omega c_5c_4c_3c_2c_1c_0-1\\
f_2&=&(((((c_5+\omega )c_4+\omega c_5)c_3+\omega c_5c_4)c_2+\omega c_5c_4c_3)c_1+\omega c_5c_4c_3c_2)c_0+\omega c_5c_4c_3c_2c_1\\
f_3&=&((((c_4+\omega )c_3+\omega c_5)c_2+\omega c_5c_4)c_1+\omega c_5c_4c_3)c_0+c_5c_4c_3c_2c_1+\omega c_5c_4c_3c_2\\
f_4&=&(((c_3+\omega )c_2+\omega c_5)c_1+\omega c_5c_4)c_0+c_4c_3c_2c_1+c_5c_4c_3c_2+\omega c_5c_4c_3\\
f_5&=&((c_2+\omega )c_1+\omega c_5)c_0+c_3c_2c_1+c_4c_3c_2+c_5c_4c_3+\omega c_5c_4\\
f_6&=&(c_1+\omega )c_0+c_2c_1+c_3c_2+c_4c_3+c_5c_4+\omega c_5\\
f_7&=&c_0+c_1+c_2+c_3+c_4+c_5+\omega
\end{eqnarray*}

$Cyc$ $B$O(B, cyclic-7 $B$K$*$$$F(B, $c_6$ $B$r(B 1 $B$N86;O(B 7 $B>h:,(B
$\omega$ $B$KCV$-49$($?$b$N$G$"$k(B. $Cyc$ $B$N(B $\Q(\omega)$ $B>e$G$N(B
$B%0%l%V%J!<4pDl7W;;$O(B, $B@F<!2=(B trace $B%"%k%4%j%:%`$K$h$j(B 22 $BIC(B
$B$G7W;;$G$-$k(B. $B$3$N$&$A(B, monic $B2=$N7W;;;~4V$O(B 2.2 $BIC(B, $B$=$N$&$A(B
$B5U857W;;$O(B 0.2$BIC(B $B$G$"$k(B.

$\omega$ $B$N:G>.B?9`<0$rE:2C$7$F(B $\Q$ $B>e$G(B
$B7W;;$9$k>l9g(B 220 $BIC$+$+$k(B. 
\end{Exp}

\begin{Exp}\rm
\label{exp:cap}
\begin{eqnarray*}
Cap&=&\{f_1,f_2,f_3,f_4\}\\
f_1&=&(2ty-2)x-(\alpha+\beta)zy^2-z\\
f_2&=&2\beta\alpha^4zx^3+(4ty+\beta)x^2+(4zy^2+4z)x+2ty^3-10y^2-10ty+2\alpha^2+\beta^2\\
f_3&=&(t^2-1)x+(\beta\alpha^4+\beta^3\alpha^3)tzy-2z\\
f_4&=&(-z^2+4t^2+\beta\alpha+2\beta^3)zx+(4tz^2+2t^3-10t)y+4z^2-10t^2+\beta\alpha^3\\
m_1&=&u^7-7u+3\\
m_2&=&u^6+\alpha u^5+\alpha^2u^4+\alpha^3u^3+\alpha^4u^2+\alpha^5u+\alpha^6-7
\end{eqnarray*}
$Cap$ $B$O(B $Caprasse$ \cite{SYMBDATA} 
$B$N78?t$r%i%s%@%`$KBe?tE*?t$KCV$-49$($?(B
$B$b$N$G$"$k(B. $\alpha$, $\beta$ $B$O(B $t^7-7t+3$ $B$N(B 2 $B:,$G(B,
$\alpha$ $B$N(B $\Q$$B>e$N:G>.B?9`<0$,(B $m_1(u)$, $\beta$ $B$N(B $\Q(\alpha)$
$B>e$N:G>.B?9`<0$,(B $m_2(u)$ $B$G$"$k(B. $Cap$ $B$N(B $\Q(\alpha,\beta)$ $B>e(B
$B$G$N%0%l%V%J!<4pDl7W;;$O(B trace $B%"%k%4%j%:%`$G(B 589 $BIC(B ($BFb(B monic $B2=(B 36 $BIC(B),
$\Q$ $B>e$G$O@F<!2=$7$F$b(B, 1 $B;~4VBT$C$F$b=*N;$7$J$$(B.
\end{Exp}

\begin{Exp} \rm
$BNc(B \ref{exp:degree7} $B$GDj5A$5$l$k(B $F$ $B$O(B, $f(x)=x^7-7x+3$ $B$N:G>.J,2rBN(B
$B$G$"$k(B. $f(x)$ $B$N(B $F$ $B>e0x?tJ,2r$K8=$l$k(B, $F$ $B>e$N(B 2 $B$D$N(B 2 $B<!<0$N(B
GCD $B7W;;(B (GCD $B$O(B 1 $B<!<0(B) $B$r(B $F$ $B>e$N%0%l%V%J!<4pDl7W;;$K$h$j9T$&$H(B,
0.8 $BIC$G=*N;$9$k(B. $B5U857W;;(B 1 $B2sJ,$,7W;;;~4V$NBgItJ,$r@j$a$k(B. $B0lJ}(B,
$B$3$l$r(B $\Q$ $B>e$G9T$&$H(B, 60 $BIC$+$+$k(B.
\end{Exp}
	
\section{$B$*$o$j$K(B}
$BK\9F$GDs0F$7$?J}K!$K$h$j(B, $BBe?tBN>e$N%0%l%V%J!<4pDl7W;;$,(B, $BC1$K:G>.B?9`(B
$B<0$rE:2C$7$FM-M}?tBN>e$G7W;;$9$k$h$j9bB.$K7W;;$G$-$k>l9g$,$"$k$3$H$,<((B
$B$;$?(B.  $B$7$+$7(B, $B$3$N$h$&$J7W;;$,:$Fq$G$"$k$3$H$K$OJQ$o$j$J$$(B. $B$h$jK\<A(B
$BE*$J2~NI(B, $B?7%"%k%4%j%:%`$bI,MW$G$"$m$&(B.

$B:#8e$NM=Dj$H$7$F0J2<$r5s$2$F$*$/(B.
\begin{itemize}
\item DCGB $B$H$N4X78(B

$B:4F#$i(B \cite{SATO} $B$K$h$k(B DCGB $B$b(B, $BF1MM$KBe?tBN>e$N%0%l%V%J!<(B
$B4pDl$rM?$($k(B. $B$3$NJ}K!$H$NHf3S$O6=L#$"$kOCBj$G$"$m$&(B.

\item change of ordering, RUR 

$B<B:]$N5a2r$KI,MW$K$J$k(B, FGLM $B$d(B RUR $B$N7W;;$rBe?tBN>e$K(B
$B3HD%$9$k$3$H$OI,MW$G$"$m$&(B. $B$3$N>l9g$K$b(B, $B@~7AJ}Dx<05a2r$r(B
$BBe?tBN>e$G9T$&$+(B, $BM-M}?tBN>e$G9T$&$+$NA*Br$,@8$:$k(B. $B$3$l$i$N(B
$BHf3S$b:#8e$N2]Bj$G$"$k(B.

\item $BBe?tBN1i;;$N<BAu$N8zN(2=(B

$B:#2s$N<BAu$G$O(B, $BBe?tBN$NI=8=$H$7$F(B, Asir $B5lMh$NJ,;6B?9`<07?$G$"$k(B
{\tt DP} $B$rMQ$$$?(B. $B$3$l$O(B, {\tt nd} $B7O4X?t$,8=>u$G$O:FF~IT2D$G$"$k(B
$B$H$$$&$N$,<g$JM}M3$G$"$C$?(B. {\tt nd} $B$N3+H/F05!$,(B {\tt DP} $B7?$N(B
$B7W;;8zN($X$NITK~$G$"$C$?$3$H$r9M$($l$P(B, $B$3$NItJ,$N2~NI$O0UL#$,$"$k(B.
$BFC$K(B, triangular form $B$K$h$k4JLs2=$KFC2=$7$?%G!<%?7?$*$h$S4X?t(B
$B$r=q$/$3$H$K$h$j(B, $B$h$j0lAX$N8zN(2=$,C#@.$G$-$k$G$"$m$&(B.
\end{itemize}



\begin{thebibliography}{99}
\bibitem{HOEI02}
M.v. Hoeij, M. Monagan, A Modular GCD algorithm over Number Fields presented with Multiple Extensions. Proc. ISSAC'02 (2002), 109-116.

\bibitem{NORO96}
$BLnO$(B, $BC`<!Be?t3HBgBN>e$G$N(B 1 $BJQ?tB?9`<0$N(B GCD $B$K$D$$$F(B. $B?tM}8&9V5fO?(B 920 (1996), 1-8.

\bibitem{SATO}
Y. Sato, A. Suzuki,  Discrete Comprehensive Gr\"obner Bases.
Proc. ISSAC'01 (2001), 292-296.

\bibitem{SYMBDATA}
SymbolicData. {\tt http://www.SymbolicData.org}.
\end{thebibliography}
\end{document}