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).
Document type :
Journal articles
Complete list of metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal.inria.fr/inria-00181029
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, October 24, 2007 - 11:17:28 AM
Last modification on : Friday, April 19, 2019 - 3:24:32 PM
Long-term archiving on : Tuesday, September 21, 2010 - 2:46:51 PM

Files

RR-6331.pdf
Files produced by the author(s)

Identifiers

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

Collections

Citation

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

Share

Metrics

Record views

697

Files downloads

348