A Multi-level Blocking Distinct Degree Factorization Algorithm

Richard Brent 1 Paul Zimmermann 2
2 CACAO - Curves, Algebra, Computer Arithmetic, and so On
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We give a new algorithm for performing the distinct-degree factorization of a polynomial P(x) over GF(2), using a multi-level blocking strategy. The coarsest level of blocking replaces GCD computations by multiplications, as suggested by Pollard (1975), von~zur Gathen and Shoup (1992), and others. The novelty of our approach is that a finer level of blocking replaces multiplications by squarings, which speeds up the computation in GF(2)[x]/P(x) of certain interval polynomials when P(x) is sparse. As an application we give a fast algorithm to search for all irreducible trinomials x^r + x^s + 1 of degree r over GF(2), while producing a certificate that can be checked in less time than the full search. Naive algorithms cost O(r^2) per trinomial, thus O(r^3) to search over all trinomials of given degree r. Under a plausible assumption about the distribution of factors of trinomials, the new algorithm has complexity O(r^2 (log r)^{3/2}(log log r)^{1/2}) for the search over all trinomials of degree r. Our implementation achieves a speedup of greater than a factor of 560 over the naive algorithm in the case r = 24036583 (a Mersenne exponent). Using our program, we have found two new primitive trinomials of degree 24036583 over GF(2) (the previous record degree was 6972593).
Type de document :
Article dans une revue
Arithmeric, Geometry and Coding Theory - Contemporary mathematics, American Mathematical Society, 2008, Finite Fields and Applications, 461, pp.47-58
Liste complète des métadonnées

https://hal.inria.fr/inria-00181029
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 octobre 2007 - 11:17:28
Dernière modification le : mardi 25 octobre 2016 - 17:02:24
Document(s) archivé(s) le : mardi 21 septembre 2010 - 14:46:51

Fichiers

RR-6331.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00181029, version 2
  • ARXIV : 0710.4410

Citation

Richard Brent, Paul Zimmermann. A Multi-level Blocking Distinct Degree Factorization Algorithm. Arithmeric, Geometry and Coding Theory - Contemporary mathematics, American Mathematical Society, 2008, Finite Fields and Applications, 461, pp.47-58. <inria-00181029v2>

Partager

Métriques

Consultations de
la notice

405

Téléchargements du document

112