Factoring bivariate sparse (lacunary) 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...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Avendaño, Martín, Krick, Teresa Elena Genoveva, Sombra, Martín
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:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0885064X_v23_n2_p193_Avendano 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	paper:paper_0885064X_v23_n2_p193_Avendano
record_format	dspace
spelling	paper:paper_0885064X_v23_n2_p193_Avendano2023-06-08T15:46:37Z Factoring bivariate sparse (lacunary) polynomials Avendaño, Martín Krick, Teresa Elena Genoveva Sombra, Martín 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 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0885064X_v23_n2_p193_Avendano 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, Martín Krick, Teresa Elena Genoveva Sombra, Martín 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.
author	Avendaño, Martín Krick, Teresa Elena Genoveva Sombra, Martín
author_facet	Avendaño, Martín Krick, Teresa Elena Genoveva Sombra, Martín
author_sort	Avendaño, Martín
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	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0885064X_v23_n2_p193_Avendano http://hdl.handle.net/20.500.12110/paper_0885064X_v23_n2_p193_Avendano
work_keys_str_mv	AT avendanomartin factoringbivariatesparselacunarypolynomials AT krickteresaelenagenoveva factoringbivariatesparselacunarypolynomials AT sombramartin factoringbivariatesparselacunarypolynomials
_version_	1768542273640857600

Factoring bivariate sparse (lacunary) polynomials

Ejemplares similares