[BACK]Return to rims-2002-noro-ja.tex CVS log [TXT][DIR] Up to [local] / OpenXM / doc / Papers

Annotation of OpenXM/doc/Papers/rims-2002-noro-ja.tex, Revision 1.4

1.4     ! noro        1: % $OpenXM: OpenXM/doc/Papers/rims-2002-noro-ja.tex,v 1.3 2002/12/09 02:09:23 noro Exp $
1.1       noro        2: \documentclass[theorem]{jarticle}
1.3       noro        3: %\usepackage{jssac}
1.4     ! noro        4: \topmargin -0.5in
        !             5: \oddsidemargin 0in
        !             6: \evensidemargin 0in
1.3       noro        7: %
1.4     ! noro        8: \textwidth 6in
        !             9: \textheight 9in
        !            10: \columnsep 0.33in
1.1       noro       11:
                     12: \def\HT{{\rm HT}}
                     13: \def\HC{{\rm HC}}
1.4     ! noro       14: \def\GF{{\rm GF}}
1.1       noro       15: \def\GCD{{\rm GCD}}
                     16: \def\tdeg{{\rm tdeg}}
                     17: \def\pp{{\rm pp}}
                     18: \def\lc{{\rm lc}}
                     19: \def\Z{{\bf Z}}
                     20:
                     21: \title{$BM-8BBN>e$NB?JQ?tB?9`<0$N0x?tJ,2r$K$D$$$F(B ($B$=$N(B 2)}
                     22:
                     23: \author{$BLnO$(B $B@59T(B ($B?@8MBg!&M}(B)}
                     24:
                     25: \begin{document}
                     26: \maketitle
                     27:
                     28: \section{$B$O$8$a$K(B}
                     29:
                     30: $BK\9F$G$O(B, \cite{funny01} $B$G=R$Y$?(B, $BM-8BBN>e$G$N(B 2 $BJQ?tB?9`<0$N0x?tJ,2r(B
1.3       noro       31: $B$r4pAC$H$7$F(B, $B0lHL$NB?JQ?tB?9`<0$N(B GCD, $BL5J?J}J,2r(B, $B0x?tJ,2r%"%k%4%j%:(B
                     32: $B%`$*$h$S$=$N<BAu$K$D$$$F=R$Y$k(B.
1.1       noro       33:
                     34: \section{$BB?JQ?tB?9`<0$NL5J?J}J,2r$H(B GCD}
                     35:
                     36: $B8=:_(B Risa/Asir $B$GMQ$$$F$$$k%"%k%4%j%:%`$O(B,
                     37: $B0J2<$K=R$Y$k$h$&$K(B,
                     38: Bernardin $B$NL5J?J}J,2r%"%k%4%j%:%`(B \cite{B97-2} $B$r(B
                     39: modify $B$7$?$b$N$G$"$k(B.
                     40:
                     41: $F$ $B$rI8?t(B $p$ $B$NM-8BBN$H$7(B, $f \in F[x_1,\ldots,x_n]$ $B$H(B
                     42: $B$9$k(B. $'$ $B$,(B $d/dx_1$ $B$rI=$9$H$9$k(B.
                     43: $$f = FGH, F=\prod f_i^{a_i}, G=\prod g_j^{b_j},
                     44: H=\prod h_k^{c_k}$$
                     45: ($f_i, g_j, h_k$ $B$OL5J?J}(B, $B8_$$$KAG$G(B,
                     46: $f_i' \neq 0$, $p \not{|}a_j$, $p | b_j$, $h_k' = 0$)
                     47: $B$H=q$/$H(B $f' = F'GH$ $B$,@.$jN)$D(B.
                     48: $B$9$k$H(B $$\GCD(f,f') = \GCD(F,F')GH$$ $B$G(B,
                     49: $\GCD(F,F') = \prod f_i^{a_i-1}$ $B$@$+$i(B
                     50: $$f/\GCD(f,f')=\prod f_i.$$
                     51: $\prod f_i$ $B$G(B $f$ $B$r7+$jJV$73d$j(B, $B3d$j@Z$l$J$/$J$C$?(B
                     52: $BCJ3,$G(B, $B$=$N>&$H(B $\prod f_i$ $B$N(B GCD $B$r7W;;$9$k$3$H$G(B,
                     53: $F$ $BCf$N=EJ#EY:G>.$N0x;R(B $f_1$ $B$,5a$^$k(B. $B$3$l$r7+$jJV$9$H(B
                     54: $F$ $B$,A4$FL5J?J}J,2r$G$-$k(B.
                     55: $B;D$j$N(B $f$ $B$O(B $f = GH$ $B$H=q$1$k(B. $B$3$3$G(B $f' = 0$ $B$,(B
                     56: $B@.$jN)$D$3$H$KCm0U$9$k(B. $B0J>e$N<jB3$-$r(B
                     57: $B3F(B $x_i$ $B$K$D$$$F7+$jJV$7$F;D$C$?(B $f$ $B$O(B,
                     58: $$df/dx_1 = \ldots = df/dx_n = 0$$
                     59: $B$rK~$?$9(B. $B$3$l$O(B, $BA4$F$N;X?t$,(B $p$
                     60: $B$G3d$j@Z$l$k$3$H$r0UL#$9$k(B. $B$9$k$H(B, $F$ $B$OI8?t(B $p$ $B$N(B
                     61: $BM-8BBN$@$+$i(B, $f = g^p$ $B$H=q$1$k$3$H$K$J$k(B.
                     62: $B$3$N(B $g$ $B$KBP$7$F(B, $B0J>e$N<jB3$-$r:F5"E*$KE,MQ$9$k(B
                     63: $B$3$H$G(B, $f$ $B$NL5J?J}J,2r$,F@$i$l$k(B.
                     64:
                     65: $B$3$N%"%k%4%j%:%`$K$*$$$F(B, $g=\GCD(f,f')$ $B$N7W;;$,I,MW$H$J$k(B.
                     66: $BI8?t$,(B 0 $B$N>l9g(B, $\GCD(g,f'/g)=1$ $B$,(B
                     67: $BJ]>Z$5$l$k$?$a(B, $B$3$N7W;;$KB?JQ?t$N(B Hensel $B9=@.$rMQ$$$k$3$H$,$G$-$k(B.
                     68: $B$7$+$7(B, $B@5I8?t$N>l9g$K$O(B,
                     69: $\GCD(g,f'/g) = \GCD(\GCD(F,F')GH,F'/\GCD(F,F'))$ $B$H$J$j(B,
                     70: $B0x;R(B $GH$ $B$NB8:_$N$?$a(B, $B$3$N(B GCD $B$,(B 1 $B$H$O8B$i$J$$(B. $B$3$N$?$a(B,
                     71: $B$d$`$J$/(B Brown $B$N%"%k%4%j%:%`(B ($BCf9q>jM>DjM}$K$h$k(B GCD $B$N7W;;(B)
                     72: $B$rMQ$$$F$$$k(B.
                     73:
                     74: \begin{tabbing}
                     75: GCD $B$N7W;;(B \\
                     76: $BF~NO(B : $f_1,\ldots,f_m \in K[X]$ ($K$ $B$OBN(B, $X$ $B$OJQ?t$N=89g(B)\\
                     77: $B=PNO(B : $\GCD(f_1,\ldots,f_m)$\\
                     78: $y \leftarrow$ $BE,Ev$JJQ?t(B; $Z \leftarrow X\setminus \{y\}$\\
                     79: $< \leftarrow K[Z]$ $B$NE,Ev$J9`=g=x(B; $B0J2<(B $f_i \in K[y][Z]$ $B$H$_$J$9(B\\
                     80: $h_i(y) \leftarrow \HT_<(f_i)$; $h_g(y) \leftarrow \GCD(h_1,\ldots,h_m)$\\
                     81: $g \leftarrow 0$; $M \leftarrow 1$\\
                     82: do \= \\
                     83:    \> $a \leftarrow $ $BL$;HMQ$N(B $K$ $B$N85(B\\
                     84:    \> $g_a \leftarrow \GCD(f_1|_{y=a},\ldots,f_m|_{y=a})$\\
                     85:    \> if \= $g \neq 0$ $B$+$D(B $\HT_<(g) = \HT_<(g_a)$ then \\
1.3       noro       86:    \>    \> $adj \leftarrow h_g(a)/\HC_<(g_a)\cdot g_a - g(a)$\\
                     87:    \>    \> 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 \\
1.1       noro       88:    \>    \>    \> return $\pp(g)$\\
                     89:    \>    \> endif\\
                     90:    \>    \> $g \leftarrow g+adj \cdot M(a)^{-1} \cdot M$; $M \leftarrow M\cdot (y-a)$\\
1.3       noro       91:    \> else if $\tdeg(\HT_<(g)) > \tdeg(\HT_<(g_a))$ then \\
1.1       noro       92:    \>    \> $g \leftarrow g_a$; $M \leftarrow  y-a$\\
                     93:    \> else if $\tdeg(\HT_<(g)) = \tdeg(\HT_<(g_a))$ then \\
                     94:    \>    \> $g \leftarrow 0$; $M \leftarrow 1$\\
                     95:    \> endif\\
                     96: end do
                     97: \end{tabbing}
                     98:
                     99: $\HT$ $B$OF,9`(B, $\HC$ $B$OF,78?t(B, $\tdeg$ $B$OA4<!?t(B, $\pp$ $B$O86;OE*ItJ,(B
                    100: $B$rI=$9(B.
                    101:
                    102: $B$3$N%"%k%4%j%:%`$G$O(B, $f_1, \ldots, f_m$ $B$KBP$7(B, $B$"$kJQ?t(B $y$ $B$K$5$^$6$^$J(B
                    103: $BCM(B $a$
                    104: $B$rBeF~$7$F(BGCD $g_a$ $B$r7W;;$7(B, $B$=$l$i$rCf9q>jM>DjM}$G7k9g$9$k(B. $B$=$N:](B,
                    105: $B;D$j$NJQ?t(B $Z$ $B$K4X$7$FE,Ev$J9`=g=x(B $<$ $B$r@_Dj$7(B, $B$=$N9`=g=x$K4X$9$kF,(B
                    106: $B9`$,Ey$7$$4V$O(B, $B??$N(B GCD $B$N@5$7$$<M1F$K$J$C$F$$$k$H(B
                    107: $B2>Dj$9$k(B. $B$=$l$^$G$H0[$J$kF,9`$r;}$D(B $g_a$ $B$,F@$i$l$?>l9g(B,
                    108: $B$=$NF,9`$NA4<!?t$,(B, $B$=$l$^$G$NF,9`$NA4<!?t$h$j??$KBg$-$$>l9g$K$O(B,
                    109: $BL@$i$+$K@5$7$/$J$$$N$G(B, $B<N$F$k(B. $B$^$?(B, $B??$K>.$5$$>l9g$K$O(B, $B$3$l$^$G(B
                    110: $B$N7k2L$O@5$7$/$J$$$3$H$K$J$j(B, $B?7$?$K(B $g_a$ $B$+$i%j%9%?!<%H$9$k(B.
                    111: $B$b$7(B, $BA4<!?t$,Ey$7$1$l$P(B, $BN>J}$N7k2L$,@5$7$/$J$$$3$H$K$J$j(B,
                    112: $BN>J}$r<N$F$F%j%9%?!<%H$9$k(B.
                    113:
                    114: $B$^$?(B, $B??$N(B GCD $B$N(B $<$ $B$K4X$9$kF,78?t$,(B
                    115: $f_i$ $B$NF,78?t$N(B GCD $B$G$"$k(B $h_g$ $B$N0x;R$K$J$C$F$$$k$3$H$rMQ$$(B, $BCf9q>jM>DjM}$r(B
                    116: $BE,MQ$9$k:](B, $BF,78?t$,(B $h_g$ $B$K$J$k$h$&$KD4@a$7$F$$$k(B.
                    117:
                    118: $B?7$?$J(B $a$ $B$GF@$?(B $g_a$ $B$H(B, $B$3$l$^$GF@$?(B $g$ $B$N(B $a$ $B$G$NCM$,(B
                    119: $BEy$7$$>l9g$K(B, $B<B:]$K(B $g$ $B$,(B $h_gf_i$ $B$r$9$Y$F3d$j@Z$k$+%A%'%C%/$r(B
                    120: $B9T$C$F$$$k(B. $B<B:]$N<BAu$K$*$$$F$O(B, $BE,Ev$J(B $f_i$ $B$rA*$s$G$*$-(B,
                    121: cofactor $B$N$[$&$bCf9q>jM>DjM}$G9=@.$7$F$$$-(B, $B$=$A$i$G$b3d;;%A%'%C%/(B
                    122: $B$r9T$&$3$H$G(B, GCD, cofactor $B$$$:$l$+$,I|85$G$-$?;~E@$G%"%k%4%j%:%`(B
                    123: $B$,=*N;$G$-$k(B.
                    124:
                    125: $B$3$N%"%k%4%j%:%`$G$O(B, GCD $B$N(B $y$ $B$K4X$9$k<!?t$h$jB?$$(B $K$ $B$N85$,I,MW(B
                    126: $B$K$J$k(B. $K$ $B$N0L?t$,$3$l$KK~$?$J$$>l9g$K$O(B, $K$ $B$r3HBg$9$k(B. $B$3$l$K(B
                    127: $B$D$$$F$O8e$G=R$Y$k(B.
                    128:
                    129: \section{$BL5J?J}B?9`<0$N0x?tJ,2r(B}
                    130:
                    131: $B0J2<(B, $f \in K[X]$ $B$OL5J?J}$H$9$k(B. $f$ $B$N0x?tJ,2r$O<!$N$h$&$K9T$&(B.
                    132:
                    133: \subsection{$B<gJQ?t(B $x$ $B$NA*Br(B}
                    134:
                    135: $f$ $B$N0x?tJ,2r$O(B, $B$"$kJQ?t(B $x$ $B0J30$NJQ?t$KE,Ev$JCM$rBeF~$7$FF@$i$l$?(B
                    136: $x$ $B$N0lJQ?tB?9`<0$N0x?tJ,2r$r%?%M$+$i=g<!(B Hensel $B9=@.$K$h$j7W;;$9$k(B (EZ $BK!(B).
                    137: $x$ $B$O(B, $x$ $B$K4X$9$kHyJ,$,>C$($J$$$h$&$KA*$VI,MW$,$"$k(B.
                    138: $B$^$?(B, $x$ $B$K4X$9$k<!?t$,Bg$-$$Dx(B, $B%?%M$H$J$k0x;R$N?t$,Bg$-$/$J$k2DG=@-$,(B
                    139: $B$"$k$?$a(B, $B$J$k$Y$/<!?t$,>.$5$$$h$&$J(B $x$ $B$rA*$s$G$$$k(B.
                    140:
                    141: \subsection{$B=>JQ?t(B $y$ $B$NA*Br(B}
                    142:
                    143: $B=>JQ?t$H$OL/$JMQ8l$G$"$k$,(B, $B$3$3$G$O(B, $BB?JQ?t$N0x?tJ,2r$r(B, 2 $BJQ?t$N0x?t(B
                    144: $BJ,2r$+$i(B Hensel $B9=@.$K$h$jF@$k$?$a(B, $B$=$N$?$a$NJQ?t$r$b$&0l$DA*$s$G$*$/(B
                    145: $BI,MW$,$"$k(B. $B$9$J$o$A(B, $B$"$kJQ?t(B $y$ $B$rA*$S(B, $x$, $y$ $B0J30$NJQ?t$K(B
                    146: $BE,Ev$JCM$rBeF~$7$?(B 2 $BJQ?tB?9`<0$N0x?tJ,2r$r(B \cite{funny01} $B$G=R$Y$?(B
                    147: $BJ}K!$K$h$j7W;;$9$k(B. $B$=$l$r4p$K(B, $B;D$j$NJQ?t$K4X$7$F(B Hensel $B9=@.$r(B
                    148: $B9T$&(B. $B$3$3$G(B, Hensel $B9=@.$O(B $K[X] = K[y][x,Z]$
                    149: ($Z=X\setminus\{x,y\} = \{z_1,\ldots,z_{n-2}\}$) $B$H$_$J$7$F(B
                    150: $B9T$&(B. $B$9$J$o$A(B, $B0lJQ?tB?9`<04D(B $K[y]$ $B$r(B, $BM-M}?tBN>e$NB?JQ?tB?9`<0(B
                    151: $B$N0x?tJ,2r$K$*$1$k(B, $B@0?t4D$NN`;w$H$_$J$9$o$1$G$"$k(B. $B$3$&$9$k$3$H$K(B
                    152: $B$h$j(B, 1 $BJQ?t$NJ,2r$+$i=PH/$7$?>l9g$K@8$:$kBgNL$N%K%;0x;R$K$h$k:$Fq$r(B
                    153: $BHr$1$k$3$H$,$G$-$k(B. $B$"$H$G<($9$h$&$K(B, Hensel $B9=@.<+BN$b(B, $B@0?t>e$N(B
                    154: $B>l9g$NN`;w$NJ}K!$K$h$j9T$&$3$H$,$G$-$k(B.
                    155:
                    156: \subsection{2 $BJQ?t$N0x?tJ,2r(B}
                    157:
1.3       noro      158: $x$, $y$ $B$,7h$^$C$?$i(B, $f_a(x,y) = f(x,y,a)$ $B$,(B
1.1       noro      159: $BL5J?J}$K$J$k$h$&$K(B $Z$ $B$KBeF~$9$kCM$N%Y%/%H%k(B
                    160: $a = (a_1,\ldots,a_{n-2}) \in K^{n-2}$ $B$rA*$S(B, $f_a$ $B$r0x?tJ,2r$9$k(B.
                    161: $B$3$3$G(B, $f_a$ $B$N(B $x$ $B$K4X$9$k<g78?t(B
                    162: ($B$3$l$O(B $y$ $B$NB?9`<0(B) $B$NDj?t9`$,(B 0 $B$G$J$/(B, $B$+$D(B
                    163: $f_a|_{y=0}$ $B$,L5J?J}$G$"$k$h$&(B,
                    164: $BI,MW$,$"$l$P(B $y\rightarrow y+c$ $B$H$$$&J?9T0\F0$r9T$&(B.
1.3       noro      165: $B<B:]$K$O(B, $B$3$NA`:n$O(B 2 $BJQ?t$N0x?tJ,2r$G(B, $y$ $B$X$NBeF~CM$rC5$9(B
                    166: $B2>Dj$G9T$o$l$F$$$k$?$a(B, $B$=$N7k2L$r$=$N$^$^JV$9$h$&$JFbIt(B
                    167: $B%5%V%k!<%A%s$r8F$S=P$7$F$$$k(B.
1.1       noro      168:
                    169: \subsection{$K[y]$ $B>e$G$N(B Hensel $B9=@.(B ($BA0=hM}(B)}
                    170:
                    171: $f_a(x,y)$ $B$N0x?tJ,2r$N7k2L$h$j(B, $B0x;R$r(B 2 $BAH$K$o$1(B
                    172: $f_a(x,y) = g_0(x,y)h_0(x,y)$ $B$H$7$?>e$G(B, $K[y]$ $B>e$G(B Hensel $B9=@.$r(B
                    173: $B9T$&(B. $B$3$N:](B, $BLdBj$H$J$k$N$,(B $g_0$, $h_0$ $B$N(B $x$ $B$K4X$9$k<g78?t$N(B
1.3       noro      174: $B7h$aJ}$G$"$k(B. $BC1$K(B, $BAPJ}$N78?t$r(B $f$ $B$N(B $x$ $B$K4X$9$k<g78?t(B
                    175: $\lc_x(f)$ $B$K9g$o$;$k$H$$$&J}K!(B
                    176: $B$G$O(B, Hensel $B9=@.$NCJ?t$,ITI,MW$KA}$($k(B, $B$$$o$f$k<g78?tLdBj(B
                    177: $B$r5/$3$9(B. $B$3$l$r2sHr$9$k$?$a$K(B, $B??$N0x;R$N<g78?t(B
1.1       noro      178: $B$H$J$k$Y$/6a$$$b$N$r$"$i$+$8$a8GDj$7$F$*$/$N$,$h$$(B. $B>/$J$/$H$b(B,
1.3       noro      179: $B$=$l$O(B $\lc_x(f)$ $B$N0x;R$G$O$"$k(B.
1.1       noro      180: $BM-M}?tBN>e$N>l9g(B, P. S. Wang $B$K$h$j<g78?t$N7hDjJ}K!$,Ds0F$5$l$F(B
                    181: $B$$$k$,(B, $B$3$3$G$O<!$N$h$&$K8+@Q$b$k(B:
                    182:
                    183: \begin{enumerate}
                    184: \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).
                    185:
                    186: \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
                    187: $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.
                    188: $BF1MM$K(B $h_0$ $B$KBP$7$F$b(B $\lc_h$ $B$r5a$a$k(B.
                    189:
                    190: $B$b$7(B,
                    191: $\lc_x(g_0) \not{|}\, \lc_g(a)$ $B$^$?$O(B $\lc_x(h_0) \not{|}\, \lc_h(a)$
                    192: $B$^$?$O(B,
                    193: $\lc_x(f) \not{|}\, \lc_g \cdot \lc_h$
                    194: $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,
                    195: $g_0$, $h_0$ $B$r$H$jD>$9(B.
                    196:
                    197: \item
                    198:
                    199: $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
                    200:
                    201: $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
                    202:
                    203: $f \leftarrow \lc_g\cdot \lc_h/\lc_x(f) \cdot f$
                    204:
                    205: $B$H$9$k(B. $B$3$N;~(B, $f = g_0h_0$ $B$H$J$C$F$$$k(B.
                    206: \end{enumerate}
                    207: $B$3$NCJ3,$G(B, $B$b$7(B $g_0$ $B$,??$N0x;R$N<M1F$H$J$C$F$$$l$P(B, Hensel $B9=@.(B
                    208: $B$K$h$j(B, $f$ $B$N0x;R$K;}$A>e$k$O$:$G$"$j(B, $\lc_x(g_0)$ $B$O4{$K(B, $B??$N0x;R(B
                    209: $B$N<g78?t$KEy$7$/$J$C$F$$$k(B. $B$3$N>l9g(B, $h_0$ $B$bF1MM$N@-<A$rK~$?$9(B.
                    210:
                    211: \subsection{$K[y]$ $B>e$G$N(B Hensel $B9=@.(B}
                    212:
                    213: $BA09`$K$h$j(B, $f=g_0h_0$ $B$K$*$$$F(B,
                    214: $g_0$ $B$,@5$7$$0x;R$N<M1F$J$i$P(B, $\lc_x(g_0)$ $B$O(B
                    215: $B4{$K??$N0x;R$N<g78?t$KEy$7$$(B. $B$3$3$G$O(B, $g_0$, $h_0$ $B$+$i(B $K[y]$ $B>e$N(B
                    216: Hensel $B9=@.$K$h$j(B, $f=g_kh_k \bmod I^{k+1}$, $B$?$@$7(B
1.3       noro      217: $I = \langle z_1-a_1,\ldots,z_{n-2}-a_{n-2} \rangle$, $B$H$J$k(B $g_k$, $h_k$ $B$r(B EZ $BK!$K(B
1.1       noro      218: $B$h$j7W;;$9$k(B. $B$^$:(B, $z_i \rightarrow z_i+a_i$ $B$J$kJ?9T0\F0$K$h$j(B,
1.3       noro      219: $I=\langle z_1,\ldots,z_{n-2} \rangle$ $B$H$7$F$*$/(B. $BDL>o$N(B EZ $BK!$G$O(B, $B78?t$KJ,?t$,(B
1.1       noro      220: $B8=$l$k$N$rHr$1$k$?$a(B, $B0x;R$N78?t$NBg$-$5$NI>2A$+$iDj$a$i$l$k(B,
                    221: $B$"$kBg$-$JAG?t6R(B $p^l$ $B$rK!$H$7$F(B $\Z/(p^l)$ $B>e$G7W;;$9$k(B.
                    222: $B$3$3$G$O(B, $f$ $B$N(B $y$ $B$K4X$9$k<!?t$r1[$($k@0?t(B $d$ $B$KBP$7(B,
                    223: $K[y]/(y^d)$ $B$G$N1i;;$rF3F~$9$k$3$H$G(B, $K[y]$ $B$G$N>&BN$G$N1i;;$rHr$1$k(B.
                    224: $B$9$J$o$A(B, $u g_0(a)+v h_0(a)=1 \bmod y^d$ $B$H$J$k(B $u, v \in K[y]$ $B$r(B
                    225: $B7W;;$7$F$*$-(B, Hensel $B9=@.$N78?t$N7W;;$O(B $u, v$ $B$rMQ$$$F(B $\bmod\,  y^d$
                    226: $B$G9T$&$N$G$"$k(B. $B$3$N$H$-(B, $f = g_kh_k \bmod (I^{k+1},y^d)$ $B$@$,(B,
                    227: $d$ $B$,==J,Bg$-$$$?$a(B, $g_0$ $B$,??$N0x;R$N<M1F$J$i$P(B, Hensel $B9=@.$N0l0U(B
                    228: $B@-$K$h$j(B, $B==J,Bg$-$$(B $k$ $B$KBP$7(B $f = g_kh_k$ $B$H$J$k(B. $u$, $v$ $B$N7W;;$O(B,
                    229: $g_0(a)|_{y=0}$, $h_0(a)_{y=0}$ $B$,8_$$$KAG$G$"$k$3$H$rMxMQ$7$F(B,
                    230: $B$d$O$j(B Hensel $B9=@.$K$h$j7W;;$G$-$k(B.
                    231:
                    232: $K[y]$ $B>e$N(B Hensel $B9=@.$O<!$N$h$&$K9T$&(B.
                    233:
                    234: \begin{enumerate}
                    235: \item $f-g_{k-1}h_{k-1} = \sum_t F_t t \bmod (I^k,y^d)$ $B$H=q$/(B.
                    236: $B$3$3$G(B $t \in I^k$ $B$OC19`<0(B, $F_t \in K[y][x]$.
                    237: \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.
                    238: $B$3$l$O(B $u$, $v$ $B$r;H$C$F:n$l$k(B.
                    239: \item $g_{k+1} \leftarrow g_k + \sum_t G_t t$,
                    240: $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)$.
                    241: \end{enumerate}
                    242:
                    243: $B$3$NA`:n$K$*$$$F(B, $\sum_t G_t t$ $B$^$?$O(B $\sum_t H_t t$ $B$,(B 0 $B$H$J$C$?>l9g$K(B
                    244: $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
                    245: $B$;$:$K(B, $B??$N0x;R$r8!=P$9$k$3$H$,$G$-$k(B.
                    246:
                    247:
                    248: \section{$B<BAu$K$D$$$F(B}
                    249:
                    250: \subsection{$BM-8BBN$NI=8=$K$D$$$F(B}
                    251:
                    252: $B$3$3$G=R$Y$?3F%"%k%4%j%:%`$K$*$$$F$O(B, $B78?tBN$N0L?t$,==J,Bg$-$$I,MW$,$"(B
                    253: $B$k(B. \cite{funny01} $B$G=R$Y$?$h$&$K(B, $BBeF~$9$kE@$N?t$,ITB-$9$k>l9g$N$?$a(B
                    254: $B$K(B, $BBe?t3HBg$7$F$b7W;;8zN($,Mn$A$J$$$h$&$J(B, $B86;O:,$rMQ$$$?I=8=$r<BAu$7(B,
                    255: $B$=$NM-8z@-$r<($7$?(B. $B7gE@$H$7$F$O(B, $B$3$NI=8=$K$*$$$F(B, $B<BMQE*$J(B
                    256: $B0L?t$,(B $2^{16}$ $BDxEY$K8B$i$l$k$3$H$G$"$C$?(B. $B:#2s(B, $B$=$N2~NI$H$7$F(B, $BI8?t(B
                    257: $B$,(B $2^{14}$ $B0J2<$N>l9g$K$O(B, $B86;O:,I=8=$r5v$7(B, $B$=$l0J>e$N>l9g$K$O(B, $BDL>o$N(B
                    258: $BI=8=$r$H$k$3$H$K$7$?(B. $B$3$l$O(B, $B8e<T$G$O<BMQ>e==J,$KBeF~$9$kE@$,F@$i$l$k(B
                    259: $B$+$i$G$"$k(B. $B$3$l$K$h$j(B, $B0L?t$,(B $2^{29}$ $BDxEY$^$G$NAGBN>e$G(B, $BB?JQ?tB?9`<0(B
                    260: $B$N0x?tJ,2r$,9T$($k$h$&$K$J$C$?(B.
                    261:
1.2       noro      262: \subsection{$B78?t4D$H$7$F$N(B $K[y]/(y^d)$ $B$K$D$$$F(B}
1.1       noro      263:
1.2       noro      264: Hensel $B9=@.$K$*$$$F$O(B, $K[y]/(y^d)$ $B$r(B, $BB?9`<0$N78?t4D$H$7$F(B
                    265: $B07$&I,MW$,$"$k(B. Asir $B$K$*$$$F$O(B, $B4{$K(B, $B>.0L?tM-8BBN(B $K$ $B$NBe?t3HBg(B
                    266: $B$rI=8=$9$k7?$,$"$k$,(B, $B$3$l$O(B, $K[y]/(m(y))$ ($m(y)$ $B$O:G>.B?9`<0(B)
                    267: $B$H$7$FI=8=$5$l$F$$$k$?$a(B, $m(y)=y^d$ $B$H$9$l$P(B, $B2C8:>h;;$ON.MQ(B
                    268: $B$G$-$k(B. $B$^$?(B, $B=|;;$K8=$l$k5U857W;;$K$D$$$F$O(B, 0 $B$G$J$$Dj?t9`$r;}$D(B
                    269: $BB?9`<0$GI=8=$5$l$k85$K8B$l$P(B, $B$=$l$O(B $y^d$ $B$H8_$$$KAG$J$N$G(B
                    270: $B5U85$r;}$A(B, $B8_=|K!$G7W;;$G$-$k(B. $B4{$K=R$Y$?$h$&$K(B, $x$ $B$K4X$9$k<g78?t(B
                    271: $B$,(B 0 $B$G$J$$Dj?t9`$r;}$D$h$&$KJ?9T0\F0$7$F$"$k$N$G(B, $K[y]/(y^d)$ $B$N(B
                    272: $B7W;;$r(B, $B$3$3$G=R$Y$?J}K!$G9T$&$3$H$,$G$-$k(B.
                    273: $BB?JQ?tB?9`<0$O(B, Hensel $B9=@.$N:G=i$G(B, $B$3$N(B
1.1       noro      274: $B7?$N78?t$r;}$DB?9`<0$KJQ49$5$l$k(B. $B$"$i$+$8$a(B $d$ $B$r%;%C%H$7$F(B
                    275: $B$*$/$3$H$K$h$j(B, $B1i;;$O<+F0E*$K(B $\bmod \, y^d$ $B$5$l$k$?$a(B,
                    276: $BDL>o$NB?9`<01i;;$N8F$S=P$7$r9T$&$@$1$G(B, $K[y]/(y^d)$ $B78?t$N(B
                    277: $BB?9`<01i;;$,<B9T$G$-$k(B.
1.2       noro      278:
                    279: \section{$B%?%$%_%s%0%G!<%?(B}
                    280:
                    281: $BM-8BBN>e$NB?JQ?tB?9`<0$N0x?tJ,2r$rDs6!$7$F$$$k%7%9%F%`$O?t>/$J$$(B.
                    282: $BI.<T$NCN$kM#0l$N$b$N$O(B Maple $B$J$N$G(B, Maple $B$HHf3S$r9T$&(B. Maple $B$O(B,
                    283: $B$3$N5!G=$K4X$7$F$O(B, kernel $B$K$*$$$F@lMQ$NFC<l$J%G!<%?7?$rB?MQ$7$F(B
                    284: $B8zN($r>e$2$F$$$k$?$a(B, $BHf3S$9$k$3$H$O%"%s%U%'%"$G$O$J$$$H9M$($k(B.
1.4     ! noro      285: $BNc$H$7$F$O(B, P.S. Wang $B$K$h$k(B, $B<g78?tLdBj$r5/$3$7$d$9$$B?9`<0$N(B
        !           286: $BNc(B (Asir $B$N(B {\tt lib/fctrdata} $B$N(B {\tt Wang[1]} $B$+$i(B
        !           287: {\tt Wang[15]} $B$rMQ$$$?(B. $B%^%7%s$O(B Athlon 1900+ $B$GC10L$OIC(B,
        !           288: $p$ $B$O(B, $B4pACBN$NI8?t$rI=$9(B. $BI=$G(B $N$ $B$O(B 60 $BICBT$C$F$bEz$($,(B
        !           289: $B$G$J$$$b$N(B, $F$ $B$O(B, Maple $B$,2?$i$+$NM}M3$G%(%i!<$r=P$7$F(B
        !           290: $B7W;;$G$-$J$+$C$?$b$N$rI=$9(B. Asir $B$K$*$$$F(B $p(n)$ $B$O(B, $n$ $B<!3HBg(B,
        !           291: $B$9$J$o$A(B $\GF(p^n)$ $B>e$G0x?tJ,2r$r9T$C$?$3$H$r<($9(B. 8 $BHV$NB?9`<0(B
        !           292: $B$N$h$&$KNc30E*$K;~4V$,$+$+$k$b$N$O$"$k$,(B, $B$*$*$`$M(B, Asir $B$,(B
        !           293: $BNI9%$J%Q%U%)!<%^%s%9$r<($7$F$$$k(B.
        !           294:
        !           295: \begin{table}[hbtp]
        !           296: \begin{center}
        !           297: % &  &  &  &  &  &  &  &  &  &  &  &  &  &  &  \\ \hline
        !           298: {\normalsize
        !           299: \begin{tabular}{c|ccccccccc} \hline
        !           300: $p$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline
        !           301: 2 & N & F & F & F & N & N & 0.01 & 1 & 0.01 \\ \hline
        !           302: 3 & 0.07 & 0.1 & 0.07 & N & 0.4 & N & 0.01 & 0.02 & 0.06 \\ \hline
        !           303: 5 & N & 0.05 & 0.08 & 3.5 & 0.2 & 0.4 & 0.01 & 0.6 & 0.1 \\ \hline
        !           304: 7 & 0.08  & 0.1  & 0.1  & 0.25 & 0.6  & 0.5  & 0.02  & 1  & F \\ \hline
        !           305: \end{tabular}
        !           306:
        !           307: \begin{tabular}{c|cccccc} \hline
        !           308: $p$ & 10 & 11 & 12 & 13 & 14 & 15 \\ \hline
        !           309: 2 & F & N & 0.005 & 0.006 & 0.008 & F \\ \hline
        !           310: 3 & 4 & N & 0.004 & 0.007 & 0.14  & 0.02 \\ \hline
        !           311: 5 & 0.2  & F  & 0.005 & 0.006 & 0.03  &  0.4 \\ \hline
        !           312: 7 & 0.6  & 14  & 0.005  & 0.16  & 0.04 & 0.6 \\ \hline
        !           313: \end{tabular}
        !           314:
        !           315: \begin{tabular}{c|ccccccccc} \hline
        !           316: $p$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline
        !           317: 547 & 0.2& 0.2& 0.1& 0.3& 1& 1.2& 0.02& 6& F\\ \hline
        !           318: 32003&  0.2& 0.2&  0.2& 0.4 & 1 & 1 & 0.02 & 4.2 & F  \\ \hline
        !           319: 99981793 & 0.5 & 0.6 & 0.5 & 3 & 3 & 4.5 & 0.02 & N &  F\\ \hline
        !           320: \end{tabular}
        !           321:
        !           322: \begin{tabular}{c|cccccc} \hline
        !           323: $p$ & 10 & 11 & 12 & 13 & 14 & 15 \\ \hline
        !           324: 547 & 0.9 &3.3  & 0.005 & 0.2 & 0.1 & 0.4  \\ \hline
        !           325: 32003 & 1.8 & 4.9 &0.006  & 0.3 & 0.1  & 0.4 \\ \hline
        !           326: 99981793 & 2.6  & 11  & 0.006 & 0.9 & 0.5  & 1.4  \\ \hline
        !           327: \end{tabular}
        !           328: }
        !           329: \end{center}
        !           330: \caption{$B0x?tJ,2r(B (Maple7)}
        !           331: \end{table}
        !           332:
        !           333: \begin{table}[hbtp]
        !           334: \begin{center}
        !           335: % &  &  &  &  &  &  &  &  &  &  &  &  &  &  &  \\ \hline
        !           336: {\normalsize
        !           337: \begin{tabular}{c|ccccccccc} \hline
        !           338: $p$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline
        !           339: 2(5) & 0.003 & 0.003 & 0.004 & 0.01 & 0.02 & 0.05 & 0.001 & 0.01 & 0.0003 \\ \hline
        !           340: 3(5) & 0.003 & 0.002 & 0.005 & 0.003 & 0.003 & 0.1 & 0.002 & 0.001 & 0.003  \\ \hline
        !           341: 5(2) & 0.004 & 0.003 & 0.004 & 0.02 & 0.06 & 0.4 & 0.002 & 0.4 & 0.005 \\ \hline
        !           342: 7(2) & 0.004  & 0.004  & 0.005 & 0.03 & 0.1  & 0.1  & 0.004  & 1.8  & 0.2 \\ \hline
        !           343: \end{tabular}
        !           344:
        !           345: \begin{tabular}{c|cccccc} \hline
        !           346: $p$ & 10 & 11 & 12 & 13 & 14 &  15 \\ \hline
        !           347: 2(5) & 0.03 & 0.07 & 0.0006 & 0.001 & 0.002 & 0.001  \\ \hline
        !           348: 3(5) & 0.04 & 0.2 & 0.0001  & 0.0005 & 0.02  & 0.001 \\ \hline
        !           349: 5(2) & 0.01  & 0.2  & 0.001 & 0.001 & 0.004  & 0.01  \\ \hline
        !           350: 7(2) & 0.02  & 0.6  & 0.001  & 0.007  & 0.005 & 0.01 \\ \hline
        !           351: \end{tabular}
        !           352:
        !           353: \begin{tabular}{c|ccccccccc} \hline
        !           354: $p$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline
        !           355: 547 & 0.004 & 0.004 & 0.005 & 0.03 & 0.05 & 0.2 & 0.02& 2& 0.2\\ \hline
        !           356: 32003 & 0.004  &  0.004 & 0.005  &0.04  &0.07  & 0.2 & 0.004 & 2 & 0.2 \\ \hline
        !           357: 99981793& 0.004 & 0.004& 0.005 & 0.03 & 0.03 & 0.2 & 0.004 & 4 & 0.2  \\ \hline
        !           358: \end{tabular}
        !           359:
        !           360: \begin{tabular}{c|cccccc} \hline
        !           361: $p$ & 10 & 11 & 12 & 13 & 14 &  15 \\ \hline
        !           362: 547 & 0.04 & 0.3 & 0.001 &0.006  & 0.006 & 0.01  \\ \hline
        !           363: 32003 & 0.04 &0.2  &0.001  &0.007  & 0.006  & 0.03 \\ \hline
        !           364: 99981793 & 0.04  & 0.3  &0.001  & 0.008 & 0.008  & 0.01  \\ \hline
        !           365: \end{tabular}
        !           366: }
        !           367: \end{center}
        !           368: \caption{$B0x?tJ,2r(B (Asir)}
        !           369: \end{table}
1.2       noro      370: \section{$B$*$o$j$K(B}
                    371:
                    372: $B:#8e$NM=Dj$H$7$F(B, $B<!$N$h$&$J$3$H$r9M$($F$$$k(B.
                    373:
                    374: \begin{itemize}
1.3       noro      375: \item $B@5I8?t$N=`AGJ,2r$N<BAu(B.
1.2       noro      376:
1.3       noro      377: \item $BBN$N0L?t$,B-$j$J$$>l9g$K(B, $B<+F0E*$K4pACBN$r3HBg$9$k(B.
1.2       noro      378:
1.3       noro      379: \item $BBN$NI8?t$,==J,Bg$-$$>l9g$K(B, $BL5J?J}J,2r$rI8?t(B 0 $B$H(B
                    380: $BF1MM$N(B Hensel $B9=@.$G9T$&$h$&$K$9$k(B.
                    381:
                    382: \item 2 $BJQ?t$N0x?tJ,2r$K$*$$$F(B, \cite{funny01} $B$G=R$Y$?(B, $BB?9`<0(B
                    383: $B;~4V%"%k%4%j%:%`$r<+F0E*$KA*Br$7$F<B9T$9$k(B.
1.2       noro      384: \end{itemize}
1.1       noro      385:
                    386: \begin{thebibliography}{99}
                    387: \bibitem{B97-2}
                    388: Bernardin, L. (1997).
                    389: On square-free factorization of multivariate polynomials over a finite
                    390: field.
                    391: {\em Theoret.\ Comput.\ Sci.\/} {\bf 187}, 105--116.
                    392:
                    393: \bibitem{funny01}
                    394: M. Noro and K. Yokoyama (2002).
                    395: Yet Another Practical Implementation of Polynomial Factorization
                    396:  over Finite Fields.
                    397: Proceedings of ISSAC2002, ACM Press, 200--206.
                    398: \end{thebibliography}
                    399: \end{document}
                    400:

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>