Arithmetic and factorization of polynomial over F2 (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Arithmetic and factorization of polynomial over F2 (extended abstract)

Full text

Pdf (951 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: 1 - 9

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
Jürgen Gerhard	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): 13, 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/236869.236882 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	M. BEN-OR, Probabilistic algorithms in finite fields. In Proc. 22nd IEEE Syrup. Foundations Computer Science, 1981, 394-398.
	3	E. R. BERLEKAMP, Factoring polynomials over finite fields. BelI System Tech. j. 46 (1967), 1853-1859.
	4	E. R. BERLEKAMP, Factoring polynomials over large finite fields. Math. Comp. 24 (1970), 713-735.
	5	David G. Gantor, On arithmetical algorithms over finite fields, Journal of Combinatorial Theory Series A, v.50 n.2, p.285-300, March 1989 [doi>10.1016/0097-3165(89)90020-4]
	6	D. G. CANTOR AND H. ZASSENHAUS, A new algorithm for factoring polynomials over finite fields. Math. Comp. 36 (1981), 587-592.
	7	Philippe Flajolet , Xavier Gourdon , Daniel Panario, Random Polynomials and Polynomial Factorization, Proceedings of the 23rd International Colloquium on Automata, Languages and Programming, p.232-243, July 08-12, 1996
	8	P. FLEISCHMANN AND P ROELSE, Comparative implementations of Berlekamp's and Niederreiter's polynomial factorization algorithms. Preprint, 1995.
	9	S. GAO AND J. VON ZUR GATHEN, Berlekamp's and Niederreiter's polynomial factorization algorithms. In Finite FieIds: Theory, Applications and Algorithms, ed. (3. L. MULLEN AND P. J-S. SmUE, vo1. 168 of Contemporary Mathematics. Amer. Math. Soc., 1994, 101-115.
	10	J. VON ZUR CATHEN AND J. GERHARD, Arithmetic and factorization of polynomials over F2. Technical report, University of Paderborn, to appear, 1996.
	11	J. VON ZUR GATHEN AND V. SHOUP, Computing Frobenius maps and factoring polyaornials. Comput compIexity 2 (1992), 187- 224,
	12	J. VON ZUR GATHEN, X. GOURDON, AND D. PANARIO, Averagecase analysis of some polynomial factorization algorithms. Unpublished, 1995.
	13	Keith O. Geddes , Stephen R. Czapor , George Labahn, Algorithms for computer algebra, Kluwer Academic Publishers, Norwell, MA, 1992
	14	Erich Kaltofen, Polynomial Factorization 1987-1991, Proceedings of the 1st Latin American Symposium on Theoretical Informatics, p.294-313, April 06-10, 1992
	15	Erich Kaltofen , Austin Lobo, Factoring high-degree polynomials by the black box Berlekamp algorithm, Proceedings of the international symposium on Symbolic and algebraic computation, p.90-98, July 20-22, 1994, Oxford, United Kingdom [doi>10.1145/190347.190371]
	16	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]
	17	A. KARATSUBA AND Y. OFMAN, ~rMHO:kI~eHI~Ie MHOFO3ttaH- HLIX tII~ICeJI Ha aBTOMaTax. Dokl. Akad. Nauk USSR 145 (1962), 293-294. Multiplication of multidigit numbers on automata, Soviet Physics-Doklady 7 (1963), 595-596.
	18	D. ~. KNUTH AND L. TRABB PARDO, Analysis of a simple factorization algorithm. Theoretical Computer Science 3 (1976), 321-348.
	19	P L. MONTGOMERY, Factorization of X~16~91 + X + I mod 2 a problem of Herb Doughty. Preprint, 1991.
	20	H. NIEDERREITER, New deterministic factorization algorithms for polynomials over finite fields. Contemporary Mathematics 168 (1994), 251-268.
	21	D. REISCHERT, Schnelle Multiplikation von Polynomen fiber GF(2) und Anwendungen. Diplomarbeit, University of Bonn, Germany, 1995.
	22	A. SCFISNFIA(t~, gchnelle Multiplikation yon Polynomen fiber KSrpern der Charakteristik 2. Acta InL 7 (1977), 395-398.
	23	Victor Shoup, A new polynomial factorization algorithm and its implementation, Journal of Symbolic Computation, v.20 n.4, p.363-397, October 1995 [doi>10.1006/jsco.1995.1055]
	24	V. STRASSEN, The computational complexity of continued fractions. SIAM d. Comput. 12 (1983), 1-27.
	25	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 4

	Hirokazu Murao , Tetsuro Fujise, Towards an efficient implementation of a fast algorithm for multipoint polynomial evaluation and its parallel processing, Proceedings of the second international symposium on Parallel symbolic computation, p.24-30, July 20-22, 1997, Maui, Hawaii, United States
	Olaf Bonorden , Joachim von zur Gathen , Jürgen Gerhard , Olaf Müller, Factoring a binary polynomial of degree over one million, ACM SIGSAM Bulletin, v.35 n.1, p.16-18, March 2001
	Fatima K. Abu Salem, A new sparse Gaussian elimination algorithm and the Niederreiter linear system for trinomials over F2, Computing, v.77 n.2, p.179-203, April 2006
	Luca De Feo , Éric Schost, Fast arithmetics in artin-schreier towers over finite fields, Proceedings of the 2009 international symposium on Symbolic and algebraic computation, July 28-31, 2009, Seoul, Republic of Korea