Factoring bivariate sparse (lacunary) polynomials

Mostrar todas las versiones(3)

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 encodi...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Avendaño, M., Krick, T., Sombra, M.
Formato:	Artículo publishedVersion
Publicado:	2007
Materias:	Height of points Lacunary (sparse) polynomials Lehmer's problem Polynomial factorization Algebra Degrees of freedom (mechanics) Factorization Problem solving Polynomials
Acceso en línea:	http://hdl.handle.net/20.500.12110/paper_0885064X_v23_n2_p193_Avendano http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_0885064X_v23_n2_p193_Avendano_oai
Aporte de:	Repositorio Digital de la Universidad de Buenos Aires (UBA) de Universidad de Buenos Aires

id	I28-R145-paper_0885064X_v23_n2_p193_Avendano_oai
record_format	dspace
spelling	I28-R145-paper_0885064X_v23_n2_p193_Avendano_oai2020-10-19 Avendaño, M. Krick, T. Sombra, M. 2007 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. Fil:Avendaño, M. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Krick, T. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Sombra, M. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. application/pdf http://hdl.handle.net/20.500.12110/paper_0885064X_v23_n2_p193_Avendano info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar J. Complexity 2007;23(2):193-216 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 Factoring bivariate sparse (lacunary) polynomials info:eu-repo/semantics/article info:ar-repo/semantics/artículo info:eu-repo/semantics/publishedVersion http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_0885064X_v23_n2_p193_Avendano_oai
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-145
collection	Repositorio Digital de la Universidad de Buenos Aires (UBA)
topic	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
spellingShingle	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 Avendaño, M. Krick, T. Sombra, M. Factoring bivariate sparse (lacunary) polynomials
topic_facet	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
description	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.
format	Artículo Artículo publishedVersion
author	Avendaño, M. Krick, T. Sombra, M.
author_facet	Avendaño, M. Krick, T. Sombra, M.
author_sort	Avendaño, M.
title	Factoring bivariate sparse (lacunary) polynomials
title_short	Factoring bivariate sparse (lacunary) polynomials
title_full	Factoring bivariate sparse (lacunary) polynomials
title_fullStr	Factoring bivariate sparse (lacunary) polynomials
title_full_unstemmed	Factoring bivariate sparse (lacunary) polynomials
title_sort	factoring bivariate sparse (lacunary) polynomials
publishDate	2007
url	http://hdl.handle.net/20.500.12110/paper_0885064X_v23_n2_p193_Avendano http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_0885064X_v23_n2_p193_Avendano_oai
work_keys_str_mv	AT avendanom factoringbivariatesparselacunarypolynomials AT krickt factoringbivariatesparselacunarypolynomials AT sombram factoringbivariatesparselacunarypolynomials
_version_	1766026714198048768

Factoring bivariate sparse (lacunary) polynomials

Ejemplares similares