HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 : Friday, February 4, 2022 - 3:32:50 AM
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