A fast deterministic algorithm for factoring polynomials over finite fields of small characteristic

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

A fast deterministic algorithm for factoring polynomials over finite fields of small characteristic

Full text

Pdf (611 KB)

Source

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

Bonn, West Germany

Pages: 14 - 21

Year of Publication: 1991

ISBN:0-89791-437-6

Author

Victor Shoup

Computer Sciences Department, University of Toronto, Toronto, Ontario M5S 1A4

Sponsors

GMD : German Natl Research Ctr for Information Tech. - Gesellschft
German Comp Soc : GI - Gesellshaft for Informatik
SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 24, Citation Count: 4

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/120694.120697 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	W. Baur and V. Strassen. The complexity of computing partial derivatives. Theoretical Computer Science, 22:317-330, 1983.
	2	M. Ben-Or. Probabilistic Mgorithms in finite fields. In 22nd Annual Symposium on Foundations of Computer Science, pages 394-398, 1981.
	3	E. R. Berlekamp. Factoring polynomi- Ms over large finite fields. Math. Comp., 24( 111):713-735, 1970.
	4	A. Borodin and I. Munro. The Computational Complexity of Algebraic and Numeric Problems. American Elsevier, 1975.
	5	D. A. Burgess. A note on the distribution of residues and non-residues. Jour. London Math. Soc., 38:253-256, 1963.
	6	P. Camion. Improving an algorithm for factoring polynomials over a finite field and constructing large irreducible polynomials. IEEE Trans. Inform. Theory, IT-29(3):378- 385, 1983.
	7	J. F. Canny , E. Kaltofen , L. Yagati, Solving systems of nonlinear polynomial equations faster, Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation, p.121-128, July 17-19, 1989, Portland, Oregon, United States [doi>10.1145/74540.74556]
	8	D. G. Cantor and E. Kaltofen. Fast multiplication of polynomials over arbitrary rings. Technical Report 87-35, Department of Computer Science, Rensselaer Polytechnic Institute, 1987. To appear, Acta. inf.
	9	D. G. Cantor and H. Zassenhaus. A new algorithm for factoring polynomials over finite fields. Math. Comp., 36(154):587-592, 1981.
	10	D. Coppersmith , S. Winograd, Matrix multiplication via arithmetic progressions, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.1-6, January 1987, New York, New York, United States [doi>10.1145/28395.28396]
	11	Michael Kaminski , David G. Kirkpatrick , Nader H. Bshouty, Addition requirements for matrix and transposed matrix products, Journal of Algorithms, v.9 n.3, p.354-364, September 1988 [doi>10.1016/0196-6774(88)90026-0]
	12	R. T. Moenck. On the efficiency of algorithms for polynomial factoring. Math. Comp., 31(137):235-250, 1977.
	13	V. Shoup, On the deterministic complexity of factoring polynomials over finite fields, Information Processing Letters, v.33 n.5, p.261-267, January 1990 [doi>10.1016/0020-0190(90)90195-4]
	14	I. E. Shparlinsky. On some questions in the theory of finite fields. Preprint, 1990.
	15	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]

CITED BY 4

	Victor Shoup, Efficient computation of minimal polynomials in algebraic extensions of finite fields, Proceedings of the 1999 international symposium on Symbolic and algebraic computation, p.53-58, July 28-31, 1999, Vancouver, British Columbia, Canada
	A. Bostan , G. Lecerf , É. Schost, Tellegen's principle into practice, Proceedings of the 2003 international symposium on Symbolic and algebraic computation, p.37-44, August 03-06, 2003, Philadelphia, PA, USA
	Cyril Pascal , Éric Schost, Change of order for bivariate triangular sets, Proceedings of the 2006 international symposium on Symbolic and algebraic computation, July 09-12, 2006, Genoa, Italy
	Raphaël Clifford , Klim Efremenko , Ely Porat , Amir Rothschild, From coding theory to efficient pattern matching, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.778-784, January 04-06, 2009, New York, New York