Computing Frobenius maps and factoring polynomials

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Computing Frobenius maps and factoring polynomials

Full text

Pdf (688 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-fourth annual ACM symposium on Theory of computing table of contents

Victoria, British Columbia, Canada

Pages: 97 - 105

Year of Publication: 1992

ISBN:0-89791-511-9

Authors

Joachim von zur Gathen	Department of Computer Science, University of Toronto, Toronto, Ontario M5S 1A4, Canada
Victor Shoup	Department of Computer Science, University of Toronto, Toronto, Ontario M5S 1A4, Canada

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 25, Citation Count: 3

Additional Information:

abstract 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/129712.129722 What is a DOI?

ABSTRACT

A new probabilistic algorithm for factoring univariate polynomials over finite fields is presented whose asymptotic running time improves upon previous results. To factor a polynomial of degree n over Fq, the algorithm uses O((n2 + n log q)•(log n)2 log log n) arithmetic operations in Fq. The main technical innovation is a new way to compute Frobenius and trace maps in the ring of polynomials modulo the polynomial to be factored.

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	A. ARWIN, Uber Kongruenzen von dem fiinften und hSheren Graden nach einem Primzahlmodulus. Arkiv f#r matematik, astronomi o. fysik 14 (1918), 1-46.
	2	L. PAPAl) E. M. LUKS, AND #. SERESS, Fast management of permutation groups. In #gth Annual Symposium on Foundations of Computer Science, 272-282, 1988.
	3	M. B#N-OR, Probabilistic algorithms in finite fields. In #$nd Annual Symposium on Foundations of Computer Science, 394-398, 1981.
	4	E. R. BERLEKAMP, Algebraic Coding Theory. McGraw-Hill, 1968.
	5	E. R. BERLEKAMP, Factoring polynomials over large finite fields. Math. Comp. 24(111) (1970), 713-735.
	6	R. P. Brent , H. T. Kung, Fast Algorithms for Manipulating Formal Power Series, Journal of the ACM (JACM), v.25 n.4, p.581-595, Oct. 1978 [doi>10.1145/322092.322099]
	7	J. BUCHMANN, Complexity of algorithms in algebraic number theory. In Number Theory. Proc. First Conf. Canadian Number Theory Assoc. Walter de Gruyter, 1990.
	8	P. CAMION, Improving an algorithm for factoring polynomials over a finite field and constructing large irreducible polynomials. IEEE Trans. In. form. Theory IT-29(3) (1983), 378- 385.
	9	David G. Cantor , Erich Kaltofen, On fast multiplication of polynomials over arbitrary algebras, Acta Informatica, v.28 n.7, p.693-701, Oct. 1991 [doi>10.1007/BF01178683]
	10	D. G. CANTOR AND H. ZASSENHAUS, A new algorithm for factoring polynomials over finite fields. Math. Comp. 36(154) (1981), 587-592.
	11	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]
	12	Joachim von zur Gathen, Irreducibility of multivariate polynomials, Journal of Computer and System Sciences, v.31 n.2, p.225-264, Sept. 1985 [doi>10.1016/0022-0000(85)90043-1]
	13	J. Von Zur Gathen, Factoring polynomials and primitive elements for special primes, Theoretical Computer Science, v.52 n.1-2, p.77-89, May 1987 [doi>10.1016/0304-3975(87)90081-8]
	14	Joachim von zur Gathen , Gadiel Seroussi, Boolean circuits versus arithmetic circuits, Information and Computation, v.91 n.1, p.142-154, March 1991 [doi>10.1016/0890-5401(91)90078-G]
	15	E. KALTOFEN, Polynomial factorization 1982- 1986. In Computers in Mathematics, ed. D. V. Chudnovsky, R. D. Jenks, Lecture Notes in Pure and Applied Mathematics, col. 125, 285-309, 1990.
	16	D. E. KNUTtt, The Art of Computer Programming, col. 2. Addison-Wesley, second edition, 1981.
	17	R. J. MCELIECE, Factorization of polynomials over finite fields. Math. Comp. 23 (1969), 861-867.
	18	M. MIGNoTTE AND C. SCHNORR, Calcul ddterministique des racines d'un polynCme dans un corps fini. C. R. Acad. Sci. Paris 306 (1988), 467- 472.
	19	R. T. MOENCK, On the efficiency of algorithms for polynomial factoring. Math. Comp. 31(137) (1977), 235-250.
	20	A M Odlyzko, Discrete logarithms in finite fields and their cryptographic significance, Proc. of the EUROCRYPT 84 workshop on Advances in cryptology: theory and application of cryptographic techniques, p.224-314, December 1985, Paris, France
	21	A. SCH6NHA6E, Schnelle Multiplikation von Polynomen fiber KSrpern der Charakteristik 2. Acta Inform. 7 (1977), 395-398.
	22	A. SCHSNHA6E AND V. STRASSEN, Schnelle Multiplikation grosser Zahlen. Computing 7 (1971), 281-282.
	23	V. SHOUP AND R. SMOLENSKY, An algorithm for modular composition. Preprint, 1991.
	24	David Y.Y. Yun, On square-free decomposition algorithms, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.26-35, August 10-12, 1976, Yorktown Heights, New York, United States [doi>10.1145/800205.806320]

CITED BY 3

	Rajiv Gupta , Scott A. Smolka , Shaji Bhaskar, On randomization in sequential and distributed algorithms, ACM Computing Surveys (CSUR), v.26 n.1, p.7-86, March 1994
	Victor Shoup, Fast construction of irreducible polynomials over finite fields, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.484-492, January 25-27, 1993, Austin, Texas, United States
	Joachim von zur Gathen, A polynomial factorization challenge, ACM SIGSAM Bulletin, v.26 n.2, p.22-24, April 1992