Return to rims2002-noro.tex CVS log

Up to [local] / OpenXM / doc / Papers

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

1.2     ! noro        1: % $OpenXM: OpenXM/doc/Papers/rims2002-noro.tex,v 1.1 2002/12/09 02:09:23 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: \def\HT{{\rm HT}}
                     25: \def\HC{{\rm HC}}
                     26: \def\GCD{{\rm GCD}}
                     27: \def\tdeg{{\rm tdeg}}
                     28: \def\pp{{\rm pp}}
                     29: \def\lc{{\rm lc}}
                     30: \def\Z{{\bf Z}}
                     31:
                     32: \title{\tc $B>.I8?tM-8BBN>e$NB?JQ?tB?9`<0$N0x?tJ,2r$K$D$$$F(B ($B$=$N(B 2)}
                     33:
                     34: \author{$BLnO$(B $B@59T(B ($B?@8MBg!&M}(B)}
                     35: \begin{document}
                     36: \large
                     37: \setlength{\parskip}{0pt}
                     38: \maketitle
                     39:
                     40: \begin{slide}{}
                     41: \begin{center}
                     42: \fbox{\fbc \large $BL5J?J}J,2r(B ($BI|=,(B)}
                     43: \end{center}
                     44:
                     45: modification of Bernardin's algorithm [Ber97]
                     46:
                     47: $f \in F[x_1,\ldots,x_n]$, $F$ : $BM-8BBN(B $Char(F) = p$
                     48:
                     49: $f = FGH$, where $F=\prod f_i^{a_i}$,
                     50: $G=\prod g_j^{b_j}$,
                     51: $H=\prod h_k^{c_k}$
                     52:
                     53: $f_i, g_j, h_k$ : $BL5J?J}(B, $B8_$$$KAG(B.
                     54:
                     55: $'$ $B$r(B $d/dx_1$ $B$H$7$F(B
                     56: $f_i' \neq 0$, $p \not{|}a_j$, $p | b_j$, $h_k' = 0$
                     57: $B$H=q$/$H(B
                     58:
                     59: $f' = F'GH$ $B$9$k$H(B $GCD(f,f') = GCD(F,F')GH$
                     60:
                     61: $GCD(F,F') = \prod f_i^{a_i-1}$ $B$@$+$i(B $f/GCD(f,f')=\prod f_i$
                     62:
                     63: $\prod f_i$ $B$G(B $f$ $B$r7+$jJV$73d$k$3$H$G(B, $f_1$ ($B=EJ#EY:G>.(B)
                     64: $B$,5a$^$k(B
                     65:
                     66: $\Rightarrow$ $F$ $B$,A4$FJ,2r$G$-$k(B
                     67:
                     68: \end{slide}
                     69:
                     70: \begin{slide}{}
                     71: \begin{center}
                     72: \fbox{\fbc \large $BL5J?J}J,2r(B ($B$D$E$-(B) }
                     73: \end{center}
                     74:
                     75: $B;D$j(B $f = GH$ $B$G(B,  $f' = 0$
                     76:
                     77: $B$3$l$r(B $x_i$ $B$K$D$$$F7+$jJV$7$F;D$C$?(B $f$
                     78:
                     79: $\Rightarrow$ $df/dx_1 = \ldots = df/dx_n = 0$
                     80:
                     81: $\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
                     82:
                     83: $\Rightarrow$ $F$ $B$OM-8BBN$@$+$i(B $f = g^p$ $B$H=q$1$k(B
                     84:
                     85: $\Rightarrow$ $g$ $B$KBP$7$F%"%k%4%j%:%`$rE,MQ(B
                     86: \end{slide}
                     87:
                     88:
                     89: \begin{slide}{}
                     90: \begin{center}
                     91: \fbox{\fbc \large $B<BAu>e$N:$Fq(B : $\GCD(f,f')$ $B$N7W;;(B}
                     92: \end{center}
                     93:
                     94: $BI8?t$,(B 0 $B$N>l9g(B $\GCD(g,f'/g)=1$ $\Rightarrow$ $BB?JQ?t$N(B Hensel $B9=@.$,(B
                     95: $B;H$($k(B
                     96:
                     97: $B@5I8?t$N>l9g(B $$\GCD(g,f'/g) = \GCD(\GCD(F,F')GH,F'/\GCD(F,F'))$$
                     98: $\Rightarrow$ $GH$ $B$NB8:_$N$?$a(B GCD $B$,(B 1 $B$H$O8B$i$J$$(B.
                     99:
                    100: $\Rightarrow$ $B$d$`$J$/(B Brown $B$N%"%k%4%j%:%`(B ($BCf9q>jM>DjM}$K$h$k(B GCD $B$N(B
                    101: $B7W;;(B) $B$rMQ$$$F$$$k(B.
                    102: \end{slide}
                    103:
                    104: \begin{slide}{}
                    105: \begin{center}
                    106: \fbox{\fbc \large GCD $B$N7W;;(B}
                    107: \end{center}
                    108:
                    109: \begin{tabbing}
                    110: $BF~NO(B : $f_1,\ldots,f_m \in K[X]$ ($K$ $B$OBN(B, $X$ $B$OJQ?t$N=89g(B)\\
                    111: $B=PNO(B : $\GCD(f_1,\ldots,f_m)$\\
                    112: $y \leftarrow$ $BE,Ev$JJQ?t(B; $Z \leftarrow X\setminus \{y\}$\\
                    113: $< \leftarrow K[Z]$ $B$NE,Ev$J9`=g=x(B; $B0J2<(B $f_i \in K[y][Z]$ $B$H$_$J$9(B\\
                    114: $h_i(y) \leftarrow \HT_<(f_i)$; $h_g(y) \leftarrow \GCD(h_1,\ldots,h_m)$\\
                    115: $g \leftarrow 0$; $M \leftarrow 1$\\
                    116: do \= \\
                    117:    \> $a \leftarrow $ $BL$;HMQ$N(B $K$ $B$N85(B\\
                    118:    \> $g_a \leftarrow \GCD(f_1|_{y=a},\ldots,f_m|_{y=a})$\\
                    119:    \> if \= $g \neq 0$ $B$+$D(B $\HT_<(g) = \HT_<(g_a)$ then \\
                    120:    \>    \> $adj \leftarrow h_g(a)/\HC_<(g_a)\cdot g_a - g(a)$
                    121: \end{tabbing}
                    122: \end{slide}
                    123:
                    124: \begin{slide}{}
                    125: \begin{tabbing}
                    126: do \= if \= \kill
                    127:    \>    \> if \= $adj = 0$ $B$+$D(B, $B$9$Y$F$N(B $f_i$ $B$KBP$7(B $g | h_g\cdot f_i$  then \\
                    128:    \>    \>    \> return $\pp(g)$\\
                    129:    \>    \> endif\\
                    130:    \>    \> $g \leftarrow g+adj \cdot M(a)^{-1} \cdot M$; $M \leftarrow M\cdot (y-a)$\\
                    131:    \> else if $\tdeg(\HT_<(g)) > \tdeg(\HT_<(g_a))$ then \\
                    132:    \>    \> $g \leftarrow g_a$; $M \leftarrow  y-a$\\
                    133:    \> else if $\tdeg(\HT_<(g)) = \tdeg(\HT_<(g_a))$ then \\
                    134:    \>    \> $g \leftarrow 0$; $M \leftarrow 1$\\
                    135:    \> endif\\
                    136: end do
                    137: \end{tabbing}
                    138: \end{slide}
                    139:
                    140: \begin{slide}{}
                    141: \begin{center}
                    142: \fbox{\fbc \large $BFsJQ?t$X$N5"Ce(B}
                    143: \end{center}
                    144:
                    145: \begin{itemize}
                    146: \item $B<gJQ?t(B $x$ $B$NA*Br(B
                    147:
                    148: $x$ $B$K4X$9$kHyJ,$,>C$($J$$$h$&$KA*$V(B.
                    149:
                    150: \item $B=>JQ?t(B $y$ $B$NA*Br(B
                    151:
                    152: $K[x,y]$ $B$G0x?tJ,2r$7$F(B, $Z=X\setminus \{x,y\}$ $B$K4X$7$F(B Hensel $B9=@.(B
                    153:
                    154: ($B0lJQ?t$^$GMn$9$H%K%;0x;R$,BgNLH/@8(B)
                    155:
                    156: \item $B$=$l0J30$NJQ?t(B $Z$ $B$X$NBeF~CM$NA*Br(B
                    157:
                    158: $f_a(x,y) = f(x,y,a)$ $B$,L5J?J}$K$J$k$h$&$KA*$V(B.
                    159:
                    160: $B$5$i$K(B, $f_a|_{y=0}$ $B$bL5J?J}$K$J$k$h$&$K(B, $y\leftarrow y+c$ $B$H(B
                    161: $BJ?9T0\F0(B.
                    162: \end{itemize}
                    163:
                    164: \end{slide}
                    165:
                    166: \begin{slide}{}
                    167: \begin{center}
                    168: \fbox{\fbc \large $K[y]$ $B>e$G$N(B Hensel $B9=@.(B ($BA0=hM}(B)}
                    169: \end{center}
                    170:
                    171: $f_a(x,y)$ $B$N0x;R$r(B 2 $BAH$K$o$1(B $f_a(x,y) = g_0(x,y)h_0(x,y)$
                    172: $B$+$i(B $K[y]$ $B>e$G(B Hensel $B9=@.(B
                    173:
                    174: $g_0$, $h_0$ $B$N(B $x$ $B$K4X$9$k<g78?t$N7h$aJ}(B
                    175:
                    176: $B<g78?tLdBj$N2sHr(B : $B??$N0x;R$N<g78?t$H$J$k$Y$/6a$$$b$N$r$"$i$+$8$a8GDj(B
                    177:
                    178: $B??$N0x;R$N<g78?t$O(B $\lc_x(f)$ $B$N0x;R$G$"$k$3$H$r;H$C$?8+@Q$j(B
                    179: \end{slide}
                    180:
                    181: \begin{slide}{}
                    182: \begin{center}
                    183: \fbox{\fbc \large $B<g78?t$N8+@Q$j(B}
                    184: \end{center}
                    185: \begin{enumerate}
                    186: \item $\lc_x(f) = \prod u_i^{n_i}$ $B$H0x?tJ,2r$9$k(B ($u_i \in K[y,Z]$ : $B4{Ls(B).
                    187:
                    188: \item $B3F(B $i$ $B$KBP$7(B, $u_i(a) \in K[y]$ $B$,(B $\lc_x(g_0)$ $B$r3d$j@Z$k2s?t$r(B
                    189: $B?t$($k(B. $B$=$l$r(B $m_i$ $B$H$7$?$H$-(B, $\lc_g = \prod u_i^{m_i}$ $B$H$9$k(B.
                    190: $BF1MM$K(B $h_0$ $B$KBP$7$F$b(B $\lc_h$ $B$r5a$a$k(B.
                    191:
                    192: $B$b$7(B,
                    193: $\lc_x(g_0) \not{|}\, \lc_g(a)$ $B$^$?$O(B $\lc_x(h_0) \not{|}\, \lc_h(a)$
                    194: $B$^$?$O(B,
                    195: $\lc_x(f) \not{|}\, \lc_g \cdot \lc_h$
                    196: $B$J$i$P(B, $B$=$l$O(B, $f_a$ $B$N0x;R$NAH9g$;$,@5$7$/$J$$$3$H$r0UL#$9$k$N$G(B,
                    197: $g_0$, $h_0$ $B$r$H$jD>$9(B.
                    198:
                    199: \item
                    200:
                    201: $g_0 \leftarrow \lc_g(a)/\lc_x(g_0)\cdot g_0$ $B$N<g78?t$r(B $\lc_g$ $B$GCV$-49$($?$b$N(B
                    202:
                    203: $h_0 \leftarrow \lc_h(a)/\lc_x(h_0)\cdot h_0$ $B$N<g78?t$r(B $\lc_h$ $B$GCV$-49$($?$b$N(B
                    204:
                    205: $f \leftarrow \lc_g\cdot \lc_h/\lc_x(f) \cdot f$
                    206:
                    207: $B$H$9$k(B. $B$3$N;~(B, $f = g_0h_0$ $B$H$J$C$F$$$k(B.
                    208: \end{enumerate}
                    209: \end{slide}
                    210:
                    211: \begin{slide}{}
                    212: \begin{center}
                    213: \fbox{\fbc \large $K[y]$ $B>e$G$N(B Hensel $B9=@.(B}
                    214: \end{center}
                    215:
                    216: $f=g_0h_0$ $B$G(B, $g_0$ $B$,@5$7$$0x;R$N<M1F(B, $\lc_x(g_0)$ $B$H2>Dj(B
                    217:
                    218: $g_0$, $h_0$ $B$+$i(B $K[y]$ $B>e$N(BHensel $B9=@.$K$h$j(B,
                    219: $$f=g_kh_k \bmod I^{k+1}$$
                    220: $B$H;}$A>e$2$k(B ($I = \langle z_1-a_1,\ldots,z_{n-2}-a_{n-2} \rangle$).
                    221:
                    222: $z_i \rightarrow z_i+a_i$ $B$J$kJ?9T0\F0$K$h$j(B,
                    223: $I=\langle z_1,\ldots,z_{n-2} \rangle$
                    224:
                    225: $BDL>o$N(B EZ $BK!(B : $\Z/(p^l)$ $B$G7W;;(B ($B78?t$KJ,?t$,8=$l$k$N$rHr$1$k(B)
                    226:
                    227: $B:#2s$N<BAu(B : $\deg_y(f) > d$ $B$J$k(B $d$ $B$KBP$7(B, $K[y]/(y^d)$
                    228: $B>e$G7W;;$9$k(B. ($K[y]$ $B$G$N>&BN$G$N1i;;$rHr$1$k(B)
                    229:
                    230: $B$3$l$O(B, $u g_0(a)+v h_0(a)=1 \bmod y^d$ $B$H$J$k(B $u, v \in K[y]$
                    231: $B$K$h$j2DG=(B
                    232:
                    233: Hensel $B9=@.$O(B $\bmod\,  y^d$ $B$G9T$&(B.
                    234: \end{slide}
                    235:
                    236: \begin{slide}{}
                    237: \begin{center}
                    238: \fbox{\fbc \large Hensel $B9=@.(B}
                    239: \end{center}
                    240: $f = g_kh_k \bmod (I^{k+1},y^d)$ $B$@$,(B,
                    241: $B==J,Bg$-$$(B $k$ $B$KBP$7(B $f = g_kh_k$
                    242:
                    243: $u$, $v$ $B$N7W;;(B : Hensel $B9=@.(B
                    244: ($g_0(a)|_{y=0}$, $h_0(a)_{y=0}$ $B$,8_$$$KAG(B)
                    245:
                    246: $K[y]$ $B>e$N(B Hensel $B9=@.$O<!$N$h$&$K9T$&(B.
                    247:
                    248: \begin{enumerate}
                    249: \item $f-g_{k-1}h_{k-1} = \sum_t F_t t \bmod (I^k,y^d)$ $B$H=q$/(B.
                    250: $B$3$3$G(B $t \in I^k$ $B$OC19`<0(B, $F_t \in K[y][x]$.
                    251: \item $G_th_0+H_tg_0 = F_t \bmod y^d$ $B$H$J$k(B $G_t, H_t \in K[y][x]$ $B$r7W;;$9$k(B.
                    252: $B$3$l$O(B $u$, $v$ $B$r;H$C$F:n$l$k(B.
                    253: \item $g_{k+1} \leftarrow g_k + \sum_t G_t t$,
                    254: $h_{k+1} \leftarrow h_k + \sum_t H_t t$ $B$H$9$l$P(B $f = g_{k+1}h_{k+1} \bmod (I^{k+1},y^d)$.
                    255: \end{enumerate}
                    256:
                    257: $\sum_t G_t t = 0$ $B$^$?$O(B $\sum_t H_t t = 0$ $\Rightarrow$ $B;n$73d$j(B
                    258:
                    259: $g_k$ $B$^$?$O(B $h_k$ $B$G(B $f$ $B$r3d$C$F$_$k$3$H$G(B, $B<!?t$N>e8B$^$G(B Hensel $B9=@.(B
                    260: $B$;$:$K(B, $B??$N0x;R$r8!=P$G$-$k(B.
                    261: \end{slide}
                    262:
                    263: \begin{slide}{}
                    264: \begin{center}
                    265: \fbox{\fbc \large $BM-8BBN$NI=8=$K$D$$$F(B}
                    266: \end{center}
                    267:
                    268: $B3F%"%k%4%j%:%`$K$*$$$F(B, $B78?tBN$N0L?t$,==J,Bg$-$$I,MW$"$j(B.
                    269:
                    270: $BBeF~$9$kE@$N?t$,ITB-$9$k(B $\Rightarrow$ $BBe?t3HBg(B
                    271:
                    272: $B7W;;8zN($,Mn$A$J$$$h$&(B, $B86;O:,$rMQ$$$?I=8=$r<BAu(B
                    273:
                    274: $B7gE@(B : $B<BMQE*$J0L?t$,(B $2^{16}$ $BDxEY$K8B$i$l$k(B
                    275:
                    276: $B2~NI(B : $BI8?t$,(B $2^{14}$ $B0J2<$N>l9g$K$O(B, $B86;O:,I=8=(B
                    277:
                    278: $B$=$l0J>e$N>l9g$K$O(B, $BDL>o$NI=8=(B
                    279: ($B<BMQ>e==J,$KBeF~$9$kE@$,F@$i$l$k$+$i(B)
                    280:
                    281: $\Rightarrow$ $B0L?t$,(B $2^{29}$ $BDxEY$^$G$NAGBN>e$G(B, $BB?JQ?tB?9`<0(B
                    282: $B$N0x?tJ,2r$,2DG=(B
                    283: \end{slide}
                    284:
                    285: \begin{slide}
                    286: \begin{center}
                    287: \fbox{\fbc \large $B78?t4D$H$7$F$N(B $K[y]/(y^d)$ $B$K$D$$$F(B}
                    288: \end{center}
                    289:
                    290: Hensel $B9=@.$K$*$$$F(B $K[y]/(y^d)$ $B$r78?t4D$H$7$F07$&(B
                    291:
                    292: Asir : $B>.0L?tM-8BBN(B $K$ $B$NBe?t3HBg$rI=8=$9$k7?(B (GFSN) $B$,$"$k(B
                    293:
                    294: $K[y]/(m(y))$ $B$H$7$FI=8=(B $\Rightarrow$ $m(y)=y^d$ $B$H$7$FN.MQ(B
                    295:
                    296: $B5U857W;;$K$D$$$F$O(B, 0 $B$G$J$$Dj?t9`$r;}$DB?9`<0$O2D5U(B ($B8_=|K!(B)
                    297:
                    298: $\lc_x \neq 0$ $B$h$j(B $K[y]/(y^d)$ $B$,$3$NJ}K!$G$G$-$k(B.
                    299:
                    300: $BB?JQ?tB?9`<0(B : Hensel $B9=@.$N:G=i$G(B, $B$3$N7?$N78?t$r;}$DB?9`<0$KJQ49(B
                    301:
                    302: $d$ $B$r%;%C%H$7$F$*$/(B $\Rightarrow$ $B7k2L$O<+F0E*$K(B $\bmod \, y^d$ $B$5$l$k(B
                    303:
                    304: $\Rightarrow$ $BDL>o$NB?9`<01i;;$K$h$j(B $K[y]/(y^d)$ $B78?t$N(B
                    305: $BB?9`<01i;;$,<B9T$G$-$k(B.
1.2     ! noro      306: \end{slide}
        !           307:
        !           308: \begin{slide}{}
        !           309: \begin{center}
        !           310: \fbox{\fbc \large Timing data (Wang $B$NNc(B)}
        !           311: \end{center}
        !           312:
        !           313: {\tt OpenXM\_contrib2/asir2000/lib/fctrdata} $B$N(B
        !           314:
        !           315:  {\tt Wang[1],\ldots,Wang[15]} $B$G%F%9%H(B.
        !           316:
        !           317: $B%^%7%s(B : Athlon 1900+
        !           318:
        !           319: Maple7 $B$HHf3S(B --- Maple7 $B$b(B Kernel $B$G=t1i;;$r%5%]!<%H$7$F$$$k$N$G(B, $B%"%s%U%'%"$G$O$J$$$@$m$&(B
        !           320:
        !           321: $B7k2L(B : $B0lIt(B ({\tt Wang[8]}) $B$r=|$$$FNI9%(B
        !           322: \end{slide}
        !           323:
        !           324: \begin{slide}{}
        !           325: \begin{center}
        !           326: \fbox{\fbc \large Timing data (Maple7)}
        !           327: \end{center}
        !           328:
        !           329: \begin{center}
        !           330: % &  &  &  &  &  &  &  &  &  &  &  &  &  &  &  \\ \hline
        !           331: {\small
        !           332: \begin{tabular}{c|ccccccccc} \hline
        !           333: $p$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline
        !           334: 2 & N & F & F & F & N & N & 0.01 & 1 & 0.01 \\ \hline
        !           335: 3 & 0.07 & 0.1 & 0.07 & N & 0.4 & N & 0.01 & 0.02 & 0.06 \\ \hline
        !           336: 5 & N & 0.05 & 0.08 & 3.5 & 0.2 & 0.4 & 0.01 & 0.6 & 0.1 \\ \hline
        !           337: 7 & 0.08  & 0.1  & 0.1  & 0.25 & 0.6  & 0.5  & 0.02  & 1  & F \\ \hline
        !           338: \end{tabular}
        !           339:
        !           340: \begin{tabular}{c|cccccc} \hline
        !           341: $p$ & 10 & 11 & 12 & 13 & 14 & 15 \\ \hline
        !           342: 2 & F & N & 0.005 & 0.006 & 0.008 & F \\ \hline
        !           343: 3 & 4 & N & 0.004 & 0.007 & 0.14  & 0.02 \\ \hline
        !           344: 5 & 0.2  & F  & 0.005 & 0.006 & 0.03  &  0.4 \\ \hline
        !           345: 7 & 0.6  & 14  & 0.005  & 0.16  & 0.04 & 0.6 \\ \hline
        !           346: \end{tabular}
        !           347:
        !           348: \begin{tabular}{c|ccccccccc} \hline
        !           349: $p$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline
        !           350: 547 & 0.2& 0.2& 0.1& 0.3& 1& 1.2& 0.02& 6& F\\ \hline
        !           351: 32003&  0.2& 0.2&  0.2& 0.4 & 1 & 1 & 0.02 & 4.2 & F  \\ \hline
        !           352: 99981793 & 0.5 & 0.6 & 0.5 & 3 & 3 & 4.5 & 0.02 & N &  F\\ \hline
        !           353: \end{tabular}
        !           354:
        !           355: \begin{tabular}{c|cccccc} \hline
        !           356: $p$ & 10 & 11 & 12 & 13 & 14 & 15 \\ \hline
        !           357: 547 & 0.9 &3.3  & 0.005 & 0.2 & 0.1 & 0.4  \\ \hline
        !           358: 32003 & 1.8 & 4.9 &0.006  & 0.3 & 0.1  & 0.4 \\ \hline
        !           359: 99981793 & 2.6  & 11  & 0.006 & 0.9 & 0.5  & 1.4  \\ \hline
        !           360: \end{tabular}
        !           361: }
        !           362: \end{center}
        !           363: \end{slide}
        !           364:
        !           365: \begin{slide}{}
        !           366: \begin{center}
        !           367: \fbox{\fbc \large Timing data (Asir)}
        !           368: \end{center}
        !           369:
        !           370: \begin{center}
        !           371: % &  &  &  &  &  &  &  &  &  &  &  &  &  &  &  \\ \hline
        !           372: {\small
        !           373: \begin{tabular}{c|ccccccccc} \hline
        !           374: $p$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline
        !           375: 2(5) & 0.003 & 0.003 & 0.004 & 0.01 & 0.02 & 0.05 & 0.001 & 0.01 & 0.0003 \\ \hline
        !           376: 3(5) & 0.003 & 0.002 & 0.005 & 0.003 & 0.003 & 0.1 & 0.002 & 0.001 & 0.003  \\ \hline
        !           377: 5(2) & 0.004 & 0.003 & 0.004 & 0.02 & 0.06 & 0.4 & 0.002 & 0.4 & 0.005 \\ \hline
        !           378: 7(2) & 0.004  & 0.004  & 0.005 & 0.03 & 0.1  & 0.1  & 0.004  & 1.8  & 0.2 \\ \hline
        !           379: \end{tabular}
        !           380:
        !           381: \begin{tabular}{c|cccccc} \hline
        !           382: $p$ & 10 & 11 & 12 & 13 & 14 &  15 \\ \hline
        !           383: 2(5) & 0.03 & 0.07 & 0.0006 & 0.001 & 0.002 & 0.001  \\ \hline
        !           384: 3(5) & 0.04 & 0.2 & 0.0001  & 0.0005 & 0.02  & 0.001 \\ \hline
        !           385: 5(2) & 0.01  & 0.2  & 0.001 & 0.001 & 0.004  & 0.01  \\ \hline
        !           386: 7(2) & 0.02  & 0.6  & 0.001  & 0.007  & 0.005 & 0.01 \\ \hline
        !           387: \end{tabular}
        !           388:
        !           389: \begin{tabular}{c|ccccccccc} \hline
        !           390: $p$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline
        !           391: 547 & 0.004 & 0.004 & 0.005 & 0.03 & 0.05 & 0.2 & 0.02& 2& 0.2\\ \hline
        !           392: 32003 & 0.004  &  0.004 & 0.005  &0.04  &0.07  & 0.2 & 0.004 & 2 & 0.2 \\ \hline
        !           393: 99981793& 0.004 & 0.004& 0.005 & 0.03 & 0.03 & 0.2 & 0.004 & 4 & 0.2  \\ \hline
        !           394: \end{tabular}
        !           395:
        !           396: \begin{tabular}{c|cccccc} \hline
        !           397: $p$ & 10 & 11 & 12 & 13 & 14 &  15 \\ \hline
        !           398: 547 & 0.04 & 0.3 & 0.001 &0.006  & 0.006 & 0.01  \\ \hline
        !           399: 32003 & 0.04 &0.2  &0.001  &0.007  & 0.006  & 0.03 \\ \hline
        !           400: 99981793 & 0.04  & 0.3  &0.001  & 0.008 & 0.008  & 0.01  \\ \hline
        !           401: \end{tabular}
        !           402: }
        !           403: \end{center}
1.1       noro      404: \end{slide}
                    405:
                    406: \begin{slide}{}
                    407: \begin{center}
                    408: \fbox{\fbc \large $B:#8e$NM=Dj(B}
                    409: \end{center}
                    410:
                    411: \begin{itemize}
                    412: \item $B@5I8?t$N=`AGJ,2r$N<BAu(B.
                    413:
                    414: \item $BBN$N0L?t$,B-$j$J$$>l9g$K(B, $B<+F0E*$K4pACBN$r3HBg$9$k(B.
                    415:
                    416: \item $BBN$NI8?t$,==J,Bg$-$$>l9g$K(B, $BL5J?J}J,2r$rI8?t(B 0 $B$H(B
                    417: $BF1MM$N(B Hensel $B9=@.$G9T$&$h$&$K$9$k(B.
                    418:
                    419: \item 2 $BJQ?t$N0x?tJ,2r$K$*$$$F(B, \cite{funny01} $B$G=R$Y$?(B, $BB?9`<0(B
                    420: $B;~4V%"%k%4%j%:%`$r<+F0E*$KA*Br$7$F<B9T$9$k(B.
                    421: \end{itemize}
                    422: \end{slide}
                    423:
                    424: \end{document}
                    425:
                    426: \begin{thebibliography}{99}
                    427: \bibitem{B97-2}
                    428: Bernardin, L. (1997).
                    429: On square-free factorization of multivariate polynomials over a finite
                    430: field.
                    431: {\em Theoret.\ Comput.\ Sci.\/} {\bf 187}, 105--116.
                    432:
                    433: \bibitem{funny01}
                    434: M. Noro and K. Yokoyama (2002).
                    435: Yet Another Practical Implementation of Polynomial Factorization
                    436:  over Finite Fields.
                    437: Proceedings of ISSAC2002, ACM Press, 200--206.
                    438: \end{thebibliography}
                    439: