HAL - INRIA :: [inria-00181029, version 2] A Multi-level Blocking Distinct Degree Factorization Algorithm

inria-00181029, version 2

arXiv:0710.4410

Voir la fiche détaillée

BibTeX EndNote TEI RefWorks

%% inria-00181029, version 2
%% http://hal.inria.fr/inria-00181029/en/
@article{BRENT:2008:INRIA-00181029:2,
	title = { {A} {M}ulti-level {B}locking {D}istinct {D}egree {F}actorization {A}lgorithm},
	author = {{B}rent, {R}ichard and {Z}immermann, {P}aul},
	abstract = {{W}e give a new algorithm for performing the distinct-degree factorization of a polynomial {P}(x) over {GF}(2), using a multi-level blocking strategy. {T}he coarsest level of blocking replaces {GCD} computations by multiplications, as suggested by {P}ollard (1975), von~zur {G}athen and {S}houp (1992), and others. {T}he 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. {A}s 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. {N}aive algorithms cost {O}(r^2) per trinomial, thus {O}(r^3) to search over all trinomials of given degree r. {U}nder 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. {O}ur implementation achieves a speedup of greater than a factor of 560 over the naive algorithm in the case r = 24036583 (a {M}ersenne exponent). {U}sing our program, we have found two new primitive trinomials of degree 24036583 over {GF}(2) (the previous record degree was 6972593).},
	keywords = {{A}mortized complexity; distinct degree factorization; finite field; irreducible trinomial; {M}ersenne exponent; polynomial factorization; primitive trinomial},
	language = {{A}nglais},
	affiliation = {{M}athematical {S}ciences {I}nstitute - {M}athematical {S}ciences {I}nstitute - {CACAO} ({C}ourbes, {A}lg{\`e}bre, {C}alculs, {A}rithm{\'e}tique des {O}rdinateurs) - {INRIA} {L}orraine - {LORIA} - {CNRS} : {UMR}7503 - {INRIA} - {U}niversit{\'e} {H}enri {P}oincar{\'e} - {N}ancy {I} - {U}niversit{\'e} {N}ancy {II} - {I}nstitut {N}ational {P}olytechnique de {L}orraine },
	booktitle = {{F}inite {F}ields and {A}pplications },
	publisher = {{AMS} },
	pages = {47-58 },
	journal = {{C}ontemporary {M}athematics },
	volume = {461 },
	note = {{G}.: {M}athematics of {C}omputing },
	audience = {internationale },
    year = {2008},
    URL = {http://hal.inria.fr/inria-00181029/en/},
    URL = {http://hal.inria.fr/inria-00181029/PDF/RR-6331.pdf},
}

%F inria-00181029, version 2
%0 Journal Article
%U http://hal.inria.fr/inria-00181029/en/
%2 INFO:INFO_DS
%T A Multi-level Blocking Distinct Degree Factorization Algorithm
%A Brent, Richard
%A Zimmermann, Paul
%A Brent, R.
%A Zimmermann, P.
%A Brent R. et al
%+ Mathematical Sciences Institute - Mathematical Sciences Institute - CACAO (Courbes, Algèbre, Calculs, Arithmétique des Ordinateurs) - INRIA Lorraine - LORIA - CNRS : UMR7503 - INRIA - Université Henri Poincaré - Nancy I - Université Nancy II - Institut National Polytechnique de Lorraine
%X 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).
%2 G.: Mathematics of Computing
%G Anglais
%J Contemporary Mathematics
%8 2008
%2 internationale
%I AMS
%2 Finite Fields and Applications
%V 461
%P 47-58
%K Amortized complexity; distinct degree factorization; finite field; irreducible trinomial; Mersenne exponent; polynomial factorization; primitive trinomial
%2 2007

A Multi-level Blocking Distinct Degree Factorization Algorithm

Richard Brent^a^, 1, Paul Zimmermann (

) ²

(2008)

Accès au texte intégral
PS
PDF

Contemporary Mathematics 461 (2008) 47-58

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

a –	Australian National University
1 :	Mathematical Sciences Institute
	Mathematical Sciences Institute
2 :	CACAO (Courbes, Algèbre, Calculs, Arithmétique des Ordinateurs) (INRIA Lorraine - LORIA)
	CNRS : UMR7503 – INRIA – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine

Domaine

Informatique/Algorithme et structure de données

Mots-clés : Amortized complexity – distinct degree factorization – finite field – irreducible trinomial – Mersenne exponent – polynomial factorization – primitive trinomial

Versions disponibles :

v1 (24-10-2007)

v2 (24-10-2007)


inria-00181029, version 2
http://hal.inria.fr/inria-00181029/fr/
oai:hal.inria.fr:inria-00181029_v2
Contributeur : Rapport De Recherche Inria <>
Soumis le : Mercredi 24 Octobre 2007, 11:17:28
Dernière modification le : Vendredi 14 Novembre 2008, 08:19:53