The complete analysis of a polynomial factorization algorithm over finite fields
As anticipated by the title, the authors analyze completely a polynomial factorization algorithm over finite fields. The algorithm they present and analyze operates in three stages: given a random polynomial \(P\) over a finite field, they first get a squarefree polynomial \(Q\) with the same irreducible factors as \(P\), then they factorize \(Q\) into polynomials whose irreducible factors all have the same degree and, finally, they factorize these factors. The use generating functions to describe certain parameters involved and singularity analysis to obtain asymptotic values.NEWLINENEWLINENEWLINEThis paper is the complete and revised version of an extended abstract presented at the ICALP'96 Conference [\textit{P. Flajolet}, \textit{X. Gourdon} and \textit{D. Panario}, Random polynomials and polynomial factorization, Lect. Notes Comput. Sci. 1099, 232-243 (1996; Zbl 0906.11057)].
- Asymptotics of subtracted singularities for generating functions with small singularities
- Smoothness test for polynomials defined over small characteristic finite fields
- The standard factorization of Lyndon words: an average point of view
- On the number of factorizations of polynomials over finite fields
- Permutation polynomials and factorization
- Faster initial splitting for small characteristic composite extension degree fields
- Factorization patterns on nonlinear families of univariate polynomials over a finite field
- Computing Frobenius maps and factoring polynomials
- Interval partitions and polynomial factorization
- D E K=(100)_8
- Analysis of Rabin's irreducibility test for polynomials over finite fields
- The space complexity analysis in the general number field sieve integer factorization
- Estimating the number of roots of trinomials over finite fields
- Calculating the set of orders of elements in the finite linear groups
- Faster individual discrete logarithms in finite fields of composite extension degree
- Computing in groups of Lie type
- Factoring polynomials over finite fields
- Univariate polynomial factorization over finite fields with large extension degree
- Enumeration of decomposable combinatorial structures with restricted patterns
- Generating series for irreducible polynomials over finite fields
This page was built for publication: The complete analysis of a polynomial factorization algorithm over finite fields
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2746437)
