Annotation of OpenXM/doc/Papers/rims2001-noro.tex, Revision 1.3
1.3 ! noro 1: % $OpenXM: OpenXM/doc/Papers/rims2001-noro.tex,v 1.2 2001/11/19 00:53:58 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}
1.3 ! noro 197: \fbox{\fbc \large $B86;O:,I=8=(B $F_m^{\times} = \{\alpha^i | ( 0 \le i \le q^m-2) \}$}
1.1 noro 198: \end{center}
199: \begin{itemize}
200: \item $B$+$1;;(B, $B3d;;(B, $B$Y$->h$OMF0W(B
201:
1.3 ! noro 202: $\alpha^i \cdot \alpha^j = \alpha^{i+j \bmod q^m-1}$
1.1 noro 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}
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>