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$).
Complete list of metadatas

Contributor : Paul Zimmermann <>
Submitted on : Tuesday, October 23, 2007 - 10:03:21 PM
Last modification on : Thursday, January 11, 2018 - 6:21:04 AM
Long-term archiving on : Sunday, April 11, 2010 - 11:35:26 PM


Files produced by the author(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⟩



Record views


Files downloads