Improving the algorithms of Berlekamp and Niederreiter for factoring polynomials over finite fields

DOI10.1016/J.JSC.2006.02.007MaRDI QIDQ2457415zbMATH OpenOpenAlexFDO

Authors Giulio Genovese

Publication date 23 October 2007

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jsc.2006.02.007

zbMATH Keywords

Berlekamp algorithmDeterministic algorithmsfinite fieldsNiederreiter algorithmpolynomial factorization

Mathematics Subject Classification ID

Polynomials over finite fields (11T06) Number-theoretic algorithms; complexity (11Y16) Polynomials, factorization in commutative rings (13P05) Numerical computation of solutions to single equations (65H05) Symbolic computation and algebraic computation (68W30)

Recommendations

• On a New Factorization Algorithm for Polynomials Over Finite Fields
• A New Algorithm for Factoring Polynomials Over Finite Fields
• scientific article; zbMATH DE number 691468
• scientific article; zbMATH DE number 1594303
• scientific article; zbMATH DE number 691482
• A new efficient factorization algorithm for polynomials over small finite fields
• Polynomial factorization algorithms over number fields
• An efficient algorithm for factoring polynomials over algebraic extension field
• scientific article; zbMATH DE number 953213
• scientific article; zbMATH DE number 1253982

Cites work

• A New Algorithm for Factoring Polynomials Over Finite Fields
• A new efficient factorization algorithm for polynomials over small finite fields
• A new polynomial factorization algorithm and its implementation
• An introduction to pseudo-linear algebra
• Computing Frobenius maps and factoring polynomials
• Connections between the algorithms of Berlekamp and Niederreiter for factoring polynomials over \(\mathbb{F}_ q\)
• Efficient computation of zero-dimensional Gröbner bases by change of ordering
• Factoring Polynomials Over Large Finite Fields
• scientific article; zbMATH DE number 1206418 (Why is no real title available?)
• scientific article; zbMATH DE number 691482 (Why is no real title available?)
• scientific article; zbMATH DE number 3265895 (Why is no real title available?)
• Subquadratic-time factoring of polynomials over finite fields

Cited in

(6)

• A verified implementation of the Berlekamp-Zassenhaus factorization algorithm
• \textsc{Ciminion}: symmetric encryption based on Toffoli-gates over large finite fields
• Improving the Berlekamp algorithm for binomials \(x^{n}-a\)
• scientific article; zbMATH DE number 691482 (Why is no real title available?)
• On a New Factorization Algorithm for Polynomials Over Finite Fields
• scientific article; zbMATH DE number 1092441 (Why is no real title available?)

Describes a project that uses

Uses Software

• NTL

This page was built for publication: Improving the algorithms of Berlekamp and Niederreiter for factoring polynomials over finite fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2457415)