Navegar

Colección

Datos Estadísticas

Artículo

Este artículo es de Acceso Abierto y puede ser descargado en su versión final desde nuestro repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

We present a deterministic algorithm for computing all irreducible factors of degree ≤ d of a given bivariate polynomial f ∈ K [x, y] over an algebraic number field K and their multiplicities, whose running time is polynomial over the rationals, in the bit length of the sparse encoding of the input and in d. Moreover, we show that the factors over over(Q, -) of degree ≤ d which are not binomials can also be computed in time polynomial in the sparse length of the input and in d. © 2006 Elsevier Inc. All rights reserved.

Registro:

Documento: Artículo
Título:Factoring bivariate sparse (lacunary) polynomials
Autor:Avendaño, M.; Krick, T.; Sombra, M.
Filiación:Departamento de Matemática, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Argentina
Departament d'Àlgebra i Geometria, Universitat de Barcelona, Spain
Palabras clave:Height of points; Lacunary (sparse) polynomials; Lehmer's problem; Polynomial factorization; Algebra; Degrees of freedom (mechanics); Factorization; Problem solving; Height of points; Lacunary (sparse) polynomials; Lehmer's problem; Polynomial factorization; Polynomials
Año:2007
Volumen:23
Número:2
Página de inicio:193
Página de fin:216
DOI: http://dx.doi.org/10.1016/j.jco.2006.06.002
Título revista:Journal of Complexity
Título revista abreviado:J. Complexity
ISSN:0885064X
PDF:https://bibliotecadigital.exactas.uba.ar/download/paper/paper_0885064X_v23_n2_p193_Avendano.pdf
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0885064X_v23_n2_p193_Avendano

Referencias:

  • Amoroso, F., David, S., Minoration de la hauteur normalisée des hypersurfaces (2000) Acta Arith., 92, pp. 339-366
  • Amoroso, F., David, S., Minoration de la hauteur normalisée dans un tore (2003) J. Inst. Math. Jussieu, 2, pp. 335-381
  • Berlekamp, E.R., Factoring polynomials over large finite fields (1970) Math. Comp., 24, pp. 713-735
  • Cucker, F., Koiran, P., Smale, S., A polynomial time algorithm for Diophantine equations in one variable (1999) J. Symbolic Comput., 27, pp. 21-29
  • David, S., Philippon, P., Minoration des hauteurs normalisées des sous-variétés des tores (1999) Ann. Sci. Scuola Norm. Sup. Pisa, 28, pp. 489-543
  • Dobrowolski, E., On a question of Lehmer and the number of irreducible factors of a polynomial (1979) Acta Arith., 34, pp. 391-401
  • Kaltofen, E., Polynomial-time reductions from multivariate to bi- and univariate integral polynomial factorization (1995) SIAM J. Comput., 14, pp. 469-489
  • Kaltofen, E., Effective Noether irreducibility forms and applications (1995) J. Comput. System Sci., 50, pp. 274-295
  • Landau, S., Factoring polynomials over algebraic number fields (1985) SIAM J. Comput., 14, pp. 184-195
  • Lawton, W., A generalization of a theorem of Kronecker (1977) J. Sci. Fac. Chiangmai Univ., 4, pp. 15-23
  • Lenstra, A.K., Factoring multivariate integral polynomials (1984) Theoret. Comput. Sci., 34, pp. 207-213
  • Lenstra, A.K., Factoring multivariate polynomials over algebraic number fields (1987) SIAM J. Comput., 16, pp. 591-598
  • Lenstra, A.K., Lenstra Jr., H.W., Lovász, L., Factoring polynomials with rational coefficients (1982) Math. Ann., 261, pp. 515-534
  • Philippon, P., Sur des hauteurs alternatives I (1991) Math. Ann., 289, pp. 255-283
  • Pontreau, C., Minoration effective de la hauteur des points d'une courbe de Gm 2 définie sur Q (2005) Acta Arith., 120 (1), pp. 1-26
  • Voutier, P., An effective lower bound for the height of algebraic numbers (1996) Acta Arith., 74, pp. 81-95
  • Zagier, D., Algebraic numbers close to both 0 and 1 (1993) Math. Comp., 61, pp. 485-491
  • Zassenhaus, H., On Hensel factorization (1969) J. Number Theory, 1, pp. 291-311
  • Zhang, S., Small points and adelic metrics (1995) J. Algebraic Geometry, 4, pp. 281-300

Citas:

---------- APA ----------
Avendaño, M., Krick, T. & Sombra, M. (2007) . Factoring bivariate sparse (lacunary) polynomials. Journal of Complexity, 23(2), 193-216.
http://dx.doi.org/10.1016/j.jco.2006.06.002
---------- CHICAGO ----------
Avendaño, M., Krick, T., Sombra, M. "Factoring bivariate sparse (lacunary) polynomials" . Journal of Complexity 23, no. 2 (2007) : 193-216.
http://dx.doi.org/10.1016/j.jco.2006.06.002
---------- MLA ----------
Avendaño, M., Krick, T., Sombra, M. "Factoring bivariate sparse (lacunary) polynomials" . Journal of Complexity, vol. 23, no. 2, 2007, pp. 193-216.
http://dx.doi.org/10.1016/j.jco.2006.06.002
---------- VANCOUVER ----------
Avendaño, M., Krick, T., Sombra, M. Factoring bivariate sparse (lacunary) polynomials. J. Complexity. 2007;23(2):193-216.
http://dx.doi.org/10.1016/j.jco.2006.06.002