Tuning and Generalizing Van Hoeij's Algorithm (original) (raw)

Rapport (Rapport De Recherche) Année : 2001

Résumé

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

Connectez-vous pour contacter le contributeur

https://inria.hal.science/inria-00072504

Soumis le : mercredi 24 mai 2006-10:08:51

Dernière modification le : mardi 4 novembre 2025-12:00:31

Archivage à long terme le : dimanche 4 avril 2010-23:10:41

Dates et versions

inria-00072504 , version 1 (24-05-2006)

Licence

Identifiants

• HAL Id : inria-00072504 , version 1

Citer

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

403 Consultations

468 Téléchargements