Factoring multivariate polynomials over large finite fields
Author:
Da Qing Wan
Journal:
Math. Comp. 54 (1990), 755-770
MSC:
Primary 11T06; Secondary 12-04, 68Q40
DOI:
https://doi.org/10.1090/S0025-5718-1990-1011448-0
MathSciNet review:
1011448
Full-text PDF Free Access
Abstract | References | Similar Articles | Additional Information
Abstract: A simple probabilistic algorithm is presented to find the irreducible factors of a bivariate polynomial over a large finite field. For a polynomial over
of total degree n, our algorithm takes at most






- [1] M. Ben-Or, Probabilistic algorithms in finite fields, Proc. 22nd Sympos. Foundations Comp. Sci., IEEE, New York, 1981, pp. 394-398.
- [2] E. R. Berlekamp, Factoring polynomials over finite fields, Bell System Tech. J. 46 (1967), 1853–1859. MR 219231, https://doi.org/10.1002/j.1538-7305.1967.tb03174.x
- [3] E. R. Berlekamp, Factoring polynomials over large finite fields, Math. Comp. 24 (1970), 713–735. MR 276200, https://doi.org/10.1090/S0025-5718-1970-0276200-X
- [4] Paul F. Camion, Improving an algorithm for factoring polynomials over a finite field and constructing large irreducible polynomials, IEEE Trans. Inform. Theory 29 (1983), no. 3, 378–385. MR 712404, https://doi.org/10.1109/TIT.1983.1056666
- [5] David G. Cantor and Hans Zassenhaus, A new algorithm for factoring polynomials over finite fields, Math. Comp. 36 (1981), no. 154, 587–592. MR 606517, https://doi.org/10.1090/S0025-5718-1981-0606517-5
- [6] S. Chowla and H. Zassenhaus, Some conjectures concerning finite fields, Norske Vid. Selsk. Forh. (Trondheim) 41 (1968), 34–35. MR 233805
- [7] Joachim von zur Gathen, Irreducibility of multivariate polynomials, J. Comput. System Sci. 31 (1985), no. 2, 225–264. Special issue: Twenty-fourth annual symposium on the foundations of computer science (Tucson, Ariz., 1983). MR 828523, https://doi.org/10.1016/0022-0000(85)90043-1
- [8] Joachim von zur Gathen, Irreducibility of multivariate polynomials, J. Comput. System Sci. 31 (1985), no. 2, 225–264. Special issue: Twenty-fourth annual symposium on the foundations of computer science (Tucson, Ariz., 1983). MR 828523, https://doi.org/10.1016/0022-0000(85)90043-1
- [9] J. von zur Gathen and E. Kaltofen, Factorization of multivariate polynomials over finite fields, Math. Comp. 45 (1985), no. 171, 251–261. MR 790658, https://doi.org/10.1090/S0025-5718-1985-0790658-X
- [10] Nicholas M. Katz, Sommes exponentielles, Astérisque, vol. 79, Société Mathématique de France, Paris, 1980 (French). Course taught at the University of Paris, Orsay, Fall 1979; With a preface by Luc Illusie; Notes written by Gérard Laumon; With an English summary. MR 617009
- [11] Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms; Addison-Wesley Series in Computer Science and Information Processing. MR 633878
- [12] Susan Landau, Factoring polynomials quickly, Notices Amer. Math. Soc. 34 (1987), no. 1, 3–8. MR 869153
- [13] A. K. Lenstra, H. W. Lenstra Jr., and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), no. 4, 515–534. MR 682664, https://doi.org/10.1007/BF01457454
- [14] A. K. Lenstra, Factoring multivariate polynomials over finite fields, J. Comput. System Sci. 30 (1985), no. 2, 235–248. MR 801825, https://doi.org/10.1016/0022-0000(85)90016-9
- [15] Rudolf Lidl and Harald Niederreiter, Finite fields, Encyclopedia of Mathematics and its Applications, vol. 20, Addison-Wesley Publishing Company, Advanced Book Program, Reading, MA, 1983. With a foreword by P. M. Cohn. MR 746963
- [16] Gary L. Mullen and Harald Niederreiter, Dickson polynomials over finite fields and complete mappings, Canad. Math. Bull. 30 (1987), no. 1, 19–27. MR 879866, https://doi.org/10.4153/CMB-1987-003-3
- [17] Michael O. Rabin, Probabilistic algorithms in finite fields, SIAM J. Comput. 9 (1980), no. 2, 273–280. MR 568814, https://doi.org/10.1137/0209024
- [18] Jean-Pierre Serre, Majorations de sommes exponentielles, Journées Arithmétiques de Caen (Univ. Caen, Caen, 1976) Soc. Math. France, Paris, 1977, pp. 111–126. Astérisque No. 41–42 (French). MR 0447142
- [19] Hans Zassenhaus, On Hensel factorization. I, J. Number Theory 1 (1969), 291–311. MR 242793, https://doi.org/10.1016/0022-314X(69)90047-X
Retrieve articles in Mathematics of Computation with MSC: 11T06, 12-04, 68Q40
Retrieve articles in all journals with MSC: 11T06, 12-04, 68Q40
Additional Information
DOI:
https://doi.org/10.1090/S0025-5718-1990-1011448-0
Article copyright:
© Copyright 1990
American Mathematical Society