The Complete Analysis of a Polynomial Factorization Algorithm over Finite Fields

DOI10.1006/jagm.2001.1158zbMath1024.11079MaRDI QIDQ2746437

Xavier Gourdon, Daniel Panario, Philippe Flajolet

Publication date: 29 November 2001

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/13d25ea8543fd6b42d1d48c96ce98b204699bb3c

zbMATH Keywords

algorithm; finite fields; algebraic complexity; polynomial factorization algorithm

Mathematics Subject Classification ID

68W05: Nonnumerical algorithms

11Y16: Number-theoretic algorithms; complexity

11T06: Polynomials over finite fields

Related Items

Faster individual discrete logarithms in finite fields of composite extension degree, Computing in groups of Lie type, Estimating the number of roots of trinomials over finite fields, Enumeration of decomposable combinatorial structures with restricted patterns, Generating series for irreducible polynomials over finite fields, 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, Interval partitions and polynomial factorization, D?E?K=(1000)8, Analysis of Rabin's irreducibility test for polynomials over finite fields, Calculating the set of orders of elements in the finite linear groups