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 $f(x,y)$ over ${F_q}$ of total degree n, our algorithm takes at most \[ {n^{4.89}}{\log ^2}n\log q\] operations in ${F_q}$ to factor $f(x,y)$ completely. This improves a probabilistic factorization algorithm of von zur Gathen and Kaltofen, which takes \[ O({n^{11}}\log n\log q)\] operations to factor $f(x,y)$ completely over ${F_q}$. The algorithm can be easily generalized to factor multivariate polynomials over finite fields. We shall give two further applications of the idea involved in the algorithm. One is concerned with exponential sums; the other is related to permutational polynomials over finite fields (a conjecture of Chowla and Zassenhaus).
-
M. Ben-Or, Probabilistic algorithms in finite fields, Proc. 22nd Sympos. Foundations Comp. Sci., IEEE, New York, 1981, pp. 394-398.
- E. R. Berlekamp, Factoring polynomials over finite fields, Bell System Tech. J. 46 (1967), 1853–1859. MR 219231, DOI https://doi.org/10.1002/j.1538-7305.1967.tb03174.x
- E. R. Berlekamp, Factoring polynomials over large finite fields, Math. Comp. 24 (1970), 713–735. MR 276200, DOI https://doi.org/10.1090/S0025-5718-1970-0276200-X
- 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, DOI https://doi.org/10.1109/TIT.1983.1056666
- 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, DOI https://doi.org/10.1090/S0025-5718-1981-0606517-5
- S. Chowla and H. Zassenhaus, Some conjectures concerning finite fields, Norske Vid. Selsk. Forh. (Trondheim) 41 (1968), 34–35. MR 233805
- 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, DOI https://doi.org/10.1016/0022-0000%2885%2990043-1
- 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, DOI https://doi.org/10.1016/0022-0000%2885%2990043-1
- J. von zur Gathen and E. Kaltofen, Factorization of multivariate polynomials over finite fields, Math. Comp. 45 (1985), no. 171, 251–261. MR 790658, DOI https://doi.org/10.1090/S0025-5718-1985-0790658-X
- 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
- 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
- Susan Landau, Factoring polynomials quickly, Notices Amer. Math. Soc. 34 (1987), no. 1, 3–8. MR 869153
- 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, DOI https://doi.org/10.1007/BF01457454
- A. K. Lenstra, Factoring multivariate polynomials over finite fields, J. Comput. System Sci. 30 (1985), no. 2, 235–248. MR 801825, DOI https://doi.org/10.1016/0022-0000%2885%2990016-9
- 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
- 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, DOI https://doi.org/10.4153/CMB-1987-003-3
- Michael O. Rabin, Probabilistic algorithms in finite fields, SIAM J. Comput. 9 (1980), no. 2, 273–280. MR 568814, DOI https://doi.org/10.1137/0209024
- 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
- Hans Zassenhaus, On Hensel factorization. I, J. Number Theory 1 (1969), 291–311. MR 242793, DOI https://doi.org/10.1016/0022-314X%2869%2990047-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
Article copyright:
© Copyright 1990
American Mathematical Society