Return to rims2001-noro.tex CVS log

Up to [local] / OpenXM / doc / Papers

Annotation of OpenXM/doc/Papers/rims2001-noro.tex, Revision 1.1

1.1     ! noro        1: % $OpenXM$
        !             2: \documentclass{slides}
        !             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: \def\gr{Gr\"obner basis }
        !            11: \def\st{\, s.t. \,}
        !            12: \def\ni{\noindent}
        !            13: \def\ve{\vfill\eject}
        !            14: \textwidth 9.2in
        !            15: \textheight 7.2in
        !            16: \columnsep 0.33in
        !            17: \topmargin -1in
        !            18: \def\tc{\color{red}}
        !            19: \def\fbc{\bf\color{MediumBlue}}
        !            20: \def\itc{\color{brown}}
        !            21: \def\urlc{\bf\color{DarkGreen}}
        !            22: \def\bc{\color{LightGoldenrod1}}
        !            23:
        !            24: \title{\tc $B>.I8?tM-8BBN>e$NB?JQ?tB?9`<0$N0x?tJ,2r$K$D$$$F(B}
        !            25:
        !            26: \author{$BLnO$(B $B@59T(B ($B?@8MBg!&M}(B)\\ $B2#;3(B $BOB90(B ($B6e=#Bg!&?tM}(B)}
        !            27: \begin{document}
        !            28: \large
        !            29: \setlength{\parskip}{0pt}
        !            30: \maketitle
        !            31:
        !            32: \begin{slide}{}
        !            33: \begin{center}
        !            34: \fbox{\fbc \large $B$J$<(B ($B$$$^$5$i(B)$BM-8BBN>e$NB?JQ?tB?9`<0$N0x?tJ,2r(B?}
        !            35: \end{center}
        !            36:
        !            37: \begin{itemize}
        !            38: \item Risa/Asir $B$K<BAu$5$l$F$$$J$$(B
        !            39:
        !            40: $B$J$<$J$$$N$+(B, $B$H<+J,$G;W$&$3$H$O$7$P$7$P$"$C$?(B
        !            41:
        !            42: \item $B@5I8?t=`AGJ,2r$KI,MW(B
        !            43:
        !            44: $B2<;3(B-$B2#;3%"%k%4%j%:%`$G$O(B, $\sqrt{I}$ $B$NAG%$%G%"%kJ,2r(B
        !            45: $B$+$i(B $I$ $B$N=`AGJ,2r$rF3$/(B
        !            46:
        !            47: $\sqrt{I}$ $B$NJ,2r$K$O(B, $BB?JQ?t$N0x?tJ,2r$,I,MW(B
        !            48:
        !            49: $B$R$g$C$H$7$?$iBe?t4v2?Id9f$X$N1~MQ$,$"$k$+$b$7$l$J$$(B
        !            50:
        !            51: \item $B$=$l<+BN$*$b$7$m$$(B
        !            52:
        !            53: $BI8?t$,>.$5$$>l9g(B (2,3,5,7 $B$J$I(B) $BFCM-$N:$Fq$,$"$k(B.
        !            54:
        !            55: $BL5J?J}J,2r$G$N:$Fq(B
        !            56:
        !            57: $BFC$K(B, $BJQ?t$N8D?t$r8:$i$9>l9g$N(B evaluation point
        !            58: $B$,B-$j$J$$>l9g(B
        !            59: \end{itemize}
        !            60: \end{slide}
        !            61:
        !            62: \begin{slide}{}
        !            63: \begin{center}
        !            64: \fbox{\fbc \large $B%"%k%4%j%:%`$N35MW(B I : $BL5J?J}J,2r(B}
        !            65: \end{center}
        !            66:
        !            67: modification of Bernardin's algorithm [Ber97]
        !            68:
        !            69: $f \in F[x_1,\ldots,x_n]$, $F$ : $BM-8BBN(B $Char(F) = p$
        !            70:
        !            71: $f = FGH$, where $F=\prod f_i^{a_i}$,
        !            72: $G=\prod g_j^{b_j}$,
        !            73: $H=\prod h_k^{c_k}$
        !            74:
        !            75: $f_i, g_j, h_k$ : $BL5J?J}(B, $B8_$$$KAG(B.
        !            76:
        !            77: $'$ $B$r(B $d/dx_1$ $B$H$7$F(B
        !            78: $f_i' \neq 0$, $p \not{|}a_j$, $p | b_j$, $h_k' = 0$
        !            79: $B$H=q$/$H(B
        !            80:
        !            81: $f' = F'GH$ $B$9$k$H(B $GCD(f,f') = GCD(F,F')GH$
        !            82:
        !            83: $GCD(F,F') = \prod f_i^{a_i-1}$ $B$@$+$i(B $f/GCD(f,f')=\prod f_i$
        !            84:
        !            85: $\prod f_i$ $B$G(B $f$ $B$r7+$jJV$73d$k$3$H$G(B, $f_1$ ($B=EJ#EY:G>.(B)
        !            86: $B$,5a$^$k(B
        !            87:
        !            88: $\Rightarrow$ $F$ $B$,A4$FJ,2r$G$-$k(B
        !            89:
        !            90: \end{slide}
        !            91:
        !            92: \begin{slide}{}
        !            93: \begin{center}
        !            94: \fbox{\fbc \large $BL5J?J}J,2r(B $B$D$E$-(B}
        !            95: \end{center}
        !            96:
        !            97: $B;D$j(B $f = GH$ $B$G(B,  $f' = 0$
        !            98:
        !            99: $B$3$l$r(B $x_i$ $B$K$D$$$F7+$jJV$7$F;D$C$?(B $f$
        !           100:
        !           101: $\Rightarrow$ $df/dx_1 = \ldots = df/dx_n = 0$
        !           102:
        !           103: $\Rightarrow$ $B$3$l$O(B, $BA4$F$N;X?t$,(B $p$ $B$G3d$j@Z$l$k$3$H$r0UL#$9$k(B
        !           104:
        !           105: $\Rightarrow$ $F$ $B$OM-8BBN$@$+$i(B $f = g^p$ $B$H=q$1$k(B
        !           106:
        !           107: $\Rightarrow$ $g$ $B$KBP$7$F%"%k%4%j%:%`$rE,MQ(B
        !           108: \end{slide}
        !           109:
        !           110:
        !           111: \begin{slide}{}
        !           112: \begin{center}
        !           113: \fbox{\fbc \large Bernardin $B$NJ}K!$H$NHf3S(B}
        !           114: \end{center}
        !           115: $BI8?t(B 0 $B$K$*$1$k(B Yun $B$NJ}K!(B : $B=EJ#EY$N8zN(E*7W;;(B
        !           116:
        !           117: $B=EJ#EY$,9b$$>l9g$KM-Mx(B
        !           118:
        !           119: Bernardin : $B@5I8?t$N>l9g$K$b(B Yun $B$NJ}K!$r=$@5$7$FE,MQ(B
        !           120:
        !           121: $\Rightarrow$ $B=EJ#EY$,(B $p$ $B$h$jBg$-$$>l9g$KJ#;(2=(B
        !           122:
        !           123: $\Rightarrow$ $p$ $B$,>.$5$$>l9g$K$O(B, $BC1=c$K=|;;$N7+$jJV$7$G=EJ#EY$r5a(B
        !           124: $B$a$k(B
        !           125:
        !           126: ($B>\:Y$JHf3S$O$^$@9T$C$F$$$J$$(B)
        !           127: \end{slide}
        !           128:
        !           129: \begin{slide}{}
        !           130: \begin{center}
        !           131: \fbox{\fbc \large $B%"%k%4%j%:%`$N35MW(B II : $BFsJQ?t$X$N5"Ce(B}
        !           132: \end{center}
        !           133:
        !           134: \begin{itemize}
        !           135: \item $B@0?t78?tB?JQ?tB?9`<0$N>l9g(B
        !           136:
        !           137: $n$ $B$NFb(B $n-1$ $B8D$NJQ?t$r(B fix $\Rightarrow$ 1 $BJQ?t$G0x;R$N%?%M$r:n$k(B
        !           138:
        !           139: $B%K%;0x;R$O$[$H$s$I=P$J$$(B
        !           140:
        !           141: \item $BM-8BBN78?t$N>l9g(B
        !           142:
        !           143: $B0lJQ?t$KMn$9$H%K%;0x;R$@$i$1(B
        !           144:
        !           145: $\Rightarrow$ $Z[x]$ $B$KAjEv$9$k$N$O(B $F[y][x]$
        !           146:
        !           147: \end{itemize}
        !           148:
        !           149: \end{slide}
        !           150:
        !           151: \begin{slide}{}
        !           152: \begin{center}
        !           153: \fbox{\fbc \large $B8=:_$N<BAu(B}
        !           154:
        !           155: \begin{itemize}
        !           156: \item $BL5J?J}J,2r$N%\%H%k%M%C%/$O(B $GCD(f,f')$
        !           157:
        !           158: Brown's algorithm $B$G7W;;(B $\Rightarrow$ evaluation point $B$NITB-(B
        !           159: $B$,LdBj(B $\Rightarrow$ $F$ $B$N3HBgBN$r;H$&(B ($B8e=R(B)
        !           160:
        !           161: \item 2 $BJQ?t0J30$OA4$F(B Asir $B$G5-=R(B
        !           162:
        !           163: \item 2 $BJQ?t$N$_(B builtin
        !           164:
        !           165: $B8zN(>e(B critical $B$N$?$a(B $\Rightarrow$ $B$d$O$j(B $F$ $B$N3HBgBN$,I,MW(B
        !           166:
        !           167: $B@0?t>e0lJQ?tB?9`<0$N0x?tJ,2r$H6K$a$FN`;w(B
        !           168:
        !           169: \item 2 $BJQ?t$G%?%M$r:n$C$F(B, $B0lJQ?t$+$i2~$a$F(B Hensel $B9=@.(B
        !           170:
        !           171: EEZ $B%"%k%4%j%:%`$r=q$1$F$$$J$$$?$a(B
        !           172: \end{itemize}
        !           173: \end{center}
        !           174: \end{slide}
        !           175:
        !           176: \begin{slide}{}
        !           177: \begin{center}
        !           178: \fbox{\fbc \large $BM-8BBN$NBe?t3HBg$N8zN(E*I=8=(B}
        !           179: \end{center}
        !           180:
        !           181: evaluation point $B$N3NJ]$N$?$a(B, $BM-8BBN$NBe?t3HBg$,I,MW(B
        !           182:
        !           183: $F=GF(q)$ $B$N(B $m$ $B<!3HBg(B $F_m$ $\cdots$ $h(x) \in F[x]$ : $m$ $B<!4{Ls(B
        !           184: $B$K$h$j(B $F_m = F[x]/(h(x))$
        !           185:
        !           186: $\Rightarrow$ $B$3$l$G$O7W;;$,BgJQ(B
        !           187:
        !           188: $q$ $B$O>.$G(B, $\#(F_m)$ $B$,$=$l$J$j$KBg$-$1$l$P$h$$(B
        !           189:
        !           190: $\Rightarrow$ $F_m$ $B$r86;O:,I=8=$9$l$P$h$$(B
        !           191:
        !           192: \end{slide}
        !           193:
        !           194: \begin{slide}{}
        !           195: \begin{center}
        !           196: \fbox{\fbc \large $B86;O:,I=8=(B $F_m^{\times} = \{\alpha^i | ( 0 \le i \le q-2) \}$}
        !           197: \end{center}
        !           198: \begin{itemize}
        !           199: \item $B$+$1;;(B, $B3d;;(B, $B$Y$->h$OMF0W(B
        !           200:
        !           201: $\alpha^i \cdot \alpha^j = \alpha^{i+j \bmod q-1}$
        !           202:
        !           203: \item $BB-$7;;(B, $B0z$-;;$O%F!<%V%k;2>H(B (Faug\`ere GB $B$GMQ$$$i$l$?(B)
        !           204:
        !           205: $\alpha^i + 1 = \alpha^{a_i}$ $B$J$k(B $a_i$ $B$r7W;;$7(B,
        !           206: $(i,a_i)$ $B$r%F!<%V%k$GJ];}(B
        !           207:
        !           208: $\alpha^i+\alpha^j = \alpha^j(\alpha^{i-j}+1)$ $B$H$7$F7W;;(B
        !           209:
        !           210: \item $F_m$ $B$N%5%$%:$,(B $2^16$ $BDxEY$^$G$J$i<BMQE*(B
        !           211:
        !           212: $BBN$r3HBg$7$F$b(B, $B7W;;B.EY$O$[$H$s$IJQ$o$i$J$$(B.
        !           213:
        !           214: \end{itemize}
        !           215: \end{slide}
        !           216:
        !           217: \begin{slide}{}
        !           218: \begin{center}
        !           219: \fbox{\fbc \large 2 $BJQ?t$N(B Hensel $B9=@.(B }
        !           220: \end{center}
        !           221:
        !           222: $f(x,y) = \prod_{i=1}^l f_i(x) \bmod y$
        !           223:
        !           224: $\Rightarrow$ $f(x,y) = \prod_{i=1}^l f_{k,i}(x) \bmod y^k$ $B$X$N(B Hensel $B9=@.$O(B
        !           225:
        !           226: $f(x,y) = f_{k,1} \cdot F_1 \bmod y^k$
        !           227:
        !           228: $\Rightarrow$ $F_1(x,y) = f_{k,2} \cdot F_2 \bmod y^k$
        !           229:
        !           230: $\Rightarrow$ $F_2(x,y) = f_{k,3} \cdot F_3 \bmod y^k$
        !           231:
        !           232: $\cdots$
        !           233:
        !           234: $B$H7W;;$7$F$$$/(B $\cdots$ $BC1=c$+$D9bB.(B
        !           235:
        !           236:
        !           237: \end{slide}
        !           238:
        !           239: \begin{slide}{}
        !           240: \begin{center}
        !           241: \fbox{\fbc \large Finding true factors}
        !           242: \end{center}
        !           243:
        !           244: \begin{itemize}
        !           245: \item combination $\Rightarrow$ trial division
        !           246:
        !           247: bound $B$h$j>/$7B?$a$K(B Hensel $B9=@.(B
        !           248:
        !           249: $\Rightarrow$ $d-1$ test ($B:4!9LZ(B, Abbott et al.) $B$,$h$/8z$/(B
        !           250:
        !           251: $B$7$+$7(B, $BAH$_9g$o$;GzH/$O9nI~$G$-$J$$(B
        !           252:
        !           253: \item ``funny factorization''
        !           254:
        !           255: change of ordering $B$K$h$j(B true factor $B$r8+$D$1$k(B
        !           256:
        !           257: $B%K%;0x;R$,B?$$>l9g$K8z2LE*(B
        !           258:
        !           259: \end{itemize}
        !           260: \end{slide}
        !           261:
        !           262: \begin{slide}{}
        !           263: \begin{center}
        !           264: \fbox{\fbc \large Funny factorization}
        !           265: \end{center}
        !           266:
        !           267: $f(x,y)$ : $x$ $B$K$D$$$F(B monic $B$H$9$k(B.
        !           268:
        !           269: $f(x,y) \simeq g_k(x,y) h_k(x,y) \bmod y^k$
        !           270:
        !           271: $B$KBP$7(B, $I=Id(g_k,y^k)$ $B$r9M$($k$H(B $\{g_k,y^k\}$ $B$O(B
        !           272: $x<_l y$ $B$J$k(B lex order $B$G$N%0%l%V%J4pDl(B
        !           273:
        !           274: $g_k| g \bmod y^k$, $g|f$ $B$J$k4{Ls0x;R(B $g$ $B$O(B $g\in I$.
        !           275:
        !           276: \underline{$BDjM}(B}
        !           277:
        !           278: $k$ $B$,==J,Bg$-$$$H$-(B, $g$ $B$O(B $I$ $B$N(B degree compatible order $<$ $B$G$N%0(B
        !           279: $B%l%V%J4pDl$N=g=x:G>.$N85(B
        !           280:
        !           281: [$B>ZL@(B] $B$b$7(B $g' < g$, $g'\in I$ $B$,$"$l$P(B $Id(g',g)$ $B$O(B 0 $B<!85$G(B,
        !           282:
        !           283: $\#V(Id(g',g)) \le tdeg(g')\cdot tdeg(g)$ (B\'ezout) $B$@$,(B,
        !           284:
        !           285: $\#V(I) = k\deg_x(g_k) \le \#V(Id(g',g))$
        !           286:
        !           287: $B$h$j(B $k$ $B$rBg$-$/$H$l$PL7=b(B.
        !           288: \end{slide}
        !           289:
        !           290: \begin{slide}{}
        !           291: \begin{center}
        !           292: \fbox{\fbc \large Funny factorization $B$D$E$-(B}
        !           293: \end{center}
        !           294:
        !           295: $I$ $B$N(B $<_l$ $B$G$N%0%l%V%J4pDl$,J,$+$C$F$$$k(B
        !           296:
        !           297: $\Rightarrow$ change of ordering $B$G(B $g$ $B$,7W;;$G$-$k(B
        !           298:
        !           299: $k > tdeg(f)^2/\deg_x(g_k)$ $B$J$i(B deterministic
        !           300:
        !           301: $B>.$5$$<!?t$N0x;R$r4|BT$7$F(B $k$ $B$r>.$5$/$H$k(B
        !           302:
        !           303: $BFC$K(B, $\bmod y$ $B$G$N0x;R$,B?$$>l9g$KM-8z(B
        !           304:
        !           305: \end{slide}
        !           306:
        !           307: \begin{slide}{}
        !           308: \begin{center}
        !           309: \fbox{\fbc \large $B85$NBN$G$N0x;R$N7W;;(B}
        !           310: \end{center}
        !           311:
        !           312: $F = GF(q)$ $B>e$N4{Ls0x;R$,(B $F_m$ $B>e$GJ,2r$9$k2DG=@-$"$j(B
        !           313:
        !           314: $f \in F[x_1,\ldots,x_n]$, $f$ : $F$ $B>e4{Ls$G(B $f = \prod f_i$,
        !           315: $f_i$ : $F_m$ $B>e4{Ls$H$9$k(B.
        !           316:
        !           317: $F_m/F$ $B$O(B Galois $B3HBg$G(B, $G=Gal(F_m/F) = \langle \sigma \rangle$ $B$?$@$7(B
        !           318: $\sigma : \beta \mapsto \beta^q$
        !           319:
        !           320: $S$ $B$r(B $f_1$ $B$N(B $G$-orbit $B$H$9$k$H(B $\prod_{s\in S}s$ $B$O(B $G$-$BITJQ$@$+$i(B
        !           321: $\prod_{s\in S}s \in F[x_1,\ldots,x_n]$. $f$ $B$O(B $F$ $B>e4{Ls$@$+$i(B
        !           322: $f = \prod_{s\in S}s$.
        !           323:
        !           324: $B$h$C$F(B, $F$ $B>e$N4{Ls0x;R$O(B, $F_m$ $B>e$N4{Ls0x;R$N(B $G$-orbit $B$r5a$a$l$P(B
        !           325: $B$h$$(B.
        !           326:
        !           327: $\sigma(h)$ $B$O78?t$r(B $q$ $B>h$9$l$P$h$$$+$iMF0W(B.
        !           328:
        !           329: \end{slide}
        !           330:
        !           331: \begin{slide}{}
        !           332: \begin{center}
        !           333: \fbox{\fbc \large $B%?%$%_%s%0%G!<%?(B --- [BM97] $B$+$i$NNc(B}
        !           334: \end{center}
        !           335:
        !           336: \underline{ 2 $BJQ?tB?9`<0(B}
        !           337: \begin{center}
        !           338: {\normalsize
        !           339: \begin{tabular}{|c|c|c|c|c|c|c|} \hline
        !           340:  & $f_2$ & $f_7$ & $f_{11}$ & $f_{13}$ & $f_{17}$ & $f_{17,y\rightarrow y^2}$ \\ \hline
        !           341: $\deg_x,\deg_y$ & 7,5 & 100,100 & 300,300 & $10^3,10^3$ & 32,16 & 32,32 \\ \hline
        !           342: \#factors & 2 & 2 & 1 & 2 & 1 & 2 \\ \hline
        !           343: Maple7 & 4.2 & 30 & 68 & $>$1day & 36 & 32 \\ \hline
        !           344: Asir & 0 ($2^3$) & 2.6($7^2$)  & 34  & 5040 & 0.24 & 0.57  \\ \hline
        !           345: %Hensel & 0  &  & & 2965 &  &   \\ \hline
        !           346: \end{tabular}
        !           347: }
        !           348: \end{center}
        !           349: $f_p$ $B$r(B $GF(p)$ $B>e$G0x?tJ,2r(B
        !           350:
        !           351: Asir $B$N(B $(p^m)$ : $GF(p^m)$ $B$^$G3HBg$9$kI,MW$,$"$C$?(B
        !           352: \end{slide}
        !           353:
        !           354: \begin{slide}{}
        !           355: \fbox{\fbc \large Maple $B$H$NHf3S(B}
        !           356:
        !           357: \begin{itemize}
        !           358: \item Hensel $B9=@.$N@-G=Hf3S(B
        !           359:
        !           360: $f_{11}$ $B$O(B Hensel $B9=@.$,$[$H$s$I(B $\Rightarrow$ Hensel $B9=@.(B
        !           361: $B<+BN$N@-G=$OBg:9$J$$(B
        !           362:
        !           363: [BM97] $B$K$h$l$P(B, $BAGBN>e$NB?9`<0$O(B kernel $B$GFCJL$K<BAu$5$l$F$$$k(B
        !           364: (Asir $B$HF1$8(B)
        !           365:
        !           366: \item $B2rC5:wIt$N@-G=Hf3S(B
        !           367:
        !           368: $f_{17}$ $B$N>l9g(B, Maple $B$N7W;;;~4V$N$[$H$s$I$O(B bad combination $B$N(B
        !           369: $BGS=|(B $\Rightarrow$ $B2?$+FCJL$J$3$H$r$7$F$$$FCY$$(B?
        !           370:
        !           371: \item $B3HBg$,I,MW$J>l9g$NHf3S(B
        !           372:
        !           373: Maple $B$G$O(B, $BBN$N3HBg$,I,MW$J>l9g$K$O(B, Domains package ($B0lHL$NM-8BBN$r(B
        !           374: $B07$&(B generic $B$J<BAu(B) $B$r;H$&$?$a(B, $f_2$, $f_7$ $B$G:9$,=P$?(B
        !           375: \end{itemize}
        !           376: \end{slide}
        !           377:
        !           378:
        !           379: \begin{slide}{}
        !           380: \begin{center}
        !           381: \fbox{\fbc \large $B%?%$%_%s%0%G!<%?(B --- $BBN$N3HBg$H8zN((B}
        !           382: \end{center}
        !           383:
        !           384: \begin{center}
        !           385: {\normalsize
        !           386: \begin{tabular}{|c|c|c|c|c|c|c|c|} \hline
        !           387: $B3HBg<!?t(B  & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline
        !           388: $f_7$ & ---  & 2.6 & 2.9 & 2.7 & 2.6 & 5.8 & 9.1 \\ \hline
        !           389: $f_{17,y\rightarrow y^2}$ & 0.57 & 0.78 & 0.55 & 2.3 & --- & --- & --- \\ \hline
        !           390: \end{tabular}
        !           391: }
        !           392: \end{center}
        !           393:
        !           394: \underline{$B9M;!(B}
        !           395:
        !           396: \begin{itemize}
        !           397: \item $BBN$,>.$5$$$&$A$O(B, $B3HBg$7$F$b8zN($OMn$A$J$$(B
        !           398:
        !           399: $B$b$A$m$s(B, $B3HBg$K$h$j0x;R$,A}$($k>l9g$O=|$/(B
        !           400:
        !           401: \item $BBN$N%5%$%:$,Bg$-$/$J$k$H(B, $B5^7c$K8zN($,Mn$A$k(B
        !           402:
        !           403: $B;2>H$9$k%F!<%V%k$,Bg$-$/$J$k(B $\Rightarrow$ $B%-%c%C%7%e%5%$%:$K4X78(B?
        !           404: \end{itemize}
        !           405: \end{slide}
        !           406:
        !           407: \begin{slide}{}
        !           408: \begin{center}
        !           409: \fbox{\fbc \large $BAH$_9g$o$;GzH/$r5/$3$9>l9g(B}
        !           410: \end{center}
        !           411:
        !           412: $f(x,y) = f_{17,y\rightarrow y^2}(x,y)f_{17,y\rightarrow y^2}(x+1,y^2)$
        !           413:
        !           414: $B??$N0x;R$O(B 4 $B8D(B, $\bmod y$ $B$G$N0x;R(B 32 $B8D(B
        !           415:
        !           416: \underline{$BDL>o$N(B Belrekamp-Zassenhaus $B7?$G7W;;$7$?>l9g(B}
        !           417:
        !           418: \begin{itemize}
        !           419: \item $B=hM}$7$?AH$_9g$o$;(B : 3852356
        !           420: \item $B<!?t%A%'%C%/$GGS=|(B : 3734707
        !           421: \item $B7W;;;~4V(B : 162sec
        !           422: \end{itemize}
        !           423:
        !           424: \underline{Funny factorization $B$G7W;;$7$?>l9g(B}
        !           425: \begin{itemize}
        !           426: \item bound = 16 ($B$3$l$O4E$9$.(B)         2.6sec
        !           427: \item bound = 32 ($B>/$J$/$H$b0x;R$O=P$k(B) 17sec
        !           428: \end{itemize}
        !           429: \end{slide}
        !           430:
        !           431: \begin{slide}{}
        !           432: \begin{center}
        !           433: \fbox{\fbc \large $B:#8e$NM=Dj(B}
        !           434: \end{center}
        !           435:
        !           436: \begin{itemize}
        !           437: \item $BL5J?J}J,2rIt$N2~NI(B, engine $BAH$_9~$_(B
        !           438:
        !           439: \item 3 $BJQ?t0J>e$X$N(B Hensel $B9=@.$r(B EEZ $B2=(B
        !           440:
        !           441: \item 2 $BJQ?tB?9`<0$N@Q$N(B, Karatsuba $B$K$h$k9bB.2=(B
        !           442:
        !           443: \item Zassenhaus, Funny $B$N(B OpenXM $B$K$h$kJBNs2=(B
        !           444:
        !           445: \item knapsack $B7?$N%"%k%4%j%:%`$NE,MQ2DG=@-$N8!F$(B
        !           446: \end{itemize}
        !           447: \end{slide}
        !           448:
        !           449: \end{document}