Finding small degree factors of multivariate supersparse (lacunary) polynomials over algebraic number fields

ABSTRACT

We present algorithms that compute all irreducible factors of degree ≤ d of supersparse (lacunary) multivariate polynomials in n variables over an algebraic number field in deterministic polynomial-time in (l+d)ⁿ, where l is the size of the input polynomial. In supersparse polynomials, the term degrees enter logarithmically as their numbers of binary digits into the size measure l. The factors are again represented as supersparse polynomials. If the factors are represented as straight-line programs or black box polynomials, we can achieve randomized polynomial-time in (l+d)^O(1). Our approach follows that by H. W. Lenstra, Jr., on computing factors of univariate supersparse polynomials over algebraic number fields. We generalize our ISSAC 2005 results for computing linear factors of supersparse bivariate polynomials over the rational numbers by appealing to recent lower bounds on the height of algebraic numbers and to a special case of the former Lang conjecture.

REFERENCES

• 1: Amoroso, F., and Zannier, U. A relative Dobrowolski lower bound over Abelian varieties. Ann. Scuola Norm. Sup. Pisa Cl. Sci. (4) XXIX (2000), 711--727.
• 2: Felipe Cucker , Pascal Koiran , Steve Smale, A polynomial time algorithm for diophantine equations in one variable, Journal of Symbolic Computation, v.27 n.1, p.21-29, Jan. 1999 [doi>10.1006/jsco.1998.0242]
• 3: Joachim von zur Gathen , Erich Kaltofen, Factoring sparse multivariate polynomials, Journal of Computer and System Sciences, v.31 n.2, p.265-287, Sept. 1985 [doi>10.1016/0022-0000(85)90044-3]
• 4: Gyõry, K., Iwaniec, H., and Urbanowicz, J., Eds. Number Theory in Progress (1999), vol. 1 Diophantine Problems and Polynomials, Stefan Banach Internat. Center, Walter de Gruyter Berlin/New York. Proc. Internat. Conf. Number Theory in Honor of the 60th Birthday of Andrzej Schinzel, Zakopane, Poland June 30-July 9, 1997.
• 5: Hindry, M., and Silverman, J. H. Diophantine Geometry: An Introduction. Springer Verlag, Heidelberg, Germany, 2000.
• 6: Humphreys, J. E. Linear Algebraic Groups. Springer Verlag, New York, 1975.
• 7: Kaltofen, E. Polynomial-time reductions from multivariate to bi- and univariate integral polynomial factorization. SIAM J. Comput. 14, 2 (1985), 469--489.
• 8: Erich Kaltofen, Greatest common divisors of polynomials given by straight-line programs, Journal of the ACM (JACM), v.35 n.1, p.231-264, Jan. 1988 [doi>10.1145/42267.45069]
• 9: Kaltofen, E. Factorization of polynomials given by straight-line programs. In Randomness and Computation, S. Micali, Ed., vol. 5 of Advances in Computing Research. JAI Press Inc., Greenwhich, Connecticut, 1989, pp. 375--412.
• 10: Erich Kaltofen, Polynomial Factorization 1987-1991, Proceedings of the 1st Latin American Symposium on Theoretical Informatics, p.294-313, April 06-10, 1992
• 11: Erich Kaltofen , Pascal Koiran, On the complexity of factoring bivariate supersparse (Lacunary) polynomials, Proceedings of the 2005 international symposium on Symbolic and algebraic computation, p.208-215, July 24-27, 2005, Beijing, China [doi>10.1145/1073884.1073914]
• 12: Erich Kaltofen , Wen-shin Lee, Early termination in sparse interpolation algorithms, Journal of Symbolic Computation, v.36 n.3-4, p.365-400, September 2003 [doi>10.1016/S0747-7171(03)00088-9]
• 13: Erich Kaltofen , Barry M. Trager, Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators, Journal of Symbolic Computation, v.9 n.3, p.301-320, March 1990 [doi>10.1016/S0747-7171(08)80015-6]
• 14: Lang, S. Algebra. Addison-Wesley, 1993.
• 15: Laurent, M. Equations diophantiennes exponentielles. Inventiones Mathematicae 78, 2 (1984), 299--327.
• 16: Lenstra, Jr., H. W. Finding small degree factors of lacunary polynomials. In Gyõry et al. {4}, pp. 267--276.
• 17: Lenstra, Jr., H. W. On the factorization of lacunary polynomials. In Gyõry et al. {4}, pp. 277--291.
• 18: Plaisted, D. A. New NP-hard and NP-complete polynomial and integer divisibility problems. Theoretical Comput. Sci. 13 (1984), 125--138.
• 19: van der Waerden, B. L. Moderne Algebra. Springer Verlag, Berlin, 1940. English transl. publ. under the title "Modern algebra" by F. Ungar Publ. Co., New York, 1953.
• 20: Waldschmidt, M. Diophantine approximation on linear algebraic groups. Springer Verlag, Heidelberg, Germany, 2000.
• 21: Zippel, R. E. Probabilistic algorithms for sparse polynomials. PhD thesis, Massachusetts Inst. of Technology, Cambridge, USA, Sept. 1979.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Theory

Keywords:
Lang conjecture, algebraic numbers, height, lacunary polynomials, multivariate polynomials, polynomial factorization, polynomial-time complexity, sparse polynomials