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 encoding of the input...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Avendaño, M., Krick, T., Sombra, M.
Formato: Artículo publishedVersion
Lenguaje:Inglés
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
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paperaa:paper_0885064X_v23_n2_p193_Avendano
record_format dspace
spelling paperaa:paper_0885064X_v23_n2_p193_Avendano2023-06-12T16:48:20Z Factoring bivariate sparse (lacunary) polynomials J. Complexity 2007;23(2):193-216 Avendaño, M. Krick, T. Sombra, M. 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 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. 2007 info:eu-repo/semantics/article info:ar-repo/semantics/artículo info:eu-repo/semantics/publishedVersion application/pdf eng info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_0885064X_v23_n2_p193_Avendano
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
language Inglés
orig_language_str_mv eng
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
work_keys_str_mv AT avendanom factoringbivariatesparselacunarypolynomials
AT krickt factoringbivariatesparselacunarypolynomials
AT sombram factoringbivariatesparselacunarypolynomials
_version_ 1769810339369582592

Ejemplares similares