Factoring multivariate polynomials over large finite fields
HTML articles powered by AMS MathViewer
 by Da Qing Wan PDF
 Math. Comp. 54 (1990), 755770 Request permission
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).References

M. BenOr, Probabilistic algorithms in finite fields, Proc. 22nd Sympos. Foundations Comp. Sci., IEEE, New York, 1981, pp. 394398.
 E. R. Berlekamp, Factoring polynomials over finite fields, Bell System Tech. J. 46 (1967), 1853–1859. MR 219231, DOI 10.1002/j.15387305.1967.tb03174.x
 E. R. Berlekamp, Factoring polynomials over large finite fields, Math. Comp. 24 (1970), 713–735. MR 276200, DOI 10.1090/S0025571819700276200X
 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 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 10.1090/S00255718198106065175
 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: Twentyfourth annual symposium on the foundations of computer science (Tucson, Ariz., 1983). MR 828523, DOI 10.1016/00220000(85)900431
 Joachim von zur Gathen, Irreducibility of multivariate polynomials, J. Comput. System Sci. 31 (1985), no. 2, 225–264. Special issue: Twentyfourth annual symposium on the foundations of computer science (Tucson, Ariz., 1983). MR 828523, DOI 10.1016/00220000(85)900431
 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 10.1090/S0025571819850790658X
 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., AddisonWesley Series in Computer Science and Information Processing, AddisonWesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. 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 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 10.1016/00220000(85)900169
 Rudolf Lidl and Harald Niederreiter, Finite fields, Encyclopedia of Mathematics and its Applications, vol. 20, AddisonWesley 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 10.4153/CMB19870033
 Michael O. Rabin, Probabilistic algorithms in finite fields, SIAM J. Comput. 9 (1980), no. 2, 273–280. MR 568814, DOI 10.1137/0209024
 JeanPierre Serre, Majorations de sommes exponentielles, Journées Arithmétiques de Caen (Univ. Caen, Caen, 1976) Astérisque No. 41–42, Soc. Math. France, Paris, 1977, pp. 111–126 (French). MR 0447142
 Hans Zassenhaus, On Hensel factorization. I, J. Number Theory 1 (1969), 291–311. MR 242793, DOI 10.1016/0022314X(69)90047X
Additional Information
 © Copyright 1990 American Mathematical Society
 Journal: Math. Comp. 54 (1990), 755770
 MSC: Primary 11T06; Secondary 1204, 68Q40
 DOI: https://doi.org/10.1090/S00255718199010114480
 MathSciNet review: 1011448