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 \emph{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 % PZ: changed ``classical'' into ``naive'' (also elsewhere - RPB) 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 :
[Research Report] 2007, 16 p
Liste complète des métadonnées

Contributeur : Paul Zimmermann <>
Soumis le : mardi 23 octobre 2007 - 22:03:21
Dernière modification le : jeudi 19 mai 2016 - 01:05:31
Document(s) archivé(s) le : dimanche 11 avril 2010 - 23:35:26


Fichiers produits par l'(les) auteur(s)


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


Richard Brent, Paul Zimmermann. A Multi-level Blocking Distinct Degree Factorization Algorithm. [Research Report] 2007, 16 p. <inria-00181029v1>



Consultations de
la notice


Téléchargements du document