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 metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00546114
Contributor : Andrew Novocin <>
Submitted on : Monday, December 13, 2010 - 4:33:39 PM
Last modification on : Thursday, January 17, 2019 - 3:16:03 PM
Long-term archiving on : Monday, November 5, 2012 - 1:30:15 PM

File

poly_factor_NOVOCIN_2010.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : ensl-00546114, version 1

Collections

Citation

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

Share

Metrics

Record views

637

Files downloads

362