Return to bib.tex CVS log

Up to [local] / OpenXM / doc / compalg

Updated the description of F_4.
Added references on the knapsack factorization algorithm.

%$OpenXM: OpenXM/doc/compalg/bib.tex,v 1.4 2001/02/27 08:07:24 noro Exp $
\begin{thebibliography}{99}
\bibitem{ABBOTT}
Abbott, J.A. et al, Factorisation of Polynomials: Old Ideas and Recent Results.
Trends in Computer Algebra (LNCS 296), 81-91.

\bibitem{ADAMS}
Adams, W., Loustaunau, P., An Introduction to Gr\"bner Bases. Graduate
Strudies in Mathematics, Vol. 3., AMS (1994).

\bibitem{ABRW}
Alonso, M. E., Becker, E., Roy, M. F., W\"ormann, T., Zeros,
Multiplicities and Idempotents for Zerodimensinal Systems.
Proc. MEGA94, Birkh\"auser (1996).

\bibitem{BW}
Becker, T., Weispfenning, V., Gr\"obner Bases. GTM 141, Springer-Verlag(1993).

\bibitem{BERL}
Berlekamp, E.R., Factoring Polynomials over Large Finite Fields.
Math. Comp. 24 (1970), 713-735.

\bibitem{GC}
Boehm, H.,Weiser, M., Garbage Collection in an Uncooperative Environment.
Software Practice \& Experience(September 1988), 807-820.

