Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

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.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download
Contributor : Andrew Novocin Connect in order to contact the contributor
Submitted on : Monday, December 13, 2010 - 4:33:39 PM
Last modification on : Thursday, September 29, 2022 - 2:58:07 PM
Long-term archiving on: : Monday, November 5, 2012 - 1:30:15 PM


Files produced by the author(s)


  • HAL Id : ensl-00546114, version 1



William Hart, Mark van Hoeij, Andrew Novocin. Practical polynomial factoring in polynomial time. 2010. ⟨ensl-00546114⟩



Record views


Files downloads