The complete analysis of a polynomial factorization algorithm over finite fields

DOI10.1006/JAGM.2001.1158MaRDI QIDQ2746437zbMATH OpenOpenAlexFDO

Authors X. 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

algebraic complexityalgorithmfinite fieldspolynomial factorization algorithm

Mathematics Subject Classification ID

Polynomials over finite fields (11T06) Number-theoretic algorithms; complexity (11Y16) Nonnumerical algorithms (68W05)

Recommendations

• On a New Factorization Algorithm for Polynomials Over Finite Fields
• Factoring polynomials over arbitrary finite fields
• A New Algorithm for Factoring Polynomials Over Finite Fields
• Computing Frobenius maps and factoring polynomials
• Factoring polynomials over finite fields: A survey

Cited in

(20)

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