{\tt http://reality.sgi.com/boehm\_mti/gc.html}

\bibitem{BUCH}
Buchberger, B., Ein algorithmisches Kriterium {f\"ur} die
{L\"osbarkeit} eines algebraischen Geichungssystems. Aequ. Math. 4/3
(1970), 374-383.

\bibitem{CZ}
Cantor, D.G., Zassenhaus, H., On Algorithms for Factoring
Polynomials over Finite Fields.
Math. Comp. 36 (1981), 587-592.

\bibitem{WALK}
Collart, M. et al, Converting Bases with the Gr\"obner Walk.
J. Symb. Comp. 24/3/4(1997), 465-469.

\bibitem{COX}
Cox, D., Little, J., O'Shea, D., Ideals, Varieties, and Algorithms. 
UTM, Springer-Verlag (1992).

\bibitem{COX2}
Cox, D., Little, J., O'Shea, D., Using Algebraic Geometry.
GTM 185, Springer-Verlag (1998).

\bibitem{DAV}
Davenport, J.H. et al, Computer Algebra. Academic Press (1988).

\bibitem{DIXON}
Dixon, J. D., Exact Solution of Linear Equations Using P-Adic Expansions.
Numerische Mathematik {\bf 40} (1982), 137-141.

\bibitem{EISEN}
Eisenbud, D., Commutative Algebra with a View Toward Algebraic Geometry.
GTM 150, Springer-Verlag (1995).

\bibitem{FGLM}
Faug\`ere, J.C., Gianni, P., Lazard, D., Mora, T., Efficient
Computation of Zero-dimensional Gr\"obnerr Bases by Change of Ordering. J. 
Symb. Comp. 16/4(1993), 329-344.

\bibitem{F}
Faug\`ere, J.C.,
A new efficient algorithm for computing Groebner bases  ($F_4$),
Journal of Pure and Applied Algebra (139) 1-3 (1999), 61-88.

\bibitem{GEB}
Gebauer, R., M\"oller, H.M., On an installation of Buchberger's algorithm.
J. Symb. Comp. 6/2/3(1989), 275-286.

\bibitem{GEDDES}
Geddes, K.O. et al., Algorithms for Computer Algebra.
Kluwer Academic Publishers, Boston (1992).

\bibitem{GEL}
Gel'fond, A.O., Transcendental and Algebraic Numbers. New York, Dover (1960).

\bibitem{GTZ}
Gianni, P., Trager, B., Zacharias, G., Gr\"obner bases and primary
decomposition of polynomial ideals. J. Symb. Comp. 6/2,3(1988), 149-167.

\bibitem{SUGAR}
Giovini, A., Mora, T., Nielsi, G., Robbiano, L., Traverso, C., ``One
sugar cube, please'' OR Selection strategies in the Buchberger
algorithm.  Proc. ISSAC '91, 49-54.

\bibitem{HOEIJ}
van Hoeij, M., Factoring polynomials and the knapsack problem.
To appear in Journal of Number Theory. The preprint is available
from {\tt http://euclid.math.fsu.edu/\verb+~+hoeij/papers.html}.

\bibitem{KR}
$B%+!<%K%O%s(B, B.W., $B%j%C%A!<(B, D.M., $B%W%m%0%i%_%s%08@8l(B C $BBh(B 2 $BHG(B. 
$B6&N)=PHG(B (1989).

\bibitem{KNUTH}
Knuth, D.E., The Art of Computer Programming, Vol. 2. 
Seminumerical Algorithms, 2nd ed. Addison-Wesley (1981).

\bibitem{LENSTRA}
Lenstra, A.K., Lenstra, H.W., Lob\'asz, Factoring polynomials with
rational coefficients, Math, Ann. 261 (1982), 515-534.

\bibitem{SUB}
Loos, R., Generalized Polynomial Remainder Sequences.
Computing, Suppl. 4 (1982), 115-137.

\bibitem{MIG}
Mignotte, M., Mathematics for Computer Algebra.
Springer-Verlag (1982).

\bibitem{YUN}
Moses, J., Yun, D.Y.Y., The EZ GCD Algorithm, Proc. ACM Annual
Conf. (1973), 159-166.

\bibitem{NAGAO}
$B1JHxHF(B, $BBe?t3X(B. 
$B?7?t3X9V:B(B 4, $BD+AR=qE9(B (1983).

\bibitem{REP}
Noro, M., J. McKay,
Computation of replicable functions on Risa/Asir.
Proc. PASCO'97, ACM Press (1997), 130-138.

\bibitem{NS}
Noro, M. et al, Asir.

{\tt ftp://archives.cs.ehime-u.ac.jp/pub/asir2000}

\bibitem{NT}
Noro, M., Takeshima, T., Risa/Asir --- A Computer Algebra system.
Proc. ISSAC'92, ACM Press(1992), 387-396.

\bibitem{NY}
Noro, M., Yokoyama, K., New methods for the change-of-ordering in Gr\"obner
basis computation. Research Report ISIS-RR-95-8E, FUJITSU LABS, ISIS
(1995).

\bibitem{NY2} 
Noro, M., Yokoyama, K., A Modular Method to Compute the
Rational Univariate Representation of Zero-Dimensional Ideals.
J. Symb. Comp. {\bf 28}/1 (1999), 243-263.

\bibitem{OAKU}
$BBg0$5W=SB'(B, $B%0%l%V%J4pDl$H@~7?JPHyJ,J}Dx<07O(B ($B7W;;Be?t2r@OF~Lg(B).
$B>eCRBg3X?t3X9V5fO?(B No. 38 (1994).

\bibitem{ROBBIANO}
Robbiano, L., Term orderings on the polynomial ring. Proc. EUROCAL'85 (LNCS 204), 513-517.

\bibitem{SASAKI}
$B:4!9LZ7z><(B, $B?t<0=hM}(B. $B>pJs=hM}AQ=q(B 7, $B>pJs=hM}3X2q(B (1981). 

\bibitem{SY}
Shimoyama, T., Yokoyaka, K., Localization and Primary Decomposition of
Polynomial ideals. J. Symb. Comp. 22(1996), 247-277.

\bibitem{TAKAGI}
$B9bLZDg<#(B, $B=iEy@0?tO@9V5A(B $BBh(B 2 $BHG(B. $B6&N)=PHG(B (1971).

\bibitem{TAKAGI2}
$B9bLZDg<#(B, $BBe?t3X9V5A(B $B2~D{?7HG(B. $B6&N)=PHG(B (1965).

\bibitem{GMP} 
Torbj\"orn et al, GNU MP library. Free Software Foundation (1996).

{\tt http://www.fsf.org/software/gmp/gmp.html}

\bibitem{TRAGER} 
Trager, B.M., Algebraic Factoring and Rational Function Integration.
Proc. SYMSAC 76, 219-226.

\bibitem{TRAV}
Traverso, C., Gr\"obner trace algorithms. Proc. ISSAC '88 (LNCS 358), 125-138.

\bibitem{WANG}
Wang, P.S., An Improved Multivariate Polynomial Factoring Algorithm.
Math. Comp. 32(1978), 1215-1231.

\bibitem{WANG2}
Wang, P.S. et al, p-adic Reconstruction of Rational Numbers.
SIGSAM Bulletin 16(1982), 2-3.

\bibitem{SQFR}
Wang, P.S., Trager, B.M., New Algorithms for Polynomial Square-Free Decomposition over the Integers. 
SIAM J. Comp. 8(1979), 300-305.

\bibitem{BMOD}
Weber, K., The Accelerated Integer GCD Algorithm. ACM Transactions on Mathematic
al Software, Vol. 21, No. 1 (1995), 111-122.

\bibitem{SYMP}
$B5HED=UIW(B, $B%7%s%W%l%/%F%#%C%/?tCM2rK!(B.
$B?tM}2J3X(B, 33, 6 (1995), 27-46.

\bibitem{ZASS}
Zassenhaus, H., On Hensel Factorization I.
J. Number Theory 1 (1969), 291-311.
\end{thebibliography}

$BK\9V$G$O(B, $BM=HwCN<1$H$7$F(B, $B@~7ABe?t$*$h$SBe?t3X$N4pACE*$JFbMF$r2>Dj$7$F(B
$B$$$k(B. $B8e<T$K4X$7$F$O(B, $B6qBNE*$K$O72(B, $B4D(B, $BBN$J$I$NBe?t7O$K4X$9$k4pACE*;v(B
$B9`(B, $BFC$KBN$N3HBg$*$h$S%$%G%"%k$K4X$9$kCN<1$r;}$C$F$$$k$3$H$,K>$^$7(B
$B$$(B. $BNc$($P(B \cite{NAGAO} $B$J$I$rA&$a$k(B. \cite{KNUTH} $B$O(B, $B?t(B, $BB?9`<0$K4X(B
$B$9$k$5$^$6$^$J%"%k%4%j%:%`$,>\:Y$+$D@53N$K2r@b$5$l$F$$$F(B, $B<-=qE*$K;H$((B
$B$k(B. \cite{DAV}\cite{GEDDES}\cite{SASAKI} $B$O7W;;5!Be?t$N652J(B
$B=q(B. \cite{ADAMS}\cite{BW}\cite{COX}\cite{COX2}\cite{EISEN}\cite{OAKU} 
$B$O%0%l%V%J4pDl$"$k$$$O2D49Be?t$K4X$9$k652J=q(B. \cite{KR} $B$O(B C $B8@8l$NI8(B
$B=`E*$J2r@b=q$G$"$k(B.

$B0J2<(B, $B3F>O$K4X$7(B, $B;29M=q(B, $BO@J8$r5s$2$J$,$i4JC1$K?6$jJV$k(B. 

\noi
$BBh(B 2 $B>O(B:

$B$3$3$G=R$Y$?$N$O(B, CPU $B$*$h$S(B C $B8@8l$K4X$9$k:GDc8B$N$3$H$,$i$G$"$k(B. CPU 
$B$K4X$7$F$O(B, $BJ8;zDL$j(B CPU $BKh$K%^%K%e%"%k$,B8:_$9$k$,(B, $B6=L#$N$"$kJ}$O(B, 
$BNc$($P(B Pentium $B$J$I$N%^%K%e%"%k$rD/$a$F$_$F$O$I$&$@$m$&$+(B. C $B8@8l$K4X(B
$B$7$F$O?t$(@Z$l$J$$Dx$N2r@b=q$,$"$k$,(B, $BI.<T$O(B \cite{KR}$B$NB>$K$O(B, $B2?$i$+(B
$B$N%U%j!<%=%U%H%&%'%"$N%=!<%9%3!<%I$rFI$`$3$H$r$*4+$a$9$k(B. $BFC$K(B, {\tt
gmp} \cite{GMP} $B$OBh(B 3 $B>O$G=R$Y$?%"%k%4%j%:%`$*$h$S$h$j?J$s$@%"%k%4%j%:(B
$B%`$,<BAu$5$l$F$*$j(B, $B;29M$K$J$k$H;W$&(B.

\noi
$BBh(B 3 $B>O(B:

$B$3$3$G:G$bM}2r$7$K$/$$$N$O=|;;%"%k%4%j%:%`$G$"$m$&(B. $B3FJdBj$N>ZL@$O(B
$B>JN,$7$F$"$k$N$G(B, $BN}=,LdBj$H$7$F2r$$$F$_$l$P=|;;%"%k%4%j%:%`$N;EAH$_(B
$B$,$h$/J,$+$k$H;W$&(B. $B$3$l$i$OA4$F(B \cite{KNUTH} $B$K>ZL@$,$"$k(B. 
$B@0?t(B GCD $B$K$D$$$F$J$K$b=R$Y$J$+$C$?$,(B, Euclid $B8_=|K!$NB>$K(B binary
GCD $B%"%k%4%j%:%`$H$h$P$l$k%?%$%W$N%"%k%4%j%:%`$,$"$j(B, $BG\@:EY@0?t=|;;(B
$B$rMQ$$$J$$$?$a9bB.$K<B9T$G$-$k(B. $B$3$l$K4X$7$F$O$d$O$j(B \cite{KNUTH}
$B$K2r@b$5$l$F$$$k(B. $B$^$?(B, $B:G6a$3$N%?%$%W$N%"%k%4%j%:%`$r$5$i$K?J2=(B
$B$5$;$?$b$N$,Ds0F$5$l$F$$$k(B. $B$3$l$K$D$$$F$O(B \cite{BMOD} $B;2>H(B. 

\noi
$BBh(B 4 $B>O(B:

$BB?9`<0$r(B C $B$J$I$N9b5i8@8l$GI=8=$7(B, $B$=$N1i;;$r5-=R$7$F$_$k$3$H$O(B, 
$B%W%m%0%i%_%s%0$N$h$$N}=,$K$J$k(B. $B$=$N:]$KLdBj$H$J$k$N$,(B, $BITMW$K$J$C$?(B
$B%a%b%jNN0h$N3+J|$K4X$9$k$3$H$G$"$k(B. C $B8@8l$G$O$3$l$O%W%m%0%i%^$N(B
$B@UG$$G$"$k$,(B, $B$3$l$r<j:n6H$G9T$&$3$H$O(B, $B3+J|$7K:$l$K$h$k%a%b%j%j!<%/(B, 
$B$"$k$$$OITE,@Z$J3+J|$J$I(B, $B=EBg$+$D8+$D$1$K$/$$%P%0$N860x$H$J$j0W$$(B. 
$B$3$l$rKI$0$?$a$K(B, \cite{GC} $B$G(B, $B<+F0%,!<%Y%C%8%3%l%/%?IU$-$N%a%b%j(B
$B4IM}$,Ds0F$5$l$?(B. $B$3$l$O%U%j!<$J%5%V%k!<%A%s%i%$%V%i%j$H$7$FMxMQ(B
$B$G$-$k(B. $B$3$N>O$G$O(B, $BB?9`<0>h;;$N9bB.%"%k%4%j%:%`$H$7$F(B Karatsuba $BK!(B
$B$N$_$r<h$j>e$2$?$,(B, $B9b<!(B ($B?t==<!0J>e(B) $B$NB?9`<0$N>h;;$,B?$/I,MW$J>l9g(B
$B$K$O(B FFT $B%"%k%4%j%:%`$,M-8z$J>l9g$b$"$k(B. $B$3$l$K$D$$$F$O(B \cite{KNUTH}
$B$r;2>H(B. 

\noi
$BBh(B 5 $B>O(B:

$B$3$3$G=R$Y$i$l$F$$$k$3$H$N$&$A(B, $B8_=|K!$K4X$9$k$3$H$O(B Euclid $B4D$K$*$$$F(B
$B@.$jN)$D(B. $B$^$?(B, $B=*7k<0$K$D$$$F$O(B, $B$=$N=EMW@-$K$b$+$+$o$i$:(B, $B0lHLE*$J(B
$BBe?t3X$N9V5A$J$I$G>\$7$/07$o$l$k$3$H$O>/$J$$$H;W$o$l$k(B. \cite{TAKAGI2}
$B$J$I$GJY6/$7$F$_$F$[$7$$(B. 

\noi
$BBh(B 6 $B>O(B:

$B$3$3$G07$o$l$F$$$kFbMF$O(B, $B7W;;5!Be?t8&5f$K$*$1$k0l$D$N%O%$%i%$%H$H$b8@(B
$B$($k$b$N$G$"$k(B. $BFC$K(B, $BM-8BBN>e$NB?9`<00x?tJ,2r$O(B, $BBJ1_6J@~0E9f$J$I$X$N(B
$BD>@\$N1~MQ$b$"$j(B, $B8=:_$b3hH/$K8&5f$5$l$F$$$k(B. $B$^$?(B, $BM-M}?tBN>e$N0x?tJ,(B
$B2r$b(B, $B?t3X$K$*$1$k<B83%D!<%k$H$7$F7W;;5!Be?t%7%9%F%`$rMQ$$$k>l9g$KBgJQ(B
$BM-8z$J5!G=$G$"$k(B. $B$3$N>O$NFbMF$N$&$A(B, $BM-8BBN(B, $BM-M}?tBN>e$N0lJQ?tB?9`<0(B
$B$N0x?tJ,2r$K4X$7$F$O(B \cite{KNUTH}, $BB?JQ?tB?9`<0$N0x?tJ,2r$K4X$7$F$O(B
\cite{SASAKI} $B$"$k$$$O(B \cite{GEDDES} $B$r;2>H(B. $B$J$*(B, $B%"%k%4%j%:%`(B 
\ref{zassenhaus} $B$O(B $BJ,2r$5$l$kB?9`<0$N<!?t(B $n$ $B$K4X$7$F:G0-7W;;NL$,(B 
$O(2^n)$ $B$H$J$k$,(B, LLL $B%"%k%4%j%:%`(B $B$rMQ$$$kB?9`<0;~4V%"%k%4%j%:%`$,(B 
\cite{LENSTRA} $B$K$h$jDs0F$5$l$F$$$k(B. $B$?$@$7$3$N%"%k%4%j%:%`$O<BMQE*$H(B
$B$O$$$($:(B, $B0lHL$K$O%"%k%4%j%:%`(B \ref{zassenhaus}$B$,MQ$$$i$l$F$-$?(B. $B$4$/(B
$B:G6a(B, $B0[$J$k4QE@$+$i(B LLL $B%"%k%4%j%:%`$rMQ$$$kJ}K!$,(B \cite{HOEIJ} 
$B$K$h$jDs0F$5$l$?(B. $B$3$NJ}K!$O(B, $B$3$l$^$G$NJ}K!$G$O;v<B>eJ,2r$,IT2DG=$@$C(B
$B$?B?9`<0$r8zN($h$/J,2r$9$k$J$I(B, $B<BMQE*$K$bM%$l$F$$$k$3$H$,Js9p$5$l$F$$(B
$B$k(B.

\noi
$BBh(B 7 $B>O(B, $BBh(B 8 $B>O(B:

$B$3$3$G$O(B, $B%0%l%V%J4pDl(B, Buchberger $B%"%k%4%j%:%`$*$h$S$=$l$i$N1~MQ$K$D(B
$B$$$F$4$/4pK\E*$J$3$H$,$i$N$_$K8BDj$7$F=R$Y$F$$$k(B. $B>\$7$/$O(B,
\cite{COX} \cite{COX2} $B$r;2>H(B. $BFC$K(B \cite{COX2} $B$OBe?t4v2?(B, $B2D49Be?t(B
$B$N8&5f$N$?$a$N%D!<%k$H$J$k%"%k%4%j%:%`$K$D$$$F(B, $B%0%l%V%J4pDl$K8B$i$J$$(B
$B:G6a$N@.2L$b4^$a$FI}9-$/5-=R$5$l$F$$$k(B. 

\noi
$BBh(B 9 $B>O(B:

$B$3$3$G$O(B, $BM}O@>e$b1~MQ>e$b=EMW$J%$%G%"%k$N=`AGJ,2r$K$D$$$F35@b$7$F$$$k(B. 
$B%"%k%4%j%:%`$O$5$^$6$^$JItIJ$+$i@.$C$F$*$j(B, $B$=$l$i$N@bL@$K$D$$$F$O(B, 
\cite{BW} $B$r;2>H(B. $B$J$*(B, $B$3$3$G=R$Y$?$N$H$O0[$J$k=`AGJ,2r%"%k%4%j%:%`$,(B
\cite{SY} $B$GDs0F$5$l$F$*$j(B, Risa/Asir $B$K<BAu$5$l$F$$$k(B. 

\noi
$BBh(B 10 $B>O(B, $BBh(B 11 $B>O(B:

$B$3$l$i$N>O$O$d$dFC<l$JFbMF$r07$C$F$*$j(B, $B%0%l%V%J4pDl7W;;$r%D!<%k$H$7$F(B
$BMQ$$$k>l9g$K$OFC$K0U<1$9$kI,MW$O$J$$(B. $B$7$+$7(B, $B$=$l$rC1$J$kJXMx$J%V%i%C(B
$B%/%\%C%/%9$H9M$($k$H(B, $B$A$g$C$H$7$?LdBj$G$b$9$0$K7W;;$,GKC>$7$F$7$^$&$3(B
$B$H$OCN$C$F$*$/I,MW$,$"$k(B. $BG$0UF~NO$+$i$N%0%l%V%J4pDl7W;;$K$D$$$F$O(B, $B:G(B
$B6aDs0F$5$l$?(B $F_4$ $B%"%k%4%j%:%`(B \cite{F} $B$,M-NO$G$"$k$,(B, $B$^$@HFMQ7W;;(B
$B5!Be?t%7%9%F%`$J$I$K$O<BAu$5$l$F$$$J$$$h$&$G$"$k(B. $B$^$?(B, change of
ordering $B$K$D$$$F$O(B, $B$3$3$G=R$Y$?J}K!$NB>$K(B Gr\"obner walk $B$H8F$P$l$kJ}K!$,(B 
\cite{WALK} $B$GDs0F$5$l$F$$$k(B. modular change of ordering$B$*$h$S(B modular
RUR $B$O(B Risa/Asir $B$K<BAu$5$l$F$$$k(B.