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: JOUR
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 todo:paper_0885064X_v23_n2_p193_Avendano
record_format dspace
spelling todo:paper_0885064X_v23_n2_p193_Avendano2023-10-03T15:40:39Z Factoring bivariate sparse (lacunary) polynomials 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. JOUR 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)
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 JOUR
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
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_ 1782024785719459840

Ejemplares similares