Subquadratic-time factoring of polynomials over finite fields

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Subquadratic-time factoring of polynomials over finite fields

Full text

Pdf (1.02 MB)

Source

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

Las Vegas, Nevada, United States

Pages: 398 - 406

Year of Publication: 1995

ISBN:0-89791-718-9

Authors

Erich Kaltofen	Department of Computer Science, Rensselaer Polytechnic Institute, Troy, New York
Victor Shoup	Universität des Saarlandes, FB 14-Informatik, PF 15 11 50, D-66041 Saarbrücken, Germany

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

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

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/225058.225166 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	Baur, W. and Strassen, V., "The complexity of partial derivatives," Theoretical Comp. Sci. 22, pp. 317-330 (1983).
	3	Berlekamp, E. R., "Factoring polynomials (over large finite fields," Math. Comp. 24, pp. 713-735 (1970).
	4	Brent, R. P., Gustavson, F. G., and Yun, D. Y. Y., "Fast so-lution of Toeplitz systems of equations and computation of Pad6 approximants," J. Algorithms 1, pp. 259-295 (1980).
	5	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]
	6	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]
	7	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]
	8	Cantor, D. G. and Zassenhaus, H., "A new algorithm for factoring polynomials over finite fields,," Math. Comp. 36, pp. 587-592 (1981).
	9	Coppersmith, D., "Rapid multiplication of rectangular ma-trices," SIAM J. Comput. 11/3, pp. 4617-471 (1982).
	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	Jean Louis Dornstetter, On the equivalence between Berlekamp's and Euclid's algorithms, IEEE Transactions on Information Theory, v.33 n.3, p.428-431, May 1, 1987 [doi>10.1109/TIT.1987.1057299]
	12	Fleischmann, P., "Connections between tlhe algorithms of Berlekamp and Niederreiter for factoring polynomials over Fq ," Linear Algebra and Applicaticms 192, pp. 101- 108 (1993).
	13	J. von zur Gathen , M. Giesbrecht, Constructing normal bases in finite fields, Journal of Symbolic Computation, v.10 n.6, p.547-570, Dec. 1990 [doi>10.1016/S0747-7171(08)80158-7]
	14	von zur Gathen, J. and Shoup, V., "Computing Frobenius maps and factoring polynomials," Comput. Complexity 2, pp. 187-224 (1992).
	15	Mark William Giesbrecht, Nearly optimal algorithms for canonical matrix forms, University of Toronto, Toronto, Ont., Canada, 1993
	16	Griewank, A., "Achieving logarithmic growth of temporal and spatial complexity in reverse automatic differentia-tion," Optimization Methods & Software 1, pp. 35-54 (1992).
	17	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]
	18	Erich Kaltofen , Victor Pan, Processor efficient parallel solution of linear systems over an abstract field, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.180-191, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113396]
	19	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]
	20	Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
	21	Lidl, R. and Niederreiter, H., Finite Field% Addkon-Wesley, Reading, MA, 1983.
	22	Linnainmaa, S., "Taylor expansion of the accumulated rounding error," BIT 16, pp. 146-160 (1976).
	23	Lotti, G. and Romani, F., "On the asymptotic complexity of rectangular matrix multiplication," Theoretical CompIJt. Sci. 23, pp. 171-185 (1983).
	24	Massey, J. L., "Shift-register synthesis and BCH decoding," IEEE Trans. M. Theory lT-15, pp. 122-127 (1969).
	25	Niederreiter, H., "A new efficient factorization algorithm for polynomials over small finite fields," Applic. Algebra En-gin., Commun. Comput. 4, pp. 81-87 (1993).
	26	Harald Niederreiter , Rainer Göttfert, Factorization of polynomials over finite fields and characteristic sequences, Journal of Symbolic Computation, v.16 n.5, p.401-412, Nov. 1993 [doi>10.1006/jsco.1993.1055]
	27	Ostrowski, G. M., Wolin, Ju. M., and Borisow, W. W,, '@her die Berechnung von Ableitungen," Wissenschaftliche Zeitschrift Techn. Hochsch. Chem. Leuna-Merseburg 13/4, pp. 382-384 (1971). In German.
	28	Schwarz, St., "On the reducibility of polynomials over a finite field," Quart. J. Math. Oxford Ser. (2) 7, pp. 110-124 (1956).
	29	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]
	30	Victor Shoup, Fast construction of irreducible polynomials over finite fields, Journal of Symbolic Computation, v.17 n.5, p.371-391, May 1994 [doi>10.1006/jsco.1994.1025]
	31	Shoup, V., 'LA new polynomial factorization algorithm and its implementation," Manuscript, Univ. d. Saarlandes, Saarbrucken, Germany, August 1994b.
	32	D H Wiedemann, Solving sparse linear equations over finite fields, IEEE Transactions on Information Theory, v.32 n.1, p.54-62, Jan. 1986 [doi>10.1109/TIT.1986.1057137]

CITED BY 7

	Tetsuro Fujise , Hirokazu Murao, Parallel distinct degree factorization algorithm, Proceedings of the 1996 international symposium on Symbolic and algebraic computation, p.18-25, July 24-26, 1996, Zurich, Switzerland
	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
	Joachim von zur Gathen , Jürgen Gerhard, Arithmetic and factorization of polynomial over F2 (extended abstract), Proceedings of the 1996 international symposium on Symbolic and algebraic computation, p.1-9, July 24-26, 1996, Zurich, Switzerland
	Erich Kaltofen , Victor Shoup, Fast polynomial factorization over high algebraic extensions of finite fields, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.184-188, July 21-23, 1997, Kihei, Maui, Hawaii, United States
	Joachim von zur Gathen , Silke Hartlieb, Factoring modular polynomials (extended abstract), Proceedings of the 1996 international symposium on Symbolic and algebraic computation, p.10-17, July 24-26, 1996, Zurich, Switzerland
	Peter Fleischmann , Markus Chr. Holder , Peter Roelse, The black-box Niederreiter algorithm and its implementation over the binary field, Mathematics of Computation, v.72 n.244, p.1887-1899, October 2003
	Joan Feigenbaum , Yuval Ishai , Tal Malkin , Kobbi Nissim , Martin J. Strauss , Rebecca N. Wright, Secure multiparty computation of approximations, ACM Transactions on Algorithms (TALG), v.2 n.3, p.435-472, July 2006