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:
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>