A Multi-level Blocking Distinct Degree Factorization Algorithm (original) (raw)

Résumé

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).

Connectez-vous pour contacter le contributeur

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

Soumis le : mercredi 24 octobre 2007-11:17:28

Dernière modification le : mercredi 18 mars 2026-11:52:02

Archivage à long terme le : mardi 21 septembre 2010-14:46:51

Dates et versions

inria-00181029 , version 1 (23-10-2007)

inria-00181029 , version 2 (24-10-2007)

Licence

Identifiants

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

Citer

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

710 Consultations