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

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00546114
Contributeur : Andrew Novocin <>
Soumis le : lundi 13 décembre 2010 - 16:33:39
Dernière modification le : vendredi 20 avril 2018 - 15:44:24
Document(s) archivé(s) le : lundi 5 novembre 2012 - 13:30:15

Fichier

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

Identifiants

  • HAL Id : ensl-00546114, version 1

Collections

Citation

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

Partager

Métriques

Consultations de la notice

591

Téléchargements de fichiers

166