Return to rims2001-noro.tex CVS log

Up to [local] / OpenXM / doc / Papers

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

1.2     ! noro        1: % $OpenXM: OpenXM/doc/Papers/rims2001-noro.tex,v 1.1 2001/11/16 10:33:25 noro Exp $
1.1       noro        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:
1.2     ! noro       44: $B2<;3(B-$B2#;3;;K!(B : $\sqrt{I}$ $B$NAG%$%G%"%kJ,2r(B $\Rightarrow$ $I$ $B$N=`AGJ,2r(B
1.1       noro       45:
                     46: $\sqrt{I}$ $B$NJ,2r$K$O(B, $BB?JQ?t$N0x?tJ,2r$,I,MW(B
                     47:
                     48: $B$R$g$C$H$7$?$iBe?t4v2?Id9f$X$N1~MQ$,$"$k$+$b$7$l$J$$(B
                     49:
1.2     ! noro       50: \item Reed-Solomon $BId9f$N(B list decoding $B$X$N1~MQ$"$j(B
        !            51:
1.1       noro       52: \item $B$=$l<+BN$*$b$7$m$$(B
                     53:
                     54: $BI8?t$,>.$5$$>l9g(B (2,3,5,7 $B$J$I(B) $BFCM-$N:$Fq$,$"$k(B.
                     55:
                     56: $BL5J?J}J,2r$G$N:$Fq(B
                     57:
1.2     ! noro       58: evaluation point $B$,B-$j$J$$>l9g(B
1.1       noro       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:
1.2     ! noro      183: $F=GF(q)$ $B$N(B $m$ $B<!3HBg(B $F_m$ $B$r(B
        !           184: $h(x) \in F[x]$ : $m$ $B<!4{Ls(B $B$K$h$j(B $F_m = F[x]/(h(x))$
        !           185: $B$GI=8=(B
1.1       noro      186:
1.2     ! noro      187: $\Rightarrow$ $B7W;;$,BgJQ(B
1.1       noro      188:
                    189: $q$ $B$O>.$G(B, $\#(F_m)$ $B$,$=$l$J$j$KBg$-$1$l$P$h$$(B
                    190:
                    191: $\Rightarrow$ $F_m$ $B$r86;O:,I=8=$9$l$P$h$$(B
                    192:
                    193: \end{slide}
                    194:
                    195: \begin{slide}{}
                    196: \begin{center}
                    197: \fbox{\fbc \large $B86;O:,I=8=(B $F_m^{\times} = \{\alpha^i | ( 0 \le i \le q-2) \}$}
                    198: \end{center}
                    199: \begin{itemize}
                    200: \item $B$+$1;;(B, $B3d;;(B, $B$Y$->h$OMF0W(B
                    201:
                    202: $\alpha^i \cdot \alpha^j = \alpha^{i+j \bmod q-1}$
                    203:
                    204: \item $BB-$7;;(B, $B0z$-;;$O%F!<%V%k;2>H(B (Faug\`ere GB $B$GMQ$$$i$l$?(B)
                    205:
                    206: $\alpha^i + 1 = \alpha^{a_i}$ $B$J$k(B $a_i$ $B$r7W;;$7(B,
                    207: $(i,a_i)$ $B$r%F!<%V%k$GJ];}(B
                    208:
                    209: $\alpha^i+\alpha^j = \alpha^j(\alpha^{i-j}+1)$ $B$H$7$F7W;;(B
                    210:
1.2     ! noro      211: \item $F_m$ $B$N%5%$%:$,(B $2^{16}$ $BDxEY$^$G$J$i<BMQE*(B
1.1       noro      212:
                    213: $BBN$r3HBg$7$F$b(B, $B7W;;B.EY$O$[$H$s$IJQ$o$i$J$$(B.
                    214:
                    215: \end{itemize}
                    216: \end{slide}
                    217:
                    218: \begin{slide}{}
                    219: \begin{center}
                    220: \fbox{\fbc \large 2 $BJQ?t$N(B Hensel $B9=@.(B }
                    221: \end{center}
                    222:
                    223: $f(x,y) = \prod_{i=1}^l f_i(x) \bmod y$
                    224:
                    225: $\Rightarrow$ $f(x,y) = \prod_{i=1}^l f_{k,i}(x) \bmod y^k$ $B$X$N(B Hensel $B9=@.$O(B
                    226:
                    227: $f(x,y) = f_{k,1} \cdot F_1 \bmod y^k$
                    228:
                    229: $\Rightarrow$ $F_1(x,y) = f_{k,2} \cdot F_2 \bmod y^k$
                    230:
                    231: $\Rightarrow$ $F_2(x,y) = f_{k,3} \cdot F_3 \bmod y^k$
                    232:
                    233: $\cdots$
                    234:
                    235: $B$H7W;;$7$F$$$/(B $\cdots$ $BC1=c$+$D9bB.(B
                    236:
                    237:
                    238: \end{slide}
                    239:
                    240: \begin{slide}{}
                    241: \begin{center}
                    242: \fbox{\fbc \large Finding true factors}
                    243: \end{center}
                    244:
                    245: \begin{itemize}
                    246: \item combination $\Rightarrow$ trial division
                    247:
                    248: bound $B$h$j>/$7B?$a$K(B Hensel $B9=@.(B
                    249:
                    250: $\Rightarrow$ $d-1$ test ($B:4!9LZ(B, Abbott et al.) $B$,$h$/8z$/(B
                    251:
                    252: $B$7$+$7(B, $BAH$_9g$o$;GzH/$O9nI~$G$-$J$$(B
                    253:
                    254: \item ``funny factorization''
                    255:
                    256: change of ordering $B$K$h$j(B true factor $B$r8+$D$1$k(B
                    257:
                    258: $B%K%;0x;R$,B?$$>l9g$K8z2LE*(B
                    259:
                    260: \end{itemize}
                    261: \end{slide}
                    262:
                    263: \begin{slide}{}
                    264: \begin{center}
                    265: \fbox{\fbc \large Funny factorization}
                    266: \end{center}
                    267:
                    268: $f(x,y)$ : $x$ $B$K$D$$$F(B monic $B$H$9$k(B.
                    269:
                    270: $f(x,y) \simeq g_k(x,y) h_k(x,y) \bmod y^k$
                    271:
                    272: $B$KBP$7(B, $I=Id(g_k,y^k)$ $B$r9M$($k$H(B $\{g_k,y^k\}$ $B$O(B
                    273: $x<_l y$ $B$J$k(B lex order $B$G$N%0%l%V%J4pDl(B
                    274:
                    275: $g_k| g \bmod y^k$, $g|f$ $B$J$k4{Ls0x;R(B $g$ $B$O(B $g\in I$.
                    276:
                    277: \underline{$BDjM}(B}
                    278:
                    279: $k$ $B$,==J,Bg$-$$$H$-(B, $g$ $B$O(B $I$ $B$N(B degree compatible order $<$ $B$G$N%0(B
                    280: $B%l%V%J4pDl$N=g=x:G>.$N85(B
                    281:
                    282: [$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,
                    283:
                    284: $\#V(Id(g',g)) \le tdeg(g')\cdot tdeg(g)$ (B\'ezout) $B$@$,(B,
                    285:
                    286: $\#V(I) = k\deg_x(g_k) \le \#V(Id(g',g))$
                    287:
                    288: $B$h$j(B $k$ $B$rBg$-$/$H$l$PL7=b(B.
                    289: \end{slide}
                    290:
                    291: \begin{slide}{}
                    292: \begin{center}
                    293: \fbox{\fbc \large Funny factorization $B$D$E$-(B}
                    294: \end{center}
                    295:
                    296: $I$ $B$N(B $<_l$ $B$G$N%0%l%V%J4pDl$,J,$+$C$F$$$k(B
                    297:
                    298: $\Rightarrow$ change of ordering $B$G(B $g$ $B$,7W;;$G$-$k(B
                    299:
                    300: $k > tdeg(f)^2/\deg_x(g_k)$ $B$J$i(B deterministic
                    301:
                    302: $B>.$5$$<!?t$N0x;R$r4|BT$7$F(B $k$ $B$r>.$5$/$H$k(B
                    303:
                    304: $BFC$K(B, $\bmod y$ $B$G$N0x;R$,B?$$>l9g$KM-8z(B
                    305:
                    306: \end{slide}
                    307:
                    308: \begin{slide}{}
                    309: \begin{center}
                    310: \fbox{\fbc \large $B85$NBN$G$N0x;R$N7W;;(B}
                    311: \end{center}
                    312:
                    313: $F = GF(q)$ $B>e$N4{Ls0x;R$,(B $F_m$ $B>e$GJ,2r$9$k2DG=@-$"$j(B
                    314:
1.2     ! noro      315: $f \in F[x_1,\ldots,x_n]$, $f$ : $F$ $B>e4{Ls$G(B
        !           316:
        !           317: $f = \prod f_i$, $f_i$ : $F_m$ $B>e4{Ls$H$9$k(B.
        !           318:
        !           319: $F_m/F$ $B$O(B Galois $B3HBg$G(B, $G=Gal(F_m/F) = \langle \sigma \rangle$
1.1       noro      320:
1.2     ! noro      321: $B$?$@$7(B $\sigma : \beta \mapsto \beta^q$
1.1       noro      322:
                    323: $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
                    324:
1.2     ! noro      325: $\prod_{s\in S}s \in F[x_1,\ldots,x_n]$.
        !           326:
        !           327: $f$ $B$O(B $F$ $B>e4{Ls$@$+$i(B $f = \prod_{s\in S}s$.
        !           328:
        !           329: $\Rightarrow$ $F$ $B>e$N4{Ls0x;R(B = $F_m$ $B>e$N4{Ls0x;R$N(B $G$-orbit
1.1       noro      330:
                    331: $\sigma(h)$ $B$O78?t$r(B $q$ $B>h$9$l$P$h$$$+$iMF0W(B.
                    332:
                    333: \end{slide}
                    334:
                    335: \begin{slide}{}
                    336: \begin{center}
                    337: \fbox{\fbc \large $B%?%$%_%s%0%G!<%?(B --- [BM97] $B$+$i$NNc(B}
                    338: \end{center}
                    339:
                    340: \underline{ 2 $BJQ?tB?9`<0(B}
                    341: \begin{center}
                    342: {\normalsize
                    343: \begin{tabular}{|c|c|c|c|c|c|c|} \hline
                    344:  & $f_2$ & $f_7$ & $f_{11}$ & $f_{13}$ & $f_{17}$ & $f_{17,y\rightarrow y^2}$ \\ \hline
                    345: $\deg_x,\deg_y$ & 7,5 & 100,100 & 300,300 & $10^3,10^3$ & 32,16 & 32,32 \\ \hline
                    346: \#factors & 2 & 2 & 1 & 2 & 1 & 2 \\ \hline
                    347: Maple7 & 4.2 & 30 & 68 & $>$1day & 36 & 32 \\ \hline
                    348: Asir & 0 ($2^3$) & 2.6($7^2$)  & 34  & 5040 & 0.24 & 0.57  \\ \hline
                    349: %Hensel & 0  &  & & 2965 &  &   \\ \hline
                    350: \end{tabular}
                    351: }
                    352: \end{center}
                    353: $f_p$ $B$r(B $GF(p)$ $B>e$G0x?tJ,2r(B
                    354:
                    355: Asir $B$N(B $(p^m)$ : $GF(p^m)$ $B$^$G3HBg$9$kI,MW$,$"$C$?(B
                    356: \end{slide}
                    357:
                    358: \begin{slide}{}
                    359: \fbox{\fbc \large Maple $B$H$NHf3S(B}
                    360:
                    361: \begin{itemize}
                    362: \item Hensel $B9=@.$N@-G=Hf3S(B
                    363:
                    364: $f_{11}$ $B$O(B Hensel $B9=@.$,$[$H$s$I(B $\Rightarrow$ Hensel $B9=@.(B
                    365: $B<+BN$N@-G=$OBg:9$J$$(B
                    366:
                    367: [BM97] $B$K$h$l$P(B, $BAGBN>e$NB?9`<0$O(B kernel $B$GFCJL$K<BAu$5$l$F$$$k(B
                    368: (Asir $B$HF1$8(B)
                    369:
                    370: \item $B2rC5:wIt$N@-G=Hf3S(B
                    371:
                    372: $f_{17}$ $B$N>l9g(B, Maple $B$N7W;;;~4V$N$[$H$s$I$O(B bad combination $B$N(B
                    373: $BGS=|(B $\Rightarrow$ $B2?$+FCJL$J$3$H$r$7$F$$$FCY$$(B?
                    374:
                    375: \item $B3HBg$,I,MW$J>l9g$NHf3S(B
                    376:
                    377: Maple $B$G$O(B, $BBN$N3HBg$,I,MW$J>l9g$K$O(B, Domains package ($B0lHL$NM-8BBN$r(B
                    378: $B07$&(B generic $B$J<BAu(B) $B$r;H$&$?$a(B, $f_2$, $f_7$ $B$G:9$,=P$?(B
                    379: \end{itemize}
                    380: \end{slide}
                    381:
                    382:
                    383: \begin{slide}{}
                    384: \begin{center}
                    385: \fbox{\fbc \large $B%?%$%_%s%0%G!<%?(B --- $BBN$N3HBg$H8zN((B}
                    386: \end{center}
                    387:
                    388: \begin{center}
                    389: {\normalsize
                    390: \begin{tabular}{|c|c|c|c|c|c|c|c|} \hline
                    391: $B3HBg<!?t(B  & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline
                    392: $f_7$ & ---  & 2.6 & 2.9 & 2.7 & 2.6 & 5.8 & 9.1 \\ \hline
                    393: $f_{17,y\rightarrow y^2}$ & 0.57 & 0.78 & 0.55 & 2.3 & --- & --- & --- \\ \hline
                    394: \end{tabular}
                    395: }
                    396: \end{center}
                    397:
                    398: \underline{$B9M;!(B}
                    399:
                    400: \begin{itemize}
                    401: \item $BBN$,>.$5$$$&$A$O(B, $B3HBg$7$F$b8zN($OMn$A$J$$(B
                    402:
                    403: $B$b$A$m$s(B, $B3HBg$K$h$j0x;R$,A}$($k>l9g$O=|$/(B
                    404:
                    405: \item $BBN$N%5%$%:$,Bg$-$/$J$k$H(B, $B5^7c$K8zN($,Mn$A$k(B
                    406:
                    407: $B;2>H$9$k%F!<%V%k$,Bg$-$/$J$k(B $\Rightarrow$ $B%-%c%C%7%e%5%$%:$K4X78(B?
                    408: \end{itemize}
                    409: \end{slide}
                    410:
                    411: \begin{slide}{}
                    412: \begin{center}
                    413: \fbox{\fbc \large $BAH$_9g$o$;GzH/$r5/$3$9>l9g(B}
                    414: \end{center}
                    415:
1.2     ! noro      416: $f(x,y) = f_{17}(x,y^2)f_{17}(x+1,y^2)$
1.1       noro      417:
                    418: $B??$N0x;R$O(B 4 $B8D(B, $\bmod y$ $B$G$N0x;R(B 32 $B8D(B
                    419:
                    420: \underline{$BDL>o$N(B Belrekamp-Zassenhaus $B7?$G7W;;$7$?>l9g(B}
                    421:
                    422: \begin{itemize}
                    423: \item $B=hM}$7$?AH$_9g$o$;(B : 3852356
                    424: \item $B<!?t%A%'%C%/$GGS=|(B : 3734707
                    425: \item $B7W;;;~4V(B : 162sec
                    426: \end{itemize}
                    427:
                    428: \underline{Funny factorization $B$G7W;;$7$?>l9g(B}
                    429: \begin{itemize}
                    430: \item bound = 16 ($B$3$l$O4E$9$.(B)         2.6sec
                    431: \item bound = 32 ($B>/$J$/$H$b0x;R$O=P$k(B) 17sec
                    432: \end{itemize}
                    433: \end{slide}
                    434:
                    435: \begin{slide}{}
                    436: \begin{center}
                    437: \fbox{\fbc \large $B:#8e$NM=Dj(B}
                    438: \end{center}
                    439:
                    440: \begin{itemize}
                    441: \item $BL5J?J}J,2rIt$N2~NI(B, engine $BAH$_9~$_(B
                    442:
                    443: \item 3 $BJQ?t0J>e$X$N(B Hensel $B9=@.$r(B EEZ $B2=(B
                    444:
                    445: \item 2 $BJQ?tB?9`<0$N@Q$N(B, Karatsuba $B$K$h$k9bB.2=(B
                    446:
                    447: \item Zassenhaus, Funny $B$N(B OpenXM $B$K$h$kJBNs2=(B
                    448:
                    449: \item knapsack $B7?$N%"%k%4%j%:%`$NE,MQ2DG=@-$N8!F$(B
                    450: \end{itemize}
                    451: \end{slide}
                    452:
                    453: \end{document}