Factoring multivariate polynomials via partial differential equations

Gao, Shuhong

doi:10.1090/S0025-5718-02-01428-X

Factoring multivariate polynomials via partial differential equations
HTML articles powered by AMS MathViewer

by Shuhong Gao PDF

Math. Comp. 72 (2003), 801-822 Request permission

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

Chanderjit Bajaj, John Canny, Thomas Garrity, and Joe Warren, Factoring rational polynomials over the complex numbers, SIAM J. Comput. 22 (1993), no. 2, 318–331. MR 1207788, DOI 10.1137/0222024
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
Lenore Blum, Felipe Cucker, Michael Shub, and Steve Smale, Complexity and real computation, Springer-Verlag, New York, 1998. With a foreword by Richard M. Karp. MR 1479636, DOI 10.1007/978-1-4612-0701-6
W. S. Brown, On Euclid’s algorithm and the computation of polynomial greatest common divisors, J. Assoc. Comput. Mach. 18 (1971), 478–504. MR 307450, DOI 10.1145/321662.321664
David G. Cantor and Erich Kaltofen, On fast multiplication of polynomials over arbitrary algebras, Acta Inform. 28 (1991), no. 7, 693–701. MR 1129288, DOI 10.1007/BF01178683
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
R. H. J. Germay, Généralisation de l’équation de Hesse, Ann. Soc. Sci. Bruxelles Sér. I 59 (1939), 139–144 (French). MR 86
A. L. Chistov, Efficient factorization of polynomials over local fields, Dokl. Akad. Nauk SSSR 293 (1987), no. 5, 1073–1077 (Russian). MR 890201
Alexandre L. Chistov, Efficient factoring polynomials over local fields and its applications, Proceedings of the International Congress of Mathematicians, Vol. I, II (Kyoto, 1990) Math. Soc. Japan, Tokyo, 1991, pp. 1509–1519. MR 1159333
Don Coppersmith, Solving linear equations over $\textrm {GF}(2)$: block Lanczos algorithm, Linear Algebra Appl. 192 (1993), 33–60. Computational linear algebra in algebraic and related problems (Essen, 1992). MR 1236735, DOI 10.1016/0024-3795(93)90235-G
Don Coppersmith, Solving homogeneous linear equations over $\textrm {GF}(2)$ via block Wiedemann algorithm, Math. Comp. 62 (1994), no. 205, 333–350. MR 1192970, DOI 10.1090/S0025-5718-1994-1192970-7
David Cox, John Little, and Donal O’Shea, Using algebraic geometry, Graduate Texts in Mathematics, vol. 185, Springer-Verlag, New York, 1998. MR 1639811, DOI 10.1007/978-1-4757-6911-1
Dominique Duval, Absolute factorization of polynomials: a geometric approach, SIAM J. Comput. 20 (1991), no. 1, 1–21. MR 1082133, DOI 10.1137/0220001
S. Gao (Gao’s papers are available at http://www.math.clemson.edu/faculty/Gao), “Absolute irreducibility of polynomials via Newton polytopes”, J. of Algebra 237 (2001), 501–520.
S. Gao and A. G. B. Lauder, “Decomposition of polytopes and polynomials”, Discrete and Computational Geometry 26 (2001), 89–104.
S. Gao and A. G. B. Lauder, “Factoring polynomials via polytopes”, in preparation.
S. Gao and A. G. B. Lauder, “Fast absolute irreducibility testing via Newton polytopes,” preprint, 2000. (13 pages)
S. Gao and A. G. B. Lauder, “Hensel lifting and bivariate polynomial factorisation over finite fields,” to appear in Mathematics of Computation. (17 pages)
Shuhong Gao and Joachim von zur Gathen, Berlekamp’s and Niederreiter’s polynomial factorization algorithms, Finite fields: theory, applications, and algorithms (Las Vegas, NV, 1993) Contemp. Math., vol. 168, Amer. Math. Soc., Providence, RI, 1994, pp. 101–116. MR 1291420, DOI 10.1090/conm/168/01691
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 and Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, 1999. MR 1689167
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
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 and Victor Shoup, Computing Frobenius maps and factoring polynomials, Comput. Complexity 2 (1992), no. 3, 187–224. MR 1220071, DOI 10.1007/BF01272074
K. O. Geddes, S. R. Czapor, and G. Labahn, Algorithms for computer algebra, Kluwer Academic Publishers, Boston, MA, 1992. MR 1256483, DOI 10.1007/b102438
R. H. J. Germay, Généralisation de l’équation de Hesse, Ann. Soc. Sci. Bruxelles Sér. I 59 (1939), 139–144 (French). MR 86
D. Yu. Grigor′ev and A. L. Chistov, Fast factorization of polynomials into irreducible ones and the solution of systems of algebraic equations, Dokl. Akad. Nauk SSSR 275 (1984), no. 6, 1302–1306 (Russian). MR 746374
Robin Hartshorne, Algebraic geometry, Graduate Texts in Mathematics, No. 52, Springer-Verlag, New York-Heidelberg, 1977. MR 0463157, DOI 10.1007/978-1-4757-3849-0
Erich Kaltofen, Polynomial-time reductions from multivariate to bi- and univariate integral polynomial factorization, SIAM J. Comput. 14 (1985), no. 2, 469–489. MR 784750, DOI 10.1137/0214035
Erich Kaltofen, Computing the irreducible real factors and components of an algebraic curve, Appl. Algebra Engrg. Comm. Comput. 1 (1990), no. 2, 135–148. MR 1325518, DOI 10.1007/BF01810297
Erich Kaltofen, Effective Noether irreducibility forms and applications, J. Comput. System Sci. 50 (1995), no. 2, 274–295. 23rd Symposium on the Theory of Computing (New Orleans, LA, 1991). MR 1330258, DOI 10.1006/jcss.1995.1023
U. Kastens and P. Pfahler (eds.), Compiler construction, Lecture Notes in Computer Science, vol. 641, Springer-Verlag, Berlin, 1992. MR 1230391, DOI 10.1007/3-540-55984-1
Erich Kaltofen and Victor Shoup, Subquadratic-time factoring of polynomials over finite fields, Math. Comp. 67 (1998), no. 223, 1179–1197. MR 1459389, DOI 10.1090/S0025-5718-98-00944-2
Erich Kaltofen and Barry M. 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), no. 3, 301–320. MR 1056629, DOI 10.1016/S0747-7171(08)80015-6
A. J. Menezes and S. A. Vanstone (eds.), Advances in cryptology—CRYPTO ’90, Lecture Notes in Computer Science, vol. 537, Springer-Verlag, Berlin, 1991. MR 1232866, DOI 10.1007/3-540-38424-3
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 1056840, DOI 10.1016/S0747-7171(08)80026-0
A. K. Lenstra, Factoring multivariate integral polynomials, Theoret. Comput. Sci. 34 (1984), no. 1-2, 207–213. MR 774045, DOI 10.1016/0304-3975(84)90117-8
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
Arjen K. Lenstra, Factoring multivariate polynomials over algebraic number fields, SIAM J. Comput. 16 (1987), no. 3, 591–598. MR 889410, DOI 10.1137/0216040
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
Peter L. Montgomery, A block Lanczos algorithm for finding dependencies over $\textrm {GF}(2)$, Advances in cryptology—EUROCRYPT ’95 (Saint-Malo, 1995) Lecture Notes in Comput. Sci., vol. 921, Springer, Berlin, 1995, pp. 106–120. MR 1367513, DOI 10.1007/3-540-49264-X_{9}
David Mumford, Algebraic geometry. I, Grundlehren der Mathematischen Wissenschaften, No. 221, Springer-Verlag, Berlin-New York, 1976. Complex projective varieties. MR 0453732
David R. Musser, Multivariate polynomial factorization, J. Assoc. Comput. Mach. 22 (1975), 291–308. MR 396470, DOI 10.1145/321879.321890
Harald Niederreiter, A new efficient factorization algorithm for polynomials over small finite fields, Appl. Algebra Engrg. Comm. Comput. 4 (1993), no. 2, 81–87. MR 1223850, DOI 10.1007/BF01386831
Victor Y. Pan, Solving a polynomial equation: some history and recent progress, SIAM Rev. 39 (1997), no. 2, 187–220. MR 1453318, DOI 10.1137/S0036144595288554
Ronitt Rubinfeld and Richard Zippel, A new modular interpolation algorithm for factoring multivariate polynomials (extended abstract), Algorithmic number theory (Ithaca, NY, 1994) Lecture Notes in Comput. Sci., vol. 877, Springer, Berlin, 1994, pp. 93–107. MR 1322715, DOI 10.1007/3-540-58691-1_{4}7
Wolfgang Ruppert, Reduzibilität ebener Kurven, J. Reine Angew. Math. 369 (1986), 167–191 (German). MR 850633, DOI 10.1515/crll.1986.369.167
Wolfgang M. Ruppert, Reducibility of polynomials $f(x,y)$ modulo $p$, J. Number Theory 77 (1999), no. 1, 62–70. MR 1695700, DOI 10.1006/jnth.1999.2381
A. Schönhage and V. Strassen, Schnelle Multiplikation grosser Zahlen, Computing (Arch. Elektron. Rechnen) 7 (1971), 281–292 (German, with English summary). MR 292344, DOI 10.1007/bf02242355
J. T. Schwartz, Fast probabilistic algorithms for verification of polynomial identities, J. Assoc. Comput. Mach. 27 (1980), no. 4, 701–717. MR 594695, DOI 10.1145/322217.322225
Leo F. Epstein, A function related to the series for $e^{e^x}$, J. Math. Phys. Mass. Inst. Tech. 18 (1939), 153–173. MR 58, DOI 10.1002/sapm1939181153
Douglas H. Wiedemann, Solving sparse linear equations over finite fields, IEEE Trans. Inform. Theory 32 (1986), no. 1, 54–62. MR 831560, DOI 10.1109/TIT.1986.1057137
Richard Zippel, Probabilistic algorithms for sparse polynomials, Symbolic and algebraic computation (EUROSAM ’79, Internat. Sympos., Marseille, 1979) Lecture Notes in Comput. Sci., vol. 72, Springer, Berlin-New York, 1979, pp. 216–226. MR 575692