Factoring bivariate sparse (lacunary) polynomials
Langue
en
Article de revue
Ce document a été publié dans
Journal of Complexity. 2007, vol. 23, p. 193-216
Elsevier
Résumé en anglais
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 ...Lire la suite >
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 in the bit length of the sparse encoding of the input and in d . Moreover, we show that the factors 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 .< Réduire
Origine
Importé de halUnités de recherche