Factoring high-degree polynomials by the black box Berlekamp algorithm

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	Eric Bach , James Driscoll , Jeffrey Shallit, Factor refinement, Journal of Algorithms, v.15 n.2, p.199-222, Sept. 1993 [doi>10.1006/jagm.1993.1038]
	2	Ben-Or, M., "Probabilistic algorithms in finite fields," Proc. 22nd IEEE Syrup. Foundations Comp. Sci., pp. 394-398 (1981).
	3	Berlekamp, E. R., "Factoring polynomials over finite fields," Bell Systems Tech. J. 46, pp. 1853-1859 (1967). Republished in revised form in: E. R. Berlekamp, Algebraic Coding Theory, Chapter 6, McGraw- Hill Publ., New York 1968.
	4	Berlekamp, E. R., "Factoring polynomials over large finite fields," Math. Comp. 24, pp. 713-735 (1970).
	5	Brent, R. P., Gustavson, F. G., and Yun, D. Y. Y., "Fast solution of Toeplitz systems of equations and computation of Pad~ approximants," J. Algorithms 1, pp. 259-295 (1980).
	6	Butler, M. C. R., "On the reducibility of polynomials over a finite field," Quart. J. Math., Oxford Ser. (2) 5, pp. 102-107 (1954).
	7	Camion, P., "Un algorithme de construction des idempotents primitifs d'ideaux d'algebres sur Fq," Ann. Discrete Math 12, pp. 55-63 (1982).
	8	Cantor~ D. G. and Zassenhaus, H., "A new algorithm for factoring polynomials over finite fields," Math. Comp. 36, pp. 587-592 (1981).
	9	Don Coppersmith, Solving homogeneous linear equations over GF(2) via block Wiedemann algorithm, Mathematics of Computation, v.62 n.205, p.333-350, Jan. 1994 [doi>10.2307/2153413]
	10	Angel Díaz , Markus A. Hitz , Erich Kaltofen , A. Lobo , T. Valente, Process Scheduling in DSC and the Large Sparse Linear Systems Challenge, Proceedings of the International Symposium on Design and Implementation of Symbolic Computation Systems, p.66-80, September 15-17, 1993
	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 the algorithms of Berlekamp and Niederreiter for factoring polynomials over {:q," Linear Algebra and Applications 192, pp. 01-108 (1993).
	13	Gao, S. and von zur Gathen, J., "Berlekamp's and Niederreiter's polynomial factorization algorithm," in Finite Fields: Theory, Applications and Algorithms, Contemporary Mathematics, edited by L. Mullen and P. J.-S. Shiue; Amer. Math. Soc., Providence, Rhode Island, to appear, 1994.
	14	Joachim von zur Gathen, A polynomial factorization challenge, ACM SIGSAM Bulletin, v.26 n.2, p.22-24, April 1992 [doi>10.1145/130933.130939]
	15	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]
	16	yon zur Gathen, J. and Shoup, V., "Computing Probenius maps and factoring polynomials," Comput. Complexity 2, pp. 187-224 (1992).
	17	Erich Kaltofen, Sparse Hensel Lifting, Research Contributions from the European Conference on Computer Algebra-Volume 2, p.4-17, April 01-03, 1985
	18	Erich Kaltofen, Analysis of Coppersmith's Block Wiedemann Algorithm for the Parallel Solution of Sparse Linear Systems, Proceedings of the 10th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.195-212, May 10-14, 1993
	19	Erich Kaltofen, Analysis of Coppersmith's block Wiedemann algorithm for the parallel solution of sparse linear systems, Mathematics of Computation, v.64 n.210, p.777-806, April 1995 [doi>10.2307/2153451]
	20	Kaltofen, E., Musser, D. R., and Saunders, B. D., "A generalized class of polynomials that are hard to factor," SIAM J. Comp. 12/3, pp. 473-485 (1983).
	21	Erich Kaltofen , B. David Saunders, On Wiedemann's Method of Solving Sparse Linear Systems, Proceedings of the 9th International Symposium, on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.29-38, October 07-11, 1991
	22	Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
	23	Massey, J. L., "Shift-register synthesis and BCH decoding," IEEE Trans. Inf. Theory IT-15, pp. 122-127 (1969).
	24	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]
	25	David A. Patterson , John L. Hennessy, Computer architecture: a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
	26	Rabin, M. O., "Probabilistic algorithms in finite fields," SIAM J. Comp. 9, pp. 273-280 (1980).
	27	Schwarz, St., "On the reducibility of polynomials over a finite field," Quart. J. Math. Oxford Ser. (2) 7, pp. 110-124 (1956).
	28	Shoup, V., "Factoring polynomials over finite fields" asymptotic complexity vs. reality," in Proc. Int. IMACS Syrup. on Symbolic Comput., New Trends and Developments; Lille, France, pp. 124-129, 1993.
	29	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]

Peer to Peer - Readers of this Article have also read:

Data structures for quadtree approximation and compression Communications of the ACM 28, 9
Hanan Samet
A hierarchical single-key-lock access control using the Chinese remainder theorem Proceedings of the 1992 ACM/SIGAPP Symposium on Applied computing
Kim S. Lee , Huizhu Lu , D. D. Fisher
The GemStone object database management system Communications of the ACM 34, 10
Paul Butterworth , Allen Otis , Jacob Stein
Putting innovation to work: adoption strategies for multimedia communication systems Communications of the ACM 34, 12
Ellen Francik , Susan Ehrlich Rudman , Donna Cooper , Stephen Levine
An intelligent component database for behavioral synthesis Proceedings of the 27th ACM/IEEE Design Automation Conference on
Gwo-Dong Chen , Daniel D. Gajski