Mathematics of Computation

Author(s): Shuhong Gao.
Journal: Math. Comp. 72 (2003), 801-822.
MSC (2000): Primary 12Y05, 68W30; Secondary 11Y16, 12D05, 13P05
Posted: February 28, 2002
Retrieve article in: PDF DVI PostScript

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.

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 : block Lanczos algorithm'', Linear Algebra and Its Applications, 192 (1993), 33-60. MR 94i:65044
12.: D. COPPERSMITH, ``Solving homogeneous linear equations over 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 http://www.math.clemson.edu/faculty/Gao), ``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 '', 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 modulo '', 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

Shuhong Gao
Affiliation: Department of Mathematical Sciences, Clemson University, Clemson, South Carolina 29634-0975
Email: sgao@math.clemson.edu

DOI: 10.1090/S0025-5718-02-01428-X
PII: S 0025-5718(02)01428-X
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
Posted: 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
Copyright of article: Copyright 2002, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS