Skip to Main content Skip to Navigation
Journal articles

Modular Las Vegas Algorithms for Polynomial Absolute Factorization

Cristina Bertone 1, * Guillaume Chèze 2 André Galligo 1
* Corresponding author
1 GALAAD - Geometry, algebra, algorithms
CRISAM - Inria Sophia Antipolis - Méditerranée , UNS - Université Nice Sophia Antipolis (... - 2019), 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.
Document type :
Journal articles
Complete list of metadata

Cited literature [34 references]  Display  Hide  Download
Contributor : Cristina Bertone Connect in order to contact the contributor
Submitted on : Thursday, January 28, 2010 - 4:21:19 PM
Last modification on : Tuesday, December 7, 2021 - 4:04:11 PM
Long-term archiving on: : Thursday, September 23, 2010 - 11:35:46 AM


Files produced by the author(s)



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⟩



Record views


Files downloads