Return to rims2004-noro-ohp.tex CVS log

Up to [local] / OpenXM / doc / Papers

Annotation of OpenXM/doc/Papers/rims2004-noro-ohp.tex, Revision 1.2

1.1       noro        1: \documentclass{slides}
                      2: %\documentclass[pdf,distiller,slideColor,colorBG,azure]{prosper}
                      3: \usepackage{color}
                      4: \usepackage{rgb}
                      5: \usepackage{graphicx}
                      6: \usepackage{epsfig}
                      7: \newcommand{\qed}{$\Box$}
                      8: \newcommand{\mred}[1]{\smash{\mathop{\hbox{\rightarrowfill}}\limits_{\scriptstyle #1}}}
                      9: \newcommand{\tmred}[1]{\smash{\mathop{\hbox{\rightarrowfill}}\limits_{\scriptstyle #1}\limits^{\scriptstyle *}}}
                     10: \newtheorem{prop}{\redc $BL?Bj(B}
                     11: \def\gr{Gr\"obner basis }
                     12: \def\st{\, s.t. \,}
                     13: \def\ni{\noindent}
                     14: \def\init{{\rm in}}
                     15: \def\Q{{\bf Q}}
                     16: \def\Z{{\bf Z}}
                     17: \def\Spoly{{\rm Spoly}}
                     18: \def\Span{{\rm Span}}
                     19: \def\Supp{{\rm Supp}}
                     20: \def\StdMono{{\rm StdMono}}
                     21: \def\Im{{\rm Im}}
                     22: \def\Ker{{\rm Ker}}
                     23: \def\NF{{\rm NF}}
                     24: \def\HT{{\rm HT}}
                     25: \def\LT{{\rm LT}}
                     26: \def\ini{{\rm in}}
                     27: \def\rem{{\rm rem}}
                     28: \def\Id#1{\langle #1 \rangle}
                     29: \def\ve{\vfill\eject}
                     30: \textwidth 9.2in
                     31: \textheight 7.2in
                     32: \columnsep 0.33in
                     33: \topmargin -1in
                     34: \def\tc{\color{orange}}
                     35: \def\fbc{\bf\color{orange}}
                     36: %\def\itc{\color{LimeGreen}}
                     37: \def\itc{\color{DarkGreen}}
                     38: %\def\urlc{\bf\color{DarkGreen}}
                     39: \def\urlc{\bf\color{LimeGreen}}
                     40: \def\goldc{\color{goldenrod3}}
                     41: \def\redc{\color{orange}}
                     42: \def\vs{\vskip 1cm}
                     43: \def\vsh{\vskip 0.5cm}
                     44: \def\ns{\itc\LARGE}
                     45: \title{\tc\bf\ns $BBe?tBN>e$N%$%G%"%k$N%0%l%V%J!<4pDl7W;;$K$D$$$F(B}
                     46:
                     47: %\slideCaption{$BBe?tBN>e$N%$%G%"%k$N%0%l%V%J!<4pDl7W;;$K$D$$$F(B}
                     48: \author{{\bf\Large $BLnO$(B $B@59T(B\\ $B?@8MBg3XM}3XIt(B}}
                     49: \date{\bf\Large Dec. 16, 2004}
                     50: \begin{document}
                     51: \setlength{\parskip}{20pt}
                     52: \maketitle
                     53:
                     54: %\itc: item color
                     55: %\fbc: fbox color
                     56: %\urlc: URL color
                     57: %\goldc: bold color a
                     58: %\redc: bold color b
                     59:
                     60: \large
                     61: \bf
                     62: \setlength{\parskip}{0pt}
                     63:
                     64: \begin{slide}{\ns $BBe?tBN$N85$NI=8=J}K!(B}
                     65:
                     66: $B86;O85$K$h$kI=8=$O2DG=(B : $F=\Q[t]/(m(t))$
                     67: $\Rightarrow$ $B78?t$NA}Bg$r>7$/(B
                     68: $\Rightarrow$ $BC`<!3HBg$,8=<BE*(B
                     69: $$F_0=\Q,\quad F_i = F_{i-1}(\alpha_i)\quad (i=1,\ldots,n),\quad F=F_m$$
                     70: $m_i(t,\alpha_1,\ldots,\alpha_{i-1})$ : $\alpha_i$ $B$N:G>.B?9`<0(B $/F_{i-1}$
                     71:
                     72: $m_i$ $B$N4{Ls@-%A%'%C%/$O$+$D$F:$Fq(B
                     73: $\Rightarrow$ knapsack factorization $B$K$h$j$=$&$G$b$J$/$J$C$?(B. $B0J2<(B,
                     74: $$I=\langle m_1(x_1),m_2(x_1,x_2),\ldots,m_n(x_1,\ldots,x_n)\rangle$$
                     75: $B$G(B, $I$ $B$,(B $\Q[X]=\Q[x_1,\ldots,x_n]$ $B$N6KBg%$%G%"%k$H$9$k(B.
                     76: \end{slide}
                     77:
                     78: \begin{slide}{\ns $BBe?tE*?t$N4JLs(B}
                     79:
                     80: $m_i$ : $B<gJQ?t(B $x_i$ $B$K4X$9$k<g78?t$OM-M}?t$H$7$F$h$$(B.
                     81: $\Rightarrow$
                     82: $G=\{m_1,\ldots,m_n\}$ $B$O(B,
                     83: $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(B.
                     84:
                     85: $h(x) \bmod I \in Q[X]/I$ $B$KBP$7(B,
                     86:
                     87: $h_0 \equiv h \bmod I$, $\deg_{x_i}(h_0) < d_i$
                     88: $\Rightarrow$ $h=h\NF_G(h)$
                     89:
                     90: $h_0=\rem_{x_1}(\rem_{x_2}(\cdots \rem_{x_n}(h,m_n)\cdots),m_2),m_1)$
                     91:
                     92: $B$G$b$"$k$,(B, \underline{$B$3$N=g$G7W;;$7$F$O$$$1$J$$(B!!}
                     93:
                     94: ($f(a) \bmod b$ $B$r(B $c=f(a)$ $\Rightarrow$ $c \bmod b$ $B$H7W;;$9$k$h$&$J$b$N(B)
                     95: \end{slide}
                     96:
                     97: \begin{slide}{\ns $BC19`4JLs$K$h$kBe?tE*?t$N4JLs(B}
                     98:
                     99: $B$+$H$$$C$F(B, $B=g=x$rJQ$($l$P$h$$(B, $B$H$$$&$o$1$G$b$J$$(B
                    100:
                    101: \underline{$BB?9`<0>jM><+BN$,4m81(B} : $BB>$NJQ?t$N<!?t$,5^$K>e$,$k(B
                    102:
                    103: $\Rightarrow$ $G$ $B$K$h$kC19`4JLs$rMQ$$$k(B
                    104:
                    105: $B3F4JLs%9%F%C%W$KMQ$$$k(B $m_i$ : $i$ $B$N>.$5$$$b$NM%@h(B
                    106: \end{slide}
                    107:
                    108: \begin{slide}{\ns $B4JLs$NNc(B}
                    109:
                    110: $m_1(x_1)=x_1^7-7x_1+3$,\\
                    111: $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+\cdots$\\
                    112: $m_3(x_1,x_2,x_3)=63x_3^4+\cdots$
                    113:
                    114: $B$GDj5A$5$l$k(B $F=\Q(\alpha_1,\alpha_2,\alpha_3)$ $B$O(B $m_1(x_1)$ $B$N(B
                    115: $B:G>.J,2rBN(B.
                    116:
                    117: $(\alpha_1+\alpha_2+\alpha_3)^{20}$ $B$N4JLs(B
                    118:
                    119: $i$ $B$,>.$5$$(B $m_i$ $BM%@h$G4JLs(B : 0.1 $BIC(B
                    120:
                    121: $i$ $B$,Bg$-$$(B $m_i$ $BM%@h$G4JLs(B : 260 $BIC(B
                    122: \end{slide}
                    123:
                    124: \begin{slide}{\ns $B5U857W;;(B}
                    125:
                    126: $B5U857W;;$O%\%H%k%M%C%/$N0l$D(B
                    127:
                    128: $B3HBg<!?t$r(B $d$ $B$H$9$k(B.
                    129:
                    130: $BC13HBg(B $\Rightarrow$ $O(d^2)$ ($B3HD%(B Euclid $B8_=|K!(B)
                    131:
                    132: $BC`<!3HBg$K$b:F5"E*$KE,MQ2DG=(B
                    133:
                    134: $h(x_1,\ldots,x_n) \bmod I$ $B$N5U85$r7W;;(B
                    135:
                    136: $x_n$ $B$K4X$7(B $h$, $m_n$ $B$K3HD%(B Euclid $B8_=|K!$rE,MQ$9$k(B
                    137:
                    138: $\Rightarrow$ $\exists a,\exists b, \exists r$, $ah+bm_n=r(x_1,\ldots,x_{n-1})$
                    139:
                    140: $\Rightarrow$ $r$ $B$N5U85$r7W;;$9$l$P(B, $h$ $B$N5U85$,5a$^$k(B
                    141: \end{slide}
                    142:
                    143: \begin{slide}{\ns $B$3$NJ}K!$NLdBjE@(B}
                    144:
                    145: \begin{itemize}
                    146: \item $BCf4V<0KDD%(B
                    147:
                    148: $B:G=*7k2L$KHf3S$7$F(B, $r$ $B$N5U85$,5pBg$K$J$k>l9g$,$"$k(B.
                    149: ($B7W;;J}K!$K0MB8(B)
                    150:
                    151: \item $B4JLs2=$H$N4X78(B ($BItJ,=*7k<0;;K!$r;H$&>l9g(B)
                    152:
                    153: \begin{itemize}
                    154: \item $h \in (\Q[x_1,\ldots,x_{n-1}])[x_n]$ $B$H8+$J$9(B
                    155:
                    156: $B78?t$N=|;;$OB?9`<0$N@0=|$H$J$k$,(B, $B$3$l$i$K(B
                    157: $B8=$o$l$kJQ?t$KBP$9$k4JLs2=$,9T$o$l$J$$$N$G(B, $B0lHL$KBg$-$JB?9`<0(B
                    158: $B$,78?t$K8=$o$l$k(B.
                    159:
1.2     ! noro      160: \item $h\in (\Q(\alpha_1,\ldots,\alpha_{n-1}))[x_n]$ $B$H8+$J$9(B
1.1       noro      161:
                    162: $B78?t=|;;$,BN1i;;$H$J$j(B, $B5U857W;;$,I,MW$H$J$k(B.
                    163: \end{itemize}
                    164: \end{itemize}
                    165: \end{slide}
                    166:
                    167: \begin{slide}{\ns $B%b%8%e%i!<7W;;$K$h$k5U857W;;(B}
                    168:
                    169: $BBe?tE*?t$N7W;;$K$O%b%8%e%i!<7W;;$,M-8z(B
                    170:
1.2     ! noro      171: ([NORO96], [HOEIJ02]).
1.1       noro      172:
                    173: \begin{itemize}
                    174: \item $BCf9q>jM>DjM}(B
                    175:
                    176: $B==J,B?$/$NK!(B $p$ $B$KBP$7(B, $BK!(B $p$ $B$G$N5U85$r7W;;(B
                    177:
                    178: $BCf9q>jM>DjM}(B,  $B@0?t(B-$BM-M}?tJQ49$K$h$j5U85$rF@$k(B
                    179:
                    180: $BM-8B8D$N(B $p$ $B$r=|$$$FK!(B $p$ $B$G$N5U85$O7W;;$G$-$k(B.
                    181:
                    182: \item $BL$Dj78?tK!(B
                    183: $$M=\{x_1^{e_1}\cdots x_n^{e_n} \bmod I \,|\, 0 \le e_i \le d_i-1
                    184: (i=1,\ldots,n)\}$$ $B$K$h$j5U85$r(B $u = \sum_{t \in M} a_t t$ $B$HI=$7(B, $hu
                    185: \equiv 1 \bmod I$ $B$+$i(B $a_t$ $B$N@~7AJ}Dx<07O$r:n$C$F2r$/(B
                    186: \end{itemize}
                    187: \end{slide}
                    188:
                    189: \begin{slide}{\ns $BL$Dj78?tK!(B + Hensel lifting}
                    190:
                    191: $BL$Dj78?tK!(B $B$O(B $O(d^3)$ $B$@$,(B, $B@~7AJ}Dx<07O$r(B Hensel lifting+$B@0?t(B-$BM-M}?tJQ49(B
                    192: $B$G2r$1$k(B
                    193:
                    194: $\Rightarrow$
                    195:
                    196: \begin{itemize}
                    197: \item $O(d^3)$ $B$OM-8BBN>e$N(B LU $BJ,2r$N$_(B
                    198:
                    199: $B7k2L$,Bg$-$$78?t$r$b$D$J$i$P(B, $B7W;;;~4V$O(B
                    200: Hensel lifting (1 step $B$"$?$j(B $O(d^2)$) $B$,(B dominant
                    201:
                    202: \item $\NF_G(th)$ ($t \in M$) $B$N7W;;$N$_$G@~7AJ}Dx<0$,$G$-$k(B
                    203:
                    204: $BCf4V<0KDD%$dBN=|;;$K$h$kLdBj$O8=$o$l$J$$(B.
                    205: \end{itemize}
                    206: \end{slide}
                    207:
                    208: \begin{slide}{\ns $BBe?tBN>e$N%0%l%V%J!<4pDl7W;;(B}
                    209:
                    210: \underline{$BDjM}(B}
                    211:
1.2     ! noro      212: $F = \Q[\alpha_1,\ldots,\alpha_l] = \Q[T]/I$  ($T=\{t_1,\ldots,t_l\}$)
1.1       noro      213:
                    214: $I=\langle m_1(t_1),\ldots,m_l(t_1,\ldots,t_l)\rangle$
                    215:
                    216: $J =\langle B \rangle \subset R = F[x_1,\ldots,x_n]$ : $R$ $B$N??$N%$%G%"%k(B
                    217:
                    218: $<$ : $R$ $B$N9`=g=x(B
                    219:
                    220: $<_F$ : $\Q[X]$ $B>e$G(B $<$ $B$KEy$7$/(B, $X >> T$ $B$G$"$k%V%m%C%/=g=x(B
                    221:
                    222: $B_F = B \cup \{m_1,\ldots,m_l\}$
                    223:
                    224: $G_F = \langle B_F\rangle$ $B$N(B  $<_F$ $B$K4X$9$k%0%l%V%J!<4pDl(B
                    225:
                    226: $\Rightarrow$ $G=(G_F \setminus \Q[T]) \bmod I$ $B$O(B $J$ $B$N(B $<$ $B$K4X$9$k%0%l%V%J!<4pDl(B
                    227: \end{slide}
                    228:
                    229: \begin{slide}{\ns monic $B2=$N$?$a$K(B S-$BB?9`<0$,A}$($k(B}
                    230:
                    231: $BDjM}$K$h$j(B, $F$ $B>e$N%0%l%V%J!<4pDl7W;;$O(B $\Q$ $B>e$N$=$l$K5"Ce(B
                    232:
1.2     ! noro      233: $B<B9T$r4Q;!$9$k$H(B, $B@8@.$5$l$kCf4V4pDl$NF,9`$N(B $t$ $BJQ?t$,$@$s$@$s>CLG(B
        !           234:
        !           235: $\Rightarrow$ $BF,78?t$N5U857W;;$r(B S-$BB?9`<0$HC19`4JLs$G<B9T(B
1.1       noro      236:
                    237: $\Rightarrow$ S-$BB?9`<0$N?t$,A}Bg$7$F$$$k(B
                    238:
                    239: $BJ@32(B : $BITE,@Z$J=g=x$G(B S-$BB?9`<0$,=hM}$5$l$k2DG=@-$bA}$($k(B.
                    240:  ($BITI,MW$J78?tKDD%$N2DG=@-(B)
                    241: \end{slide}
                    242:
                    243: \begin{slide}{\ns $B@55,7A$r(B monic $B2=(B}
                    244:
                    245: \begin{itemize}
                    246: \item $BDL>o$N=hM}(B
                    247:
                    248: $S(f,g) \tmred{G} h \neq 0$ $B$J$i$P(B, $G \leftarrow G \cup \{h\}$
                    249:
                    250: \item $BJQ998e$N=hM}(B
                    251:
                    252: $S(f,g) \tmred{G} h(x,t) \neq 0$ $B$J$i$P(B,
                    253: $h(x,\alpha)$ $B$r(B monic $B2=$7$?$b$N(B
                    254: $\tilde{h}(x,\alpha)$ $B$r:n$j(B,
                    255: $G \leftarrow G \cup \{\tilde{h}(x,t)\}$
                    256: \end{itemize}
                    257:
                    258: $B$3$N$h$&$JJQ99$r9T$C$F$b(B $G_F$ $B$,7W;;$G$-$k$3$H$O$"$-$i$+(B
                    259:
                    260: \end{slide}
                    261:
                    262: \begin{slide}{\ns trace $B%"%k%4%j%:%`(B}
                    263:
                    264: $\bmod p$ $B$G$N(Btrace $B%"%k%4%j%:%`$NB39T$KI,MW$J$3$H(B
                    265:
                    266: \begin{itemize}
                    267: \item $\cdots$ $\Q$ $B>e$N4JLs2=$K$"$i$o$l$kJ,Jl$,(B $p$ $B$G3d$j@Z$l$J$$(B
                    268:
                    269: \item $B@55,7A$NF,78?t$,(B $p$ $B$G3d$j@Z$l$J$$(B
                    270: \end{itemize}
                    271:
                    272: $\Rightarrow$ monic $B2=$K(B $p$ $B$G3d$l$kJ,Jl$,$"$i$o$l$J$$(B, $B$H4K$a$i$l$k(B
                    273:
                    274: ($B$"$i$+$8$a%$%G%"%k$N@8@.85$N0l$D$G$"$C$?$H9M$($l$P$h$$(B)
                    275:
                    276: \underline{$BB>$N<B8=J}K!(B}
                    277:
                    278: $\overline{I}=I \bmod p$ $B$,:,4p%$%G%"%k(B
                    279:
                    280: $\Rightarrow$ $GF(p)[t]/\overline{I}$ $B$OM-8BBN$ND>OB(B
                    281:
                    282: $I_p$ : $I$ $B$N78?t$r(B $\Q_{<p>}=\{a/b\,|\, a, b \in Z, p \not{|} b\}$
                    283: $B$K@)8B(B
                    284:
                    285: $\phi$ : $I_p$ $B$+$i$"$kD>OB@.J,$X$N<M1F(B
                    286:
                    287: $B$H$7$F$b$h$$(B
                    288:
                    289: $\Rightarrow$ $BM-8BBN>e$N(B trace $B7W;;$N<j4V$r8:$i$;$k2DG=@-$,$"$k(B.
                    290: \end{slide}
                    291:
                    292: \begin{slide}{\ns Risa/Asir $B>e$G$N<BAu(B : $BC`<!Be?t3HBg(B}
                    293:
                    294: {\tt Alg} : $B%\%G%#It$,:F5"I=8=B?9`<0(B ($B4{B8(B)
                    295:
                    296: {\tt DAlg} : $B%\%G%#It$,J,;6I=8=B?9`<0(B ($B?75,(B) -- Alg $B$+$iJQ49(B
                    297: \begin{verbatim}
                    298: typedef struct oDAlg {
                    299:         short id;
                    300:         char nid;
                    301:         char pad;
                    302:         struct oDP *nm;  /* $B<B:]$K$O@0?t78?t(B */
                    303:         struct oQ *dn;   /* $B<B:]$K$O@0?t(B */
                    304: } *DAlg;
                    305: \end{verbatim}
                    306: $BBe?tE*?t$H$7$F$O(B {\tt nm/dn} : $BJ,Jl$rDLJ,$7$F(B {\tt dn} $B$H$9$k(B.
                    307:
                    308: $BB>$K(B, $B4JLsMQ$K3HBgBN%G!<%?$r9=B$BN$H$7$FJ];}(B
                    309:
                    310: {\tt set\_field()} $B$G@_Dj$G$-$k(B.
                    311: \end{slide}
                    312:
                    313: \begin{slide}{\ns Risa/Asir $B>e$G$N<BAu(B : $B%0%l%V%J!<4pDl7W;;(B}
                    314:
                    315: \begin{itemize}
                    316: \item {\tt nd\_gr} $B$*$h$S(B {\tt nd\_gr\_trace} $B$r2~B$(B
                    317:
1.2     ! noro      318: $BF~NO(B + $B:G>.B?9`<0$KBP$7<B9T(B + $B@55,7A$N(B monic $B2=(B
        !           319:
        !           320: $BF~NO$O(B {\tt Alg} $B7?$r78?t$K4^$s$G$h$$(B ($BMW(B monic $B2=(B)
1.1       noro      321:
                    322: \item $BFbItI=8=(B
                    323:
                    324: $BBe?tE*?t$O(B, $B85$NB?9`<0JQ?t$HF1Ey(B, $B@55,2=7W;;$OM-M}?tBN>e$G(B
                    325: $\Rightarrow$ $B78?t$N(B content $B=|5n$,<+F0E*$KE,MQ$5$l$k(B.
                    326:
                    327: \item monic $B2=(B
                    328:
1.2     ! noro      329: monic $B2=$N:]$K$N$_(B, $BK\Mh$N78?t$,Be?tE*?t(B ({\tt DAlg}$B7?(B) $B$H(B
1.1       noro      330: $B$7$F<h$j=P$5$l(B, $B5U857W;;$J$I$,9T$o$l$k(B.
                    331:
                    332: \item weight
                    333:
                    334: $BBe?tE*?t$KBP1~$9$k(Bweight $B$r(B 0 $B$K@_Dj(B $\Rightarrow$ sugar $B$r(B
                    335: $BE,@5$K$9$k$?$a(B
                    336: \end{itemize}
                    337: \end{slide}
                    338:
                    339: \begin{slide}{\ns $BB>$N<BAuK!(B}
                    340:
                    341: \underline{$BBe?tE*?t$r40A4$K78?t$H$7$F07$&(B}
                    342:
                    343: $B78?t$K4X$7$F4JLs2=$*$h$S5U857W;;$r9T$&(B
                    344:
                    345: $B<+A3$J<BAu$H8@$($k(B.
                    346:
                    347: content $B=|5n$KAjEv$9$kJ}K!$r?7$?$K9M0F$9$kI,MW(B
                    348: $B$,$"$j(B, $B:#8e$N2]Bj(B.
                    349: \end{slide}
                    350:
                    351: \begin{slide}{\ns $B7W;;$NNc(B}
                    352:
                    353: $\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%0%l%V%J!<7W;;(B
                    354: \begin{verbatim}
                    355: [0] S2=newalg(x^2-2);
                    356: (#0)
                    357: [1] S3=newalg(x^2-3);
                    358: (#1)
                    359: [2] F1=S2*x^2+(S2+S3)*x*y+S3*y^2-S3$
                    360: F2=(S2-2*S3)*x^2+2*S3*x*y+2*S2*x^2+S2+S3]$
                    361: [3] nd_gr_trace([F1,F2],[x,y],1,1,2);
                    362: [90*y^4+(-21*#0*#1-246)*y^2+(16*#0*#1+144),
                    363: 20*x+(15*#0*#1-60)*y^3+(-7*#0*#1+83)*y]
                    364: \end{verbatim}
                    365: \end{slide}
                    366:
                    367: \begin{slide}{\ns $B<B83(B : $BC1:,E:2C(B}
                    368:
                    369: {\small
                    370: \begin{eqnarray*}
                    371: Cyc&=&\{f_1,f_2,f_3,f_4,f_5,f_6,f_7\}\\
                    372: f_1&=&\omega c_5c_4c_3c_2c_1c_0-1\\
                    373: 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\\
                    374: 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\\
                    375: 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\\
                    376: 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\\
                    377: f_6&=&(c_1+\omega )c_0+c_2c_1+c_3c_2+c_4c_3+c_5c_4+\omega c_5\\
                    378: f_7&=&c_0+c_1+c_2+c_3+c_4+c_5+\omega
                    379: \end{eqnarray*}}
1.2     ! noro      380: $Cyc$: cyclic-7 $B$N(B $c_6$ $B$K(B 1 $B$N86;O(B 7 $B>h:,(B $\omega$ $B$rBeF~(B
1.1       noro      381:
                    382: \underline{$\Q(\omega)$ $B>e$G$N(B GB $B7W;;(B}: $B@F<!2=(B trace $B%"%k%4%j%:%`$K$h$j(B 22 $BIC(B
                    383: (monic $B2=$K(B 2.2 $BIC(B ($B5U857W;;(B 0.2$BIC(B))
                    384:
                    385: \underline{$B:G>.B?9`<0$rE:2C$7$F(B $\Q$ $B>e$G7W;;(B} : 220 $BIC(B
                    386:
                    387:
                    388: \end{slide}
                    389:
                    390: \begin{slide}{\ns $B<B83(B : 2 $B:,E:2C(B}
                    391: {\small
                    392: \begin{eqnarray*}
                    393: Cap&=&\{f_1,f_2,f_3,f_4\}\\
                    394: f_1&=&(2ty-2)x-(\alpha+\beta)zy^2-z\\
                    395: 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\\
                    396: f_3&=&(t^2-1)x+(\beta\alpha^4+\beta^3\alpha^3)tzy-2z\\
                    397: 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\\
                    398: m_1&=&u^7-7u+3\\
                    399: m_2&=&u^6+\alpha u^5+\alpha^2u^4+\alpha^3u^3+\alpha^4u^2+\alpha^5u+\alpha^6-7
                    400: \end{eqnarray*}}
                    401: $Cap$ : $Caprasse$ [SYMBDATA] $B$N78?t$r%i%s%@%`$KBe?tE*?t$KCV$-49$($?(B
                    402:
                    403: $\alpha$, $\beta$ : $t^7-7t+3$ $B$N(B 2 $B:,(B
                    404:
                    405: \underline{$\Q(\alpha,\beta)$ $B>e$G$N(B GB $B7W;;(B} : $B@F<!2=(B trace $B%"%k%4%j%:%`$G(B 589 $BIC(B
                    406: (monic $B2=(B 36 $BIC(B)
                    407:
                    408: \underline{$\Q$ $B>e$G$N7W;;(B} : 1 $B;~4VBT$C$F$b=*N;$7$J$$(B.
                    409: \end{slide}
                    410:
                    411: \begin{slide}{\ns $B<B83(B : 3 $B:,E:2C(B}
                    412:
                    413: $f(x)=x^7-7x+3$ $B$N:G>.J,2rBN(B $F$ $B$O(B 3 $B:,E:2C$G<B8=$5$l$k(B ($B4{=P(B).
                    414:
                    415: $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
                    416: GCD $B7W;;(B (GCD $B$O(B 1 $B<!<0(B) $B%0%l%V%J!<4pDl$G7W;;$9$k(B.
                    417:
                    418: \underline{$F$ $B>e$N(B GB $B7W;;(B} : 0.8 $BIC(B ($B5U857W;;(B 1 $B2sJ,$,BgItJ,(B)
                    419:
                    420: \underline{$\Q$ $B>e$G7W;;(B} : 60 $BIC(B
                    421:
                    422: \end{slide}
                    423:
                    424: \begin{slide}{\ns $B$*$o$j$K(B}
                    425:
                    426: \begin{itemize}
                    427: \item DCGB $B$H$N4X78(B
                    428:
                    429: $B:4F#$i(B [SATO01] $B$K$h$k(B DCGB $B$H$NHf3S(B
                    430:
                    431: \item change of ordering, RUR
                    432:
                    433: FGLM $B$d(B RUR $B$N7W;;$NBe?tBN>e$X$N3HD%(B
                    434:
                    435: ($BBe?tBN>e(B? or $BM-M}?tBN>e(B?)
                    436:
                    437: \item $BBe?tBN1i;;$N<BAu$N8zN(2=(B
                    438:
                    439: $BBe?tBN$NI=8=$r(B {\tt DP} $B$+$i(B, $B$h$j8zN($h$$(B
                    440: $B<BAu$KJQ99$9$k(B
1.2     ! noro      441:
        !           442: \item Dynamic evaluation
        !           443:
        !           444: $BI,$:$7$b4{Ls$G$J$$B?9`<0$K$h$k3HBg$r5v$9(B
        !           445:
        !           446: $\Rightarrow$ $B5U857W;;$K<:GT$9$l$P(B, $B78?t4D$,J,2r$G$-$k(B.
1.1       noro      447: \end{itemize}
                    448:
                    449: \end{slide}
                    450:
                    451: \begin{slide}{\ns $BJ88%(B}
                    452:
                    453: [HOEIJ02] M.v. Hoeij, M. Monagan, A Modular GCD algorithm over Number Fields presented with Multiple Extensions. Proc. ISSAC'02 (2002), 109-116.
                    454:
                    455: [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.
                    456:
                    457: [SATO01] Y. Sato, A. Suzuki,  Discrete Comprehensive Gr\"obner Bases.
                    458: Proc. ISSAC'01 (2001), 292-296.
                    459:
                    460: [SYMBDATA] {\tt http://www.SymbolicData.org}.
                    461: \end{slide}
                    462:
                    463: %\begin{slide}{\ns }
                    464: %\end{slide}
                    465:
                    466: \end{document}
                    467: