Factoring modular polynomials (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Factoring modular polynomials (extended abstract)

Full text

Pdf (792 KB)

Source

International Conference on Symbolic and Algebraic Computation archive
Proceedings of the 1996 international symposium on Symbolic and algebraic computation table of contents

Zurich, Switzerland

Pages: 10 - 17

Year of Publication: 1996

ISBN:0-89791-796-0

Authors

Joachim von zur Gathen	Fachbereich 17 Mathematik-Informatik, Universität-GH Paderborn, D-33095 Paderborn, Germany
Silke Hartlieb	Fachbereich 17 Mathematik-Informatik, Universität-GH Paderborn, D-33095 Paderborn, Germany

Sponsors

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation
SIGNUM: ACM Special Interest Group on Numerical Mathematics

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 18, Citation Count: 1

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/236869.236884 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	E. BACH, Number-theoretic algorithms. Annual Rev. Comput. Sci. 4 (1990), 119-172.
	3	E. R. BERLEKAMP, Factoring polynomials over large finite fields. Math. Comp. 24 (1970), 713-735.
	4	Dario Bini , Victor Y. Pan, Polynomial and matrix computations (vol. 1): fundamental algorithms, Birkhauser Verlag, Basel, Switzerland, 1994
	5	Z. I. BOREVICH AND I.R. SHAFAREVICH, NLrmber Theory. Academic Press, Inc., 1966.
	6	A. L. CHISTOV, Efficient factorization of polynomials over local fields. Soviet Math. Dokl. 35(2) (1987), 430-433.
	7	A. L. CHISTOV, Algorithm of polynomial complexity for factoring polynomials over local fields. J. Math. Sciences 7'0(4) (1994), 1912-1933.
	8	P.M. COHN, Algebra, vol. 2. John Wiley & Sons, 1977.
	9	George E. Collins, The Calculation of Multivariate Polynomial Resultants, Journal of the ACM (JACM), v.18 n.4, p.515-532, Oct. 1971 [doi>10.1145/321662.321666]
	10	Don Coppersmith , Shmuel Winograd, Matrix multiplication via arithmetic progressions, Journal of Symbolic Computation, v.9 n.3, p.251-280, March 1990 [doi>10.1016/S0747-7171(08)80013-2]
	11	J. VON ZUR GATHEN AND S. HARTLIEB, Factorization of polynomials modulo small prime powers. Technical report, Universit~t-GH Paderborn, 1996. To appear.
	12	J. VON ZUR GATHEN AND V. SHOUP, Computing Frobenius maps and factoring polynomials, computational complexity 2 (1992), 187-224.
	13	Costas S. Iliopoulos, Worst-case complexity bounds on algorithms for computing the canonical structure of finite Abelian groups and the Hermite and Smith normal forms of an integer matrix, SIAM Journal on Computing, v.18 n.4, p.658-669, Aug. 1989 [doi>10.1137/0218045]
	14	Erich Kaltofen , Victor Shoup, Subquadratic-time factoring of polynomials over finite fields, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.398-406, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225166]
	15	E. KALTOFEN, M. S. KRISHNAMOORTHY, AND B. D. SAUNDERS~ Parallel algorithms for matrix normal forms. Linear Algebra and Appl. 136 (1990), 189-208.
	16	A. K. Lenstra , H. W. Lenstra, Jr., Algorithms in number theory, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	17	A. g. LENSTRA AND H. W. LENSTRA, ed., The development of the number field sieve, Lecture notes in mathematics 1554. Springer- Verlag Berlin Heidelberg, 1993.
	18	A. SCH()NHAGE AND V. STRASSEN, Schnelle Multiplikation groi}er Zahlen. Computing 7' (1971), 281-292.
	19	Adi Shamir, On the generation of multivariate polynomials which are hard to factor, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.796-804, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167291]
	20	M. O. VAHLE, Solving the congruence x2 -- a mod n. MapleTech 9 (I993), ~9-~6.