Return to rims2001-noro.tex CVS log

Up to [local] / OpenXM / doc / Papers

Updates

% $OpenXM: OpenXM/doc/Papers/rims2001-noro.tex,v 1.3 2001/11/26 08:41:14 noro Exp $
\documentclass{slides}
\usepackage{color}
\usepackage{rgb}
\usepackage{graphicx}
\usepackage{epsfig}
\newcommand{\qed}{$\Box$}
\newcommand{\mred}[1]{\smash{\mathop{\hbox{\rightarrowfill}}\limits_{\scriptstyle #1}}}
\newcommand{\tmred}[1]{\smash{\mathop{\hbox{\rightarrowfill}}\limits_{\scriptstyle #1}\limits^{\scriptstyle *}}}
\def\gr{Gr\"obner basis }
\def\st{\, s.t. \,}
\def\ni{\noindent} 
\def\ve{\vfill\eject} 
\textwidth 9.2in
\textheight 7.2in
\columnsep 0.33in
\topmargin -1in
\def\tc{\color{red}}
\def\fbc{\bf\color{MediumBlue}}
\def\itc{\color{brown}}
\def\urlc{\bf\color{DarkGreen}}
\def\bc{\color{LightGoldenrod1}}

\title{\tc $B>.I8?tM-8BBN>e$NB?JQ?tB?9`<0$N0x?tJ,2r$K$D$$$F(B}

\author{$BLnO$(B $B@59T(B ($B?@8MBg!&M}(B)\\ $B2#;3(B $BOB90(B ($B6e=#Bg!&?tM}(B)}
\begin{document}
\large
\setlength{\parskip}{0pt}
\maketitle

\begin{slide}{}
\begin{center}
\fbox{\fbc \large $B$J$<(B ($B$$$^$5$i(B)$BM-8BBN>e$NB?JQ?tB?9`<0$N0x?tJ,2r(B?}
\end{center}

\begin{itemize}
\item Risa/Asir $B$K<BAu$5$l$F$$$J$$(B

$B$J$<$J$$$N$+(B, $B$H<+J,$G;W$&$3$H$O$7$P$7$P$"$C$?(B

\item $B@5I8?t=`AGJ,2r$KI,MW(B

$B2<;3(B-$B2#;3;;K!(B : $\sqrt{I}$ $B$NAG%$%G%"%kJ,2r(B $\Rightarrow$ $I$ $B$N=`AGJ,2r(B

$\sqrt{I}$ $B$NJ,2r$K$O(B, $BB?JQ?t$N0x?tJ,2r$,I,MW(B

$B$R$g$C$H$7$?$iBe?t4v2?Id9f$X$N1~MQ$,$"$k$+$b$7$l$J$$(B

\item Reed-Solomon $BId9f$N(B list decoding $B$X$N1~MQ$"$j(B

\item $B$=$l<+BN$*$b$7$m$$(B

$BI8?t$,>.$5$$>l9g(B (2,3,5,7 $B$J$I(B) $BFCM-$N:$Fq$,$"$k(B.

$BL5J?J}J,2r$G$N:$Fq(B

evaluation point $B$,B-$j$J$$>l9g(B
\end{itemize}
\end{slide}

\begin{slide}{}
\begin{center}
\fbox{\fbc \large $B%"%k%4%j%:%`$N35MW(B I : $BL5J?J}J,2r(B}
\end{center}

modification of Bernardin's algorithm [Ber97]

$f \in F[x_1,\ldots,x_n]$, $F$ : $BM-8BBN(B $Char(F) = p$

$f = FGH$, where $F=\prod f_i^{a_i}$, 
$G=\prod g_j^{b_j}$, 
$H=\prod h_k^{c_k}$ 

$f_i, g_j, h_k$ : $BL5J?J}(B, $B8_$$$KAG(B.

$'$ $B$r(B $d/dx_1$ $B$H$7$F(B
$f_i' \neq 0$, $p \not{|}a_j$, $p | b_j$, $h_k' = 0$
$B$H=q$/$H(B

$f' = F'GH$ $B$9$k$H(B $GCD(f,f') = GCD(F,F')GH$

$GCD(F,F') = \prod f_i^{a_i-1}$ $B$@$+$i(B $f/GCD(f,f')=\prod f_i$

$\prod f_i$ $B$G(B $f$ $B$r7+$jJV$73d$k$3$H$G(B, $f_1$ ($B=EJ#EY:G>.(B)
$B$,5a$^$k(B

$\Rightarrow$ $F$ $B$,A4$FJ,2r$G$-$k(B

\end{slide}

\begin{slide}{}
\begin{center}
\fbox{\fbc \large $BL5J?J}J,2r(B $B$D$E$-(B}
\end{center}

$B;D$j(B $f = GH$ $B$G(B,  $f' = 0$

$B$3$l$r(B $x_i$ $B$K$D$$$F7+$jJV$7$F;D$C$?(B $f$

$\Rightarrow$ $df/dx_1 = \ldots = df/dx_n = 0$ 

$\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

$\Rightarrow$ $F$ $B$OM-8BBN$@$+$i(B $f = g^p$ $B$H=q$1$k(B

$\Rightarrow$ $g$ $B$KBP$7$F%"%k%4%j%:%`$rE,MQ(B
\end{slide}


\begin{slide}{}
\begin{center}
\fbox{\fbc \large Bernardin $B$NJ}K!$H$NHf3S(B}
\end{center}
$BI8?t(B 0 $B$K$*$1$k(B Yun $B$NJ}K!(B : $B=EJ#EY$N8zN(E*7W;;(B

$B=EJ#EY$,9b$$>l9g$KM-Mx(B

Bernardin : $B@5I8?t$N>l9g$K$b(B Yun $B$NJ}K!$r=$@5$7$FE,MQ(B

$\Rightarrow$ $B=EJ#EY$,(B $p$ $B$h$jBg$-$$>l9g$KJ#;(2=(B

$\Rightarrow$ $p$ $B$,>.$5$$>l9g$K$O(B, $BC1=c$K=|;;$N7+$jJV$7$G=EJ#EY$r5a(B
$B$a$k(B

($B>\:Y$JHf3S$O$^$@9T$C$F$$$J$$(B)
\end{slide}

\begin{slide}{}
\begin{center}
\fbox{\fbc \large $B%"%k%4%j%:%`$N35MW(B II : $BFsJQ?t$X$N5"Ce(B}
\end{center}

\begin{itemize}
\item $B@0?t78?tB?JQ?tB?9`<0$N>l9g(B

$n$ $B$NFb(B $n-1$ $B8D$NJQ?t$r(B fix $\Rightarrow$ 1 $BJQ?t$G0x;R$N%?%M$r:n$k(B

$B%K%;0x;R$O$[$H$s$I=P$J$$(B

\item $BM-8BBN78?t$N>l9g(B

$B0lJQ?t$KMn$9$H%K%;0x;R$@$i$1(B

$\Rightarrow$ $Z[x]$ $B$KAjEv$9$k$N$O(B $F[y][x]$

\end{itemize}

\end{slide}

\begin{slide}{}
\begin{center}
\fbox{\fbc \large $B8=:_$N<BAu(B}

\begin{itemize}
\item $BL5J?J}J,2r$N%\%H%k%M%C%/$O(B $GCD(f,f')$

Brown's algorithm $B$G7W;;(B $\Rightarrow$ evaluation point $B$NITB-(B
$B$,LdBj(B $\Rightarrow$ $F$ $B$N3HBgBN$r;H$&(B ($B8e=R(B)

\item 2 $BJQ?t0J30$OA4$F(B Asir $B$G5-=R(B

\item 2 $BJQ?t$N$_(B builtin

$B8zN(>e(B critical $B$N$?$a(B $\Rightarrow$ $B$d$O$j(B $F$ $B$N3HBgBN$,I,MW(B

$B@0?t>e0lJQ?tB?9`<0$N0x?tJ,2r$H6K$a$FN`;w(B

\item 2 $BJQ?t$G%?%M$r:n$C$F(B, $B0lJQ?t$+$i2~$a$F(B Hensel $B9=@.(B

EEZ $B%"%k%4%j%:%`$r=q$1$F$$$J$$$?$a(B
\end{itemize}
\end{center}
\end{slide}

\begin{slide}{}
\begin{center}
\fbox{\fbc \large $BM-8BBN$NBe?t3HBg$N8zN(E*I=8=(B}
\end{center}

evaluation point $B$N3NJ]$N$?$a(B, $BM-8BBN$NBe?t3HBg$,I,MW(B

$F=GF(q)$ $B$N(B $m$ $B<!3HBg(B $F_m$ $B$r(B
$h(x) \in F[x]$ : $m$ $B<!4{Ls(B $B$K$h$j(B $F_m = F[x]/(h(x))$
$B$GI=8=(B

$\Rightarrow$ $B7W;;$,BgJQ(B

$q$ $B$O>.$G(B, $\#(F_m)$ $B$,$=$l$J$j$KBg$-$1$l$P$h$$(B

$\Rightarrow$ $F_m$ $B$r86;O:,I=8=$9$l$P$h$$(B

\end{slide}

\begin{slide}{}
\begin{center}
\fbox{\fbc \large $B86;O:,I=8=(B $F_m^{\times} = \{\alpha^i | ( 0 \le i \le q^m-2) \}$}
\end{center}
\begin{itemize}
\item $B$+$1;;(B, $B3d;;(B, $B$Y$->h$OMF0W(B

$\alpha^i \cdot \alpha^j = \alpha^{i+j \bmod q^m-1}$

\item $BB-$7;;(B, $B0z$-;;$O%F!<%V%k;2>H(B (Faug\`ere GB $B$GMQ$$$i$l$?(B)

$\alpha^i + 1 = \alpha^{a_i}$ $B$J$k(B $a_i$ $B$r7W;;$7(B, 
$(i,a_i)$ $B$r%F!<%V%k$GJ];}(B

$\alpha^i+\alpha^j = \alpha^j(\alpha^{i-j}+1)$ $B$H$7$F7W;;(B

\item $F_m$ $B$N%5%$%:$,(B $2^{16}$ $BDxEY$^$G$J$i<BMQE*(B

$BBN$r3HBg$7$F$b(B, $B7W;;B.EY$O$[$H$s$IJQ$o$i$J$$(B. 

\end{itemize}
\end{slide}

\begin{slide}{}
\begin{center}
\fbox{\fbc \large 2 $BJQ?t$N(B Hensel $B9=@.(B }
\end{center}

$f(x,y) = \prod_{i=1}^l f_i(x) \bmod y$

$\Rightarrow$ $f(x,y) = \prod_{i=1}^l f_{k,i}(x) \bmod y^k$ $B$X$N(B Hensel $B9=@.$O(B

$f(x,y) = f_{k,1} \cdot F_1 \bmod y^k$

$\Rightarrow$ $F_1(x,y) = f_{k,2} \cdot F_2 \bmod y^k$

$\Rightarrow$ $F_2(x,y) = f_{k,3} \cdot F_3 \bmod y^k$

$\cdots$

$B$H7W;;$7$F$$$/(B $\cdots$ $BC1=c$+$D9bB.(B


\end{slide}

\begin{slide}{}
\begin{center}
\fbox{\fbc \large Finding true factors}
\end{center}

\begin{itemize}
\item combination $\Rightarrow$ trial division

bound $B$h$j>/$7B?$a$K(B Hensel $B9=@.(B

$\Rightarrow$ $d-1$ test ($B:4!9LZ(B, Abbott et al.) $B$,$h$/8z$/(B

$B$7$+$7(B, $BAH$_9g$o$;GzH/$O9nI~$G$-$J$$(B

\item ``funny factorization''

change of ordering $B$K$h$j(B true factor $B$r8+$D$1$k(B

$B%K%;0x;R$,B?$$>l9g$K8z2LE*(B

\end{itemize}
\end{slide}

\begin{slide}{}
\begin{center}
\fbox{\fbc \large Funny factorization}
\end{center}

$f(x,y)$ : $x$ $B$K$D$$$F(B monic $B$H$9$k(B.

$f(x,y) \simeq g_k(x,y) h_k(x,y) \bmod y^k$

$B$KBP$7(B, $I=Id(g_k,y^k)$ $B$r9M$($k$H(B $\{g_k,y^k\}$ $B$O(B
$x<_l y$ $B$J$k(B lex order $B$G$N%0%l%V%J4pDl(B

$g_k| g \bmod y^k$, $g|f$ $B$J$k4{Ls0x;R(B $g$ $B$O(B $g\in I$.

\underline{$BDjM}(B}

$k$ $B$,==J,Bg$-$$$H$-(B, $g$ $B$O(B $I$ $B$N(B degree compatible order $<$ $B$G$N%0(B
$B%l%V%J4pDl$N=g=x:G>.$N85(B

[$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, 

$\#V(Id(g',g)) \le tdeg(g')\cdot tdeg(g)$ (B\'ezout) $B$@$,(B, 

$\#V(I) = k\deg_x(g_k) \le \#V(Id(g',g))$

$B$h$j(B $k$ $B$rBg$-$/$H$l$PL7=b(B. 
\end{slide}

\begin{slide}{}
\begin{center}
\fbox{\fbc \large Funny factorization $B$D$E$-(B}
\end{center}

$I$ $B$N(B $<_l$ $B$G$N%0%l%V%J4pDl$,J,$+$C$F$$$k(B

$\Rightarrow$ change of ordering $B$G(B $g$ $B$,7W;;$G$-$k(B

$k > tdeg(f)^2/\deg_x(g_k)$ $B$J$i(B deterministic

$B>.$5$$<!?t$N0x;R$r4|BT$7$F(B $k$ $B$r>.$5$/$H$k(B

$BFC$K(B, $\bmod y$ $B$G$N0x;R$,B?$$>l9g$KM-8z(B

\end{slide}

\begin{slide}{}
\begin{center}
\fbox{\fbc \large $B85$NBN$G$N0x;R$N7W;;(B}
\end{center}

$F = GF(q)$ $B>e$N4{Ls0x;R$,(B $F_m$ $B>e$GJ,2r$9$k2DG=@-$"$j(B

$f \in F[x_1,\ldots,x_n]$, $f$ : $F$ $B>e4{Ls$G(B 

$f = \prod f_i$, $f_i$ : $F_m$ $B>e4{Ls$H$9$k(B.

$F_m/F$ $B$O(B Galois $B3HBg$G(B, $G=Gal(F_m/F) = \langle \sigma \rangle$ 

$B$?$@$7(B $\sigma : \beta \mapsto \beta^q$

$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

$\prod_{s\in S}s \in F[x_1,\ldots,x_n]$. 

$f$ $B$O(B $F$ $B>e4{Ls$@$+$i(B $f = \prod_{s\in S}s$.

$\Rightarrow$ $F$ $B>e$N4{Ls0x;R(B = $F_m$ $B>e$N4{Ls0x;R$N(B $G$-orbit 

$\sigma(h)$ $B$O78?t$r(B $q$ $B>h$9$l$P$h$$$+$iMF0W(B. 

\end{slide}

\begin{slide}{}
\begin{center}
\fbox{\fbc \large $B%?%$%_%s%0%G!<%?(B --- [BM97] $B$+$i$NNc(B}
\end{center}

\underline{ 2 $BJQ?tB?9`<0(B}
\begin{center}
{\normalsize
\begin{tabular}{|c|c|c|c|c|c|c|} \hline
 & $f_2$ & $f_7$ & $f_{11}$ & $f_{13}$ & $f_{17}$ & $f_{17,y\rightarrow y^2}$ \\ \hline
$\deg_x,\deg_y$ & 7,5 & 100,100 & 300,300 & $10^3,10^3$ & 32,16 & 32,32 \\ \hline
\#factors & 2 & 2 & 1 & 2 & 1 & 2 \\ \hline
Maple7 & 4.2 & 30 & 68 & $>$1day & 36 & 32 \\ \hline
Asir & 0 ($2^3$) & 2.6($7^2$)  & 34  & 5040 & 0.24 & 0.57  \\ \hline
%Hensel & 0  &  & & 2965 &  &   \\ \hline
\end{tabular}
}
\end{center}
$f_p$ $B$r(B $GF(p)$ $B>e$G0x?tJ,2r(B

Asir $B$N(B $(p^m)$ : $GF(p^m)$ $B$^$G3HBg$9$kI,MW$,$"$C$?(B
\end{slide}

\begin{slide}{}
\fbox{\fbc \large Maple $B$H$NHf3S(B}

\begin{itemize}
\item Hensel $B9=@.$N@-G=Hf3S(B

$f_{11}$ $B$O(B Hensel $B9=@.$,$[$H$s$I(B $\Rightarrow$ Hensel $B9=@.(B
$B<+BN$N@-G=$OBg:9$J$$(B

[BM97] $B$K$h$l$P(B, $BAGBN>e$NB?9`<0$O(B kernel $B$GFCJL$K<BAu$5$l$F$$$k(B
(Asir $B$HF1$8(B)

\item $B2rC5:wIt$N@-G=Hf3S(B

$f_{17}$ $B$N>l9g(B, Maple $B$N7W;;;~4V$N$[$H$s$I$O(B bad combination $B$N(B
$BGS=|(B $\Rightarrow$ $B2?$+FCJL$J$3$H$r$7$F$$$FCY$$(B?

\item $B3HBg$,I,MW$J>l9g$NHf3S(B

Maple $B$G$O(B, $BBN$N3HBg$,I,MW$J>l9g$K$O(B, Domains package ($B0lHL$NM-8BBN$r(B
$B07$&(B generic $B$J<BAu(B) $B$r;H$&$?$a(B, $f_2$, $f_7$ $B$G:9$,=P$?(B
\end{itemize}
\end{slide}


\begin{slide}{}
\begin{center}
\fbox{\fbc \large $B%?%$%_%s%0%G!<%?(B --- $BBN$N3HBg$H8zN((B}
\end{center}

\begin{center}
{\normalsize
\begin{tabular}{|c|c|c|c|c|c|c|c|} \hline
$B3HBg<!?t(B  & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline
$f_7$ & ---  & 2.6 & 2.9 & 2.7 & 2.6 & 5.8 & 9.1 \\ \hline
$f_{17,y\rightarrow y^2}$ & 0.57 & 0.78 & 0.55 & 2.3 & --- & --- & --- \\ \hline
\end{tabular}
}
\end{center}

\underline{$B9M;!(B}

\begin{itemize}
\item $BBN$,>.$5$$$&$A$O(B, $B3HBg$7$F$b8zN($OMn$A$J$$(B

$B$b$A$m$s(B, $B3HBg$K$h$j0x;R$,A}$($k>l9g$O=|$/(B

\item $BBN$N%5%$%:$,Bg$-$/$J$k$H(B, $B5^7c$K8zN($,Mn$A$k(B

$B;2>H$9$k%F!<%V%k$,Bg$-$/$J$k(B $\Rightarrow$ $B%-%c%C%7%e%5%$%:$K4X78(B?
\end{itemize}
\end{slide}

\begin{slide}{}
\begin{center}
\fbox{\fbc \large $BAH$_9g$o$;GzH/$r5/$3$9>l9g(B}
\end{center}

$f(x,y) = f_{17}(x,y^2)f_{17}(x+1,y^2)$

$B??$N0x;R$O(B 4 $B8D(B, $\bmod y$ $B$G$N0x;R(B 32 $B8D(B

\underline{$BDL>o$N(B Belrekamp-Zassenhaus $B7?$G7W;;$7$?>l9g(B}

\begin{itemize}
\item $B=hM}$7$?AH$_9g$o$;(B : 3852356
\item $B<!?t%A%'%C%/$GGS=|(B : 3734707
\item $B7W;;;~4V(B : 162sec
\end{itemize}

\underline{Funny factorization $B$G7W;;$7$?>l9g(B}
\begin{itemize}
\item bound = 16 ($B$3$l$O4E$9$.(B)         2.6sec
\item bound = 32 ($B>/$J$/$H$b0x;R$O=P$k(B) 17sec
\end{itemize}
\end{slide}

\begin{slide}{}
\begin{center}
\fbox{\fbc \large $B:#8e$NM=Dj(B}
\end{center}

\begin{itemize}
\item $BL5J?J}J,2rIt$N2~NI(B, engine $BAH$_9~$_(B

\item 3 $BJQ?t0J>e$X$N(B Hensel $B9=@.$r(B EEZ $B2=(B

\item 2 $BJQ?tB?9`<0$N@Q$N(B, Karatsuba $B$K$h$k9bB.2=(B

\item Zassenhaus, Funny $B$N(B OpenXM $B$K$h$kJBNs2=(B

\item knapsack $B7?$N%"%k%4%j%:%`$NE,MQ2DG=@-$N8!F$(B
\end{itemize}
\end{slide}

\end{document}