La plateforme OSKAR Bordeaux évolue pour rejoindre l'archive ouverte HAL. Retrouvez tous vos dépôts sur le nouveau portail HAL UB : https://u-bordeaux.hal.science/. Pour toute aide ou information, contactez-nous info@oskar-bordeaux.fr
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