Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Factoring multivariate polynomials via partial differential equations

Author: Shuhong Gao
Journal: Math. Comp. 72 (2003), 801-822
MSC (2000): Primary 12Y05, 68W30; Secondary 11Y16, 12D05, 13P05
Published electronically: February 28, 2002
MathSciNet review: 1954969
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A new method is presented for factorization of bivariate polynomials over any field of characteristic zero or of relatively large characteristic. It is based on a simple partial differential equation that gives a system of linear equations. As in Berlekamp's and Niederreiter's algorithms for factoring univariate polynomials, the dimension of the solution space of the linear system is equal to the number of absolutely irreducible factors of the polynomial to be factored, and any basis for the solution space gives a complete factorization by computing gcd's and by factoring univariate polynomials over the ground field. The new method finds absolute and rational factorizations simultaneously and is easy to implement for finite fields, local fields, number fields, and the complex number field. The theory of the new method allows an effective Hilbert irreducibility theorem, thus an efficient reduction of polynomials from multivariate to bivariate.

References [Enhancements On Off] (What's this?)

  • 1. C. BAJAJ, J. CANNY, T. GARRITY AND J. WARREN, ``Factoring rational polynomials over the complex numbers'', SIAM J. Comput. 22 (1993), 318-331. MR 94a:12001
  • 2. E. R. BERLEKAMP, ``Factoring polynomials over finite fields", Bell System Tech. J., 46 (1967), 1853-1859. MR 36:2314
  • 3. E. R. BERLEKAMP, ``Factoring polynomials over large finite fields", Math. Comp., 24 (1970), 713-735. MR 43:1948
  • 4. L. BLUM, F. CUCKER, M. SHUB AND S. SMALE, Complexity and Real Computation, Springer-Verlag, New York, Berlin, 1998. MR 99a:68070
  • 5. W. S. BROWN, On Euclid's algorithm and the computation of polynomial greatest common divisors, J. ACM 18 (1971), 478-504. MR 46:6570
  • 6. D. G. CANTOR AND E. KALTOFEN, ``On fast multiplication of polynomials over arbitrary algebras'', Acta. Inform. 28 (1991), 693-701. MR 92i:68068
  • 7. D. G. CANTOR AND H. ZASSENHAUS ``A new algorithm for factoring polynomials over finite fields'', Math. Comp. 36 (1981), no. 154, 587-592. MR 82e:12020
  • 8. A. L. CHISTOV, ``An algorithm of polynomial complexity for factoring polynomials, and determination of the components of a variety in a subexponential time'' (Russian), Theory of the complexity of computations, II., Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI) 137 (1984), 124-188. [English translation: J. Sov. Math. 34 (1986).] MR 86g:11077
  • 9. A. L. CHISTOV, ``Efficient factorization of polynomials over local fields'' (Russian), Dokl. Akad. Nauk SSSR 293 (1987), no. 5, 1073-1077. [English translation: Soviet Math. Dokl. 35 (1987), no. 2, 434-438.] MR 88d:11118
  • 10. A. L. CHISTOV, ``Efficient factoring polynomials over local fields and its applications'', Proceedings of the International Congress of Mathematicians, Vol. I, II (Kyoto, 1990), 1509-1519, Math. Soc. Japan, Tokyo, 1991. MR 93e:11152
  • 11. D. COPPERSMITH, ``Solving linear equations over $GF(2)$: block Lanczos algorithm'', Linear Algebra and Its Applications, 192 (1993), 33-60. MR 94i:65044
  • 12. D. COPPERSMITH, ``Solving homogeneous linear equations over $GF(2)$ via block Wiedemann algorithm'', Math. Comp. 62 (1994), no. 205, 333-350. MR 94c:11124
  • 13. D. COX, J. LITTLE AND D. O'SHEA, Using algebraic geometry. Graduate Texts in Mathematics, 185. Springer-Verlag, New York, 1998. MR 99h:13033
  • 14. D. DUVAL, ``Absolute factorization of polynomials: a geometric approach'', SIAM J. Comput. 20 (1991), 1-21. MR 92d:12018
  • 15. S. GAO (Gao's papers are available at, ``Absolute irreducibility of polynomials via Newton polytopes'', J. of Algebra 237 (2001), 501-520. CMP 2001:09
  • 16. S. GAO AND A. G. B. LAUDER, ``Decomposition of polytopes and polynomials'', Discrete and Computational Geometry 26 (2001), 89-104. CMP 1 832 732
  • 17. S. GAO AND A. G. B. LAUDER, ``Factoring polynomials via polytopes'', in preparation.
  • 18. S. GAO AND A. G. B. LAUDER, ``Fast absolute irreducibility testing via Newton polytopes,'' preprint, 2000. (13 pages)
  • 19. S. GAO AND A. G. B. LAUDER, ``Hensel lifting and bivariate polynomial factorisation over finite fields,'' to appear in Mathematics of Computation. (17 pages)
  • 20. S. GAO AND J. VON ZUR GATHEN, ``Berlekamp's and Niederreiter's polynomial factorization algorithms'', Proc. 2nd International Conference on Finite Fields: Theory, Applications, and Algorithms, Las Vegas, 1993. Contemporary Mathematics, vol. 168, 1994, 101-116. MR 95f:11106
  • 21. J. VON ZUR GATHEN, ``Irreducibility of multivariate polynomials'', J. Comput. System Sci. 31 (1985), no. 2, 225-264. MR 87f:12002a
  • 22. J. VON ZUR GATHEN AND J. GERHARD, Modern Computer Algebra, Cambridge University Press, New York, 1999. MR 2000j:68205
  • 23. J. VON ZUR GATHEN AND E. KALTOFEN, ``Factorization of multivariate polynomials over finite fields'', Math. Comp. 45 (1985), no. 171, 251-261. MR 87a:12005
  • 24. J. VON ZUR GATHEN AND E. KALTOFEN, ``Factoring sparse multivariate polynomials'', J. of Comput. System Sci. 31 (1985), 265-287. MR 87f:12002b
  • 25. J. VON ZUR GATHEN AND V. SHOUP, ``Computing Frobenius maps and factoring polynomials'', Computational Complexity 2 (1992), 187-224. MR 94d:12011
  • 26. K. O. GEDDES, S. R. CZAPOR AND G. LABAHN, Algorithms for Computer Algebra, Kluwer, Boston/Dordrecht/London, 1992. MR 96a:68049
  • 27. D. YU GRIGORYEV, ``Factoring polynomials over a finite field and solution of systems of algebraic equations'' (Russian), Theory of the complexity of computations, II., Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI) 137 (1984), 124-188 [English translation: J. Sov. Math. 34 (1986)]. MR 86g:11077
  • 28. D. YU GRIGORYEV AND A. L. CHISTOV, ``Fast factorization of polynomials into irreducible ones and the solution of systems of algebraic equations'' (Russian), Dokl. Akad. Nauk SSSR 275 (1984), no. 6, 1302-1306. [English translation: Soviet Math. Dokl. 29 (1984), no. 2, 380-383.] MR 86d:11101
  • 29. R. HARTSHORNE, Algebraic Geometry, Springer-Verlag, Berlin, New York, 1977. MR 57:3116
  • 30. E. KALTOFEN, ``Polynomial-time reductions from multivariate to bi- and univariate integral polynomial factorization'', SIAM J. Comput. 14 (1985), no. 2, 469-489. MR 86j:12001
  • 31. E. KALTOFEN, ``Computing the irreducible real factors and components of an algebraic curve'', Appl. Algebra Engrg. Comm. Comput. 1 (1990), 135-148. MR 96a:14063
  • 32. E. KALTOFEN, ``Effective Noether irreducibility forms and applications'', Symposium on the Theory of Computing (New Orleans, LA, 1991). J. Comput. System Sci. 50 (1995), no. 2, 274-295. MR 96g:68053
  • 33. E. KALTOFEN AND B. D. SAUNDERS, ``On Wiedemann's method of solving sparse linear systems'', in Proc. AAECC-9, LNCS 539, Springer-Verlag, 1991, 29-38. MR 94b:68003
  • 34. E. KALTOFEN AND V. SHOUP, ``Subquadratic-time factoring of polynomials over finite fields'', Math. Comp. 67 (1998), no. 223, 1179-1197. MR 99m:68097
  • 35. E. KALTOFEN AND B. TRAGER, ``Computing with polynomials given by black boxes for their evaluations: Greatest common divisors, factorization, separation of numerators and denominators'', J. Symbolic Comput. 9 (1990), 301-320. MR 91k:68100
  • 36. B. A. LAMACCHIA AND A. M. ODLYZKO, ``Solving large sparse systems over finite fields'', Advances in Cryptology, CRYPTO '90 (A.J. Menezes and S.A. Vanstone, eds.), LNCS 537, Springer-Verlag, 109-133. MR 94b:94002
  • 37. D. LAZARD AND R. RIOBOO, ``Integration of rational functions: rational computation of the logarithmic part'', J. Symbolic Comput. 9 (1990), no. 2, 113-115. MR 91h:68091
  • 38. A. K. LENSTRA, ``Factoring multivariate integral polynomials'', Theoret. Comput. Sci. 34 (1984), no. 1-2, 207-213. MR 86g:12001a
  • 39. A. K. LENSTRA, ``Factoring multivariate polynomials over finite fields'', J. Comput. System Sci. 30 (1985), no. 2, 235-248. MR 87a:11124
  • 40. A. K. LENSTRA, ``Factoring multivariate polynomials over algebraic number fields'', SIAM J. Comput. 16 (1987), no. 3, 591-598. MR 88j:12001
  • 41. A. K. LENSTRA, H. W. LENSTRA, JR. AND L. LOV´ASZ, ``Factoring polynomials with rational coefficients'', Mathematische Annalen, 161 (1982), 515-534. MR 84a:12002
  • 42. P. L. MONTGOMERY, ``A block Lanczos Algorithm for finding dependencies over $GF(2)$'', Advances in cryptology--EUROCRYPT '95 (Saint-Malo, 1995), LNCS 921, Springer, Berlin, 1995, 106-120. MR 97c:11115
  • 43. D. MUMFORD, Algebraic Geometry I: Complex Projective Varieties, Springer-Verlag, Berlin, New York, 1976. MR 56:11992
  • 44. D. R. MUSSER, ``Multivariate polynomial factorization'', J. ACM 22 (1975), 291-308. MR 53:335a
  • 45. H. NIEDERREITER, ``A new efficient factorization algorithm for polynomials over small finite fields'', Appl. Alg. Eng. Comm. Comp. 4 (1993), 81-87. MR 94h:11112
  • 46. V. Y. PAN, ``Solving a polynomial equation: some history and recent progress'', SIAM Rev. 39 (1997), 187-220. MR 99b:65066
  • 47. R. RUBINFELD AND R. ZIPPEL ``A new modular interpolation algorithm for factoring multivariate polynomials (extended abstract)'', in Proc. 1994 Algorithmic Number Theory Symposium (L. M. Adleman and M.-D. Huang, eds.), LNCS 877, Springer-Verlag, 1994, 93-107. MR 96d:12013
  • 48. W. RUPPERT, ``Reduzibilität ebener Kurven'', J. reine angew. Math. 369 (1986), 167-191. MR 88j:14010
  • 49. W. M. RUPPERT, ``Reducibility of polynomials $f(x,y)$ modulo $p$'', J. Number Theory 77 (1999), 62-70. MR 2000d:11128
  • 50. A. SCH¨ONHAGE AND V. STRASSEN, ``Schnelle Multiplikation großer Zahlen'', Computing 7 (1971), 281-292. MR 45:1431
  • 51. J.T. SCHWARTZ, ``Fast probabilistic algorithms for verification of polynomial identities,'' J. ACM 27 (1980), 710-717. MR 82m:68078
  • 52. P. S. WANG, ``An improved multivariate polynomial factorization algorithm'', Math. Comp. 32 (1978), 1215-1231. MR 58:27887
  • 53. D. H. WIEDEMANN, ``Solving sparse linear equations over finite fields'', IEEE Trans. Inform. Theory 32 (1986), 54-62. MR 87g:11166
  • 54. R. ZIPPEL, ``Probabilistic algorithms for sparse polynomials'', Symbolic and algebraic computation (EUROSAM '79, Internat. Sympos., Marseille, 1979), pp. 216-226, Lecture Notes in Comput. Sci., 72, Springer, Berlin-New York, 1979. MR 81g:68061

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 12Y05, 68W30, 11Y16, 12D05, 13P05

Retrieve articles in all journals with MSC (2000): 12Y05, 68W30, 11Y16, 12D05, 13P05

Additional Information

Shuhong Gao
Affiliation: Department of Mathematical Sciences, Clemson University, Clemson, South Carolina 29634-0975

Keywords: Polynomial factorization, absolute irreducibility, partial differential equations, Hilbert irreducibility theorem
Received by editor(s): July 19, 2000
Received by editor(s) in revised form: May 8, 2001
Published electronically: February 28, 2002
Additional Notes: The author was supported in part by NSF Grant DMS9970637, NSA Grant MDA904-00-1-0048 and ONR Grant N00014-00-1-0565. Part of the work was done while the author was a member at the Mathematical Sciences Research Institute in Berkeley, CA, USA
Article copyright: © Copyright 2002 American Mathematical Society

American Mathematical Society