On the complexity of factoring bivariate supersparse (Lacunary) polynomials

ABSTRACT

We present algorithms that compute the linear and quadratic factors of supersparse (lacunary) bivariate polynomials over the rational numbers in polynomial-time in the input size. In supersparse polynomials, the term degrees can have hundreds of digits as binary numbers. Our algorithms are Monte Carlo randomized for quadratic factors and deterministic for linear factors. Our approach relies on the results by H. W. Lenstra, Jr., on computing factors of univariate supersparse polynomials over the rational numbers. Furthermore, we show that the problem of determining the irreducibility of a supersparse bivariate polynomial over a large finite field of any characteristic is co-NP-hard via randomized reductions.

REFERENCES

• 1: Agrawal, M., Kayal, N., and Saxena, N. PRIMES is in P. Manuscript, 2002. Available from http://www.cse.iitk.ac.in/news/primality.pdf.
• 2: Barvinok, A. I., and Woods, K. Short rational generating functions for lattice point problems. J. Amer. Math. Soc. 16 (2003), 957--979.
• 3: 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]
• 4: De Loera, J. A., Hemmecke, R., Huggins, P., Sturmfels, B., and Yoshida, R. Short rational functions for toric algebras and applications. J. Symbolic Comput. 38, 2 (2004), 959--973.
• 5: Angel Díaz , Erich Kaltofen, On computing greatest common divisors with polynomials given by black boxes for their evaluations, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.232-239, July 10-12, 1995, Montreal, Quebec, Canada [doi>10.1145/220346.220375]
• 6: Joachim von zur Gathen , Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, NY, 1999
• 7: Joachim von zur Gathen , Marek Karpinski , Igor Shparlinski, Counting curves and their projections, Computational Complexity, v.6 n.1, p.64-99, 1996/1997 [doi>10.1007/BF01202042]
• 8: Goldstein, A. J., and Graham, R. L. A Hadamard-type bound on the coefficients of a determinant of polynomials. SIAM Rev. 16 (1974), 394--395.
• 9: 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.
• 10: Hindry, M., and Silverman, J. H. Diophantine Geometry: an Introduction, vol. 201 of Graduate Texts in Mathematics. Springer, 2000.
• 11: Erich Kaltofen, Sparse Hensel Lifting, Research Contributions from the European Conference on Computer Algebra-Volume 2, p.4-17, April 01-03, 1985
• 12: Kaltofen, E. Sparse Hensel lifting. Tech. Rep. 85-12, Rensselaer Polytechnic Instit., Dept. Comput. Sci., Troy, N. Y., 1985.
• 13: 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]
• 14: Erich Kaltofen, Polynomial Factorization 1987-1991, Proceedings of the 1st Latin American Symposium on Theoretical Informatics, p.294-313, April 06-10, 1992
• 15: Erich Kaltofen, Polynomial factorization: a success story, Proceedings of the 2003 international symposium on Symbolic and algebraic computation, p.3-4, August 03-06, 2003, Philadelphia, PA, USA [doi>10.1145/860854.860857]
• 16: 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]
• 17: Marek Karpinski , Igor Shparlinski, On the Computational Hardness of Testing Square-Freeness of Sparse Polynomials, Proceedings of the 13th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.492-497, November 15-19, 1999
• 18: Lang, S. Algebra. Addison-Wesley, 1993.
• 19: Lenstra, Jr., H. W. Finding small degree factors of lacunary polynomials. In Győry et al. GIU99, pp. 267--276.
• 20: Lenstra, Jr., H. W. On the factorization of lacunary polynomials. In Győry et al. GIU99, pp. 277--291.
• 21: Loos, R. Computing rational zeros of integral polynomials by p-adic expansion. SIAM J. Comput. 12 , 2 (1983), 286--293.
• 22: Plaisted, D. A New NP-hard and NP-complete polynomial and integer divisibility problems. Theoretical Comput. Sci. 13 (1984), 125--138.
• 23: Rosser, J. B., and Schoenfeld, L. Approximate formulas of some functions of prime numbers. Illinois J. Math. 6 (1962), 64--94.
• 24: Schinzel, A., and Zannier, U. The least admissible value of the parameter in Hilbert's Irreducibility Theorem. Acta Arithm. 65 (1995), 371--391.
• 25: Igor E. Shparlinski, Computing Jacobi symbols modulo sparse integers and polynomials and some applications, Journal of Algorithms, v.36 n.2, p.241-252, Aug. 2000 [doi>10.1006/jagm.2000.1091]
• 26: Sprindžuk, V. G. Arithmetic specializations in polynomials. J. reine angew. Math. 340 (1983), 26--52.
• 27: Waldschmidt, M. Diophantine approximation on linear algebraic groups. Springer Verlag, Heidelberg, Germany, 2000.
• 28: 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.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation

General Terms:
Algorithms, Theory

Keywords:
NP-hardness, lacunary polynomials, multivariate polynomials, polynomial factorizations, polynomial-time complexity, sparse polynomials