Practical polynomial factoring in polynomial time

Abstract : An algorithm was presented in Novocin's thesis to factor polynomials in Q[x]. The key result was to show that the number of LLL switches used during the factorization could be bounded by O(r^3 ) where r is the number of factors mod- ulo a prime. The thesis also claimed that it should be possi- ble to design an implementation which (a) in the worst case is comparable to the best implementations in practice and (b) could outperform existing implementations on a large class of polynomials by requiring less Hensel lifting. The goal of this paper is to verify these claims with an actual implementation.
Type de document :
Pré-publication, Document de travail
Pre-Print. 2010
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger
Contributeur : Andrew Novocin <>
Soumis le : lundi 13 décembre 2010 - 16:33:39
Dernière modification le : jeudi 17 janvier 2019 - 15:16:03
Document(s) archivé(s) le : lundi 5 novembre 2012 - 13:30:15


Fichiers produits par l'(les) auteur(s)


  • HAL Id : ensl-00546114, version 1



William Hart, Mark Van Hoeij, Andrew Novocin. Practical polynomial factoring in polynomial time. Pre-Print. 2010. 〈ensl-00546114〉



Consultations de la notice


Téléchargements de fichiers