Let f(X,Y) be an irreducible polynomial over Q. 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 construct the algebraic extension containing one absolute factor of a polynomial of degree up to 400.
Modular Las Vegas Algorithms for Polynomial Absolute Factorization
BERTONE, Cristina;
2010-01-01
Abstract
Let f(X,Y) be an irreducible polynomial over Q. 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 construct the algebraic extension containing one absolute factor of a polynomial of degree up to 400.File | Dimensione | Formato | |
---|---|---|---|
BCGElsevier.pdf
Accesso riservato
Tipo di file:
PDF EDITORIALE
Dimensione
306.47 kB
Formato
Adobe PDF
|
306.47 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.