×

Factoring bivariate sparse (lacunary) polynomials. (English) Zbl 1170.12004

Summary: We present a deterministic algorithm for computing all irreducible factors of degree \(\leq d\) of a given bivariate polynomial \(f\in K[x,y]\) over an algebraic number field \(K\) and their multiplicities, whose running time is polynomial in the bit length of the sparse encoding of the input and in \(d\). Moreover, we show that the factors over \(\mathbb Q\) of degree \(\leq d\) which are not binomials can also be computed in time polynomial in the sparse length of the input and in \(d\).

MSC:

12Y05 Computational aspects of field theory and polynomials (MSC2010)
11G50 Heights
11Y40 Algebraic number theory computations
11Y16 Number-theoretic algorithms; complexity
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Amoroso, F.; David, S., Minoration de la hauteur normalisée des hypersurfaces, Acta Arith., 92, 339-366 (2000) · Zbl 0948.11025
[2] Amoroso, F.; David, S., Minoration de la hauteur normalisée dans un tore, J. Inst. Math. Jussieu, 2, 335-381 (2003) · Zbl 1041.11048
[3] K. Belabas, M. van Hoeij, J. Klüners, A. Steel, Factoring polynomials over global fields, preprint, 2005.; K. Belabas, M. van Hoeij, J. Klüners, A. Steel, Factoring polynomials over global fields, preprint, 2005.
[4] Berlekamp, E. R., Factoring polynomials over large finite fields, Math. Comp., 24, 713-735 (1970) · Zbl 0247.12014
[5] A.L. Chistov, D.Y. Grigoriev, Polynomial-time factoring of the multivariate polynomials over a global field, LOMI preprint E-5-82, Leningrad, 1982.; A.L. Chistov, D.Y. Grigoriev, Polynomial-time factoring of the multivariate polynomials over a global field, LOMI preprint E-5-82, Leningrad, 1982.
[6] Cucker, F.; Koiran, P.; Smale, S., A polynomial time algorithm for Diophantine equations in one variable, J. Symbolic Comput., 27, 21-29 (1999) · Zbl 0920.11085
[7] David, S.; Philippon, P., Minoration des hauteurs normalisées des sous-variétés des tores, Ann. Sci. Scuola Norm. Sup. Pisa, 28, 489-543 (1999) · Zbl 1002.11055
[8] Dobrowolski, E., On a question of Lehmer and the number of irreducible factors of a polynomial, Acta Arith., 34, 391-401 (1979) · Zbl 0416.12001
[9] M. Hindry, J.H. Silverman, Diophantine Geometry. An Introduction, Graduate Texts in Mathematics, vol. 201, Springer, 2000.; M. Hindry, J.H. Silverman, Diophantine Geometry. An Introduction, Graduate Texts in Mathematics, vol. 201, Springer, 2000.
[10] Kaltofen, E., Polynomial-time reductions from multivariate to bi- and univariate integral polynomial factorization, SIAM J. Comput., 14, 469-489 (1995) · Zbl 0605.12001
[11] Kaltofen, E., Effective Noether irreducibility forms and applications, J. Comput. System Sci., 50, 274-295 (1995) · Zbl 0844.12006
[12] E. Kaltofen, P. Koiran, On the complexity of factoring bivariate supersparse (lacunary) polynomials, ISSAC’05, Proceedings of 2005 International Symposium Symbolic Algebraic Computation, ACM Press, New York, 2005.; E. Kaltofen, P. Koiran, On the complexity of factoring bivariate supersparse (lacunary) polynomials, ISSAC’05, Proceedings of 2005 International Symposium Symbolic Algebraic Computation, ACM Press, New York, 2005. · Zbl 1356.11092
[13] E. Kaltofen, P. Koiran, Finding small degree factors of multivariate supersparse (lacunary) polynomials over algebraic number fields, in: ISSAC’06, Proceedings of 2006 International Symposium Symbolic Algebraic Computation, to appear.; E. Kaltofen, P. Koiran, Finding small degree factors of multivariate supersparse (lacunary) polynomials over algebraic number fields, in: ISSAC’06, Proceedings of 2006 International Symposium Symbolic Algebraic Computation, to appear. · Zbl 1356.11093
[14] Landau, S., Factoring polynomials over algebraic number fields, SIAM J. Comput., 14, 184-195 (1985) · Zbl 0565.12002
[15] Lawton, W., A generalization of a theorem of Kronecker, J. Sci. Fac. Chiangmai Univ., 4, 15-23 (1977) · Zbl 0447.12004
[16] G. Lecerf, Improved dense multivariate polynomial factorization algorithms, J. Symbolic Comput., to appear.; G. Lecerf, Improved dense multivariate polynomial factorization algorithms, J. Symbolic Comput., to appear. · Zbl 1127.13021
[17] Lenstra, A. K., Factoring multivariate integral polynomials, Theoret. Comput. Sci., 34, 207-213 (1984) · Zbl 0985.12500
[18] Lenstra, A. K., Factoring multivariate polynomials over algebraic number fields, SIAM J. Comput., 16, 591-598 (1987) · Zbl 0636.12005
[19] Lenstra, A. K.; Lenstra, H. W.; Lovász, L., Factoring polynomials with rational coefficients, Math. Ann., 261, 515-534 (1982) · Zbl 0488.12001
[20] H.W. Lenstra Jr., On the Factorization of Lacunary Polynomials, Number Theory in Progress, vol. 1 (Zakopane-Kościelisko, 1997) de Gruyter, Berlin, 1999, pp. 277-291.; H.W. Lenstra Jr., On the Factorization of Lacunary Polynomials, Number Theory in Progress, vol. 1 (Zakopane-Kościelisko, 1997) de Gruyter, Berlin, 1999, pp. 277-291. · Zbl 0943.11047
[21] H.W. Lenstra Jr., Finding Small Degree Factors of Lacunary Polynomials, Number Theory in Progress, vol. 1 (Zakopane-Kościelisko, 1997) de Gruyter, Berlin, 1999, pp. 267-276.; H.W. Lenstra Jr., Finding Small Degree Factors of Lacunary Polynomials, Number Theory in Progress, vol. 1 (Zakopane-Kościelisko, 1997) de Gruyter, Berlin, 1999, pp. 267-276. · Zbl 0949.11053
[22] Philippon, P., Sur des hauteurs alternatives I, Math. Ann., 289, 255-283 (1991) · Zbl 0726.14017
[23] P. Philippon, M. Sombra, Quelques aspects diophantiens des variétés toriques projectives, E-print \(\langle;\rangle;\); P. Philippon, M. Sombra, Quelques aspects diophantiens des variétés toriques projectives, E-print \(\langle;\rangle;\) · Zbl 1153.11029
[24] C. Pontreau, Une généralisation du théorème de Dobrowolski, pour les hypersurfaces algébriques, Master Thesis, Univ. Caen, 2001, downloadable from \(\langle;\) http://www.math.unicaen.fr/\( \sim;\rangle;\); C. Pontreau, Une généralisation du théorème de Dobrowolski, pour les hypersurfaces algébriques, Master Thesis, Univ. Caen, 2001, downloadable from \(\langle;\) http://www.math.unicaen.fr/\( \sim;\rangle;\)
[25] Pontreau, C., Minoration effective de la hauteur des points d’une courbe de \(G_m^2\) définie sur \(Q\), Acta Arith., 120, 1, 1-26 (2005) · Zbl 1155.11331
[26] C. Pontreau, Geometric lower bounds for the normalized height of hypersurfaces, Internat. J. Number Theory (2006), to appear.; C. Pontreau, Geometric lower bounds for the normalized height of hypersurfaces, Internat. J. Number Theory (2006), to appear. · Zbl 1201.11069
[27] Voutier, P., An effective lower bound for the height of algebraic numbers, Acta Arith., 74, 81-95 (1996)
[28] Zagier, D., Algebraic numbers close to both 0 and 1, Math. Comp., 61, 485-491 (1993) · Zbl 0786.11063
[29] Zassenhaus, H., On Hensel factorization, J. Number Theory, 1, 291-311 (1969) · Zbl 0188.33703
[30] Zhang, S., Small points and adelic metrics, J. Algebraic Geometry, 4, 281-300 (1995) · Zbl 0861.14019
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.