Factoring multivariate polynomials over large finite fields
HTML articles powered by AMS MathViewer
- by Da Qing Wan PDF
- Math. Comp. 54 (1990), 755-770 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. 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 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 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 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/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 10.1016/0022-0000(85)90043-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 10.1016/0022-0000(85)90043-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 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 Series in Computer Science and Information Processing, Addison-Wesley 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/0022-0000(85)90016-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 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 10.1137/0209024
- Jean-Pierre 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/0022-314X(69)90047-X
Additional Information
- © Copyright 1990 American Mathematical Society
- 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