Modular Las Vegas Algorithms for Polynomial Absolute Factorization - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Journal of Symbolic Computation Année : 2010

Modular Las Vegas Algorithms for Polynomial Absolute Factorization

André Galligo
  • Fonction : Auteur
  • PersonId : 835184

Résumé

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.
Fichier principal
Vignette du fichier
bcgHAL2.pdf (247.4 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00436063 , version 1 (25-11-2009)
inria-00436063 , version 2 (28-01-2010)

Identifiants

Citer

Cristina Bertone, Guillaume Chèze, André Galligo. Modular Las Vegas Algorithms for Polynomial Absolute Factorization. Journal of Symbolic Computation, 2010, 45 (12), pp.1280-1295. ⟨10.1016/j.jsc.2010.06.010⟩. ⟨inria-00436063v2⟩
254 Consultations
348 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More