The Complete Analysis of a Polynomial Factorization Algorithm over Finite Fields

Abstract : A unified treatment of parameters relevant to factoring polynomials over finite fields is given. The framework is based on generating functions for describing parameters of interest and on singularity analysis for extracting asymptotic values. An outcome is a complete analysis of the standard polynomial factorization chain that is based on elimination of repeated factors, distinct degree factorization, and equal degree separation. Several basic statistics on polynomials over finite fields are obtained in the course of the analysis.
Document type :
Reports
Complete list of metadatas

https://hal.inria.fr/inria-00073319
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 12:31:43 PM
Last modification on : Friday, May 25, 2018 - 12:02:02 PM
Long-term archiving on : Thursday, March 24, 2011 - 12:40:42 PM

Identifiers

  • HAL Id : inria-00073319, version 1

Collections

Citation

Philippe Flajolet, Xavier Gourdon, Daniel Panario. The Complete Analysis of a Polynomial Factorization Algorithm over Finite Fields. [Research Report] RR-3370, INRIA. 1998. ⟨inria-00073319⟩

Share

Metrics

Record views

115

Files downloads

218