Modular Las Vegas Algorithms for Polynomial Absolute Factorization

Cristina Bertone 1, * Guillaume Chèze 2 André Galligo 1
* Auteur correspondant
1 GALAAD - Geometry, algebra, algorithms
CRISAM - Inria Sophia Antipolis - Méditerranée , UNS - Université Nice Sophia Antipolis, CNRS - Centre National de la Recherche Scientifique : UMR6621
Abstract : Let $f(X,Y) \in \ZZ[X,Y]$ be an irreducible polynomial over $\QQ$. We give a Las Vegas absolute irreducibility test based on a property of the Newton polytope of $f$, or more precisely, of $f$ modulo some prime integer $p$. The same idea of choosing a $p$ satisfying some prescribed properties together with $LLL$ is used to provide a new strategy for absolute factorization of $f(X,Y)$. We present our approach in the bivariate case but the techniques extend to the multivariate case. Maple computations show that it is efficient and promising as we are able to factorize some polynomials of degree up to 400.
Type de document :
Article dans une revue
Journal of Symbolic Computation, Elsevier, 2010, 45 (12), pp.1280-1295. 〈10.1016/j.jsc.2010.06.010〉
Liste complète des métadonnées

Littérature citée [34 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00436063
Contributeur : Cristina Bertone <>
Soumis le : jeudi 28 janvier 2010 - 16:21:19
Dernière modification le : jeudi 18 janvier 2018 - 10:39:11
Document(s) archivé(s) le : jeudi 23 septembre 2010 - 11:35:46

Fichiers

bcgHAL2.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Cristina Bertone, Guillaume Chèze, André Galligo. Modular Las Vegas Algorithms for Polynomial Absolute Factorization. Journal of Symbolic Computation, Elsevier, 2010, 45 (12), pp.1280-1295. 〈10.1016/j.jsc.2010.06.010〉. 〈inria-00436063v2〉

Partager

Métriques

Consultations de la notice

355

Téléchargements de fichiers

206