ALCOMFT-TR-01-2
|
![ALCOM-FT](../Main/logo_160x41.gif)
|
Philippe Flajolet, Xavier Gourdon and Daniel Panario
The complete analysis of a polynomial factorization algorithm over finite fields
INRIA.
Work package 4.
January 2001.
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.
Postscript file: ALCOMFT-TR-01-2.ps.gz (178 kb).
System maintainer Gerth Stølting Brodal <gerth@cs.au.dk>