The Complete Analysis of a Polynomial Factorization Algorithm over Finite Fields

Philippe Flajolet 1 Xavier Gourdon 1 Daniel Panario
1 ALGO - Algorithms
Inria Paris-Rocquencourt
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.
Type de document :
Rapport
[Research Report] RR-3370, INRIA. 1998
Liste complète des métadonnées

https://hal.inria.fr/inria-00073319
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 12:31:43
Dernière modification le : samedi 17 septembre 2016 - 01:35:39
Document(s) archivé(s) le : jeudi 24 mars 2011 - 12:40:42

Fichiers

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

85

Téléchargements de fichiers

140