Tuning and Generalizing Van Hoeij's Algorithm

Karim Belabas , Guillaume Hanrot (1) , Paul Zimmermann (1)

1 SPACES - Solving problems through algebraic computation and efficient software

Recently, van Hoeij's published a new algorithm for factoring polynomials over the rational integers [11]. This algorithms rests on the same principle as Berlekamp-Zassenhaus [2, 13], but uses lattice basis reduction to improve drastically on the recombination phase. The efficiency of the LLL algorithm is very dependent on fine tuning; in this paper, we present such tuning to achieve better performance. Simultaneously, we describe a generalization of van Hoeij's algorithm to factor polynomials over number fields.

Mots clés: POLYNOMIAL FACTORIZATION; LATTICE BASIS REDUCTION; LLL ALGORITHM; FACTORIZATION OVER NUMBER FIELDS

Domaines: Autre [cs.OH]

Karim Belabas, Guillaume Hanrot, Paul Zimmermann. Tuning and Generalizing Van Hoeij's Algorithm. [Research Report] RR-4124, INRIA. 2001. ⟨inria-00072504⟩