Subquadratic-time factoring of polynomials over finite fields
Efficiently factoring univariate polynomials over finite fields is a very important step in the solution of many discrete problems. The first random polynomial-time algorithm for such a factorization was given by \textit{E. R. Berlekamp} [Math. Comput. 24(1970), 713-735 (1971; Zbl 0247.12014)]. About a decade later a very different approach was suggested by \textit{D. G. Cantor} and \textit{H. Zassenhaus} [Math. Comput. 36, 587-592 (1981; Zbl 0493.12024)]. In this latter approach the algorithm starts with a polynomial assumed to be square-free, separates the irreducible factors of distinct degrees, and then completely factors each of the resulting factors. A number of other researchers, including both authors, have improved these techniques over the years. In the paper under review the authors use the basic Cantor/Zassenhaus strategy to develop a probabilistic approach that factors a polynomial of degree \(n\) over the finite field \(F_q\) (\(q\) being held constant) in \( O(n^{1.815})\) time. This bound is proven by using the result of \textit{D. Coppersmith} and \textit{S. Winograd} [J. Symb. Comput. 9, 251-280 (1990; Zbl 0702.65046)] that one can multiply two \(n \times n\) matrices using only \(O(n^\omega)\) arithmetic operations, where \(\omega < 2.375477\). The main technical contribution is a subquadratic distinct-degree factorization algorithm based on the so-called baby step/giant step strategy. The authors also develop a subquadratic algorithm for finding a normal basis of \(F_{q^n}\) over its subfield \(F_q\). Since the algorithms discussed rely on fast multiplication of large matrices, as stated they are not particularly practical. However, the techniques can be adapted to give a practical algorithm that seems to factor larger polynomials (in a reasonable amount of time and space) than previously possible. To achieve the subquadratic running time, randomization is of course used. It remains an open problem to find a subquadratic deterministic algorithm.
- scientific article; zbMATH DE number 1263216
- scientific article; zbMATH DE number 3880116
- Fast polynomial factorization and modular composition
- Computing Frobenius maps and factoring polynomials
- Factoring polynomials over finite fields: A survey
- scientific article; zbMATH DE number 691468
- Factorization of Multivariate Polynomials Over Finite Fields
- A generalisation of the Cantor-Zassenhaus algorithm
- Deterministic analysis of aleatoric methods of polynomial factorization over finite fields
- scientific article; zbMATH DE number 1273636
- 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
- Addition requirements for matrix and transposed matrix products
- Computing Frobenius maps and factoring polynomials
- Connections between the algorithms of Berlekamp and Niederreiter for factoring polynomials over \(\mathbb{F}_ q\)
- Constructing normal bases in finite fields
- Factoring Polynomials Over Large Finite Fields
- Factorization of polynomials over finite fields and characteristic sequences
- Fast Algorithms for Manipulating Formal Power Series
- Fast construction of irreducible polynomials over finite fields
- Fast solution of toeplitz systems of equations and computation of Padé approximants
- scientific article; zbMATH DE number 3750146 (Why is no real title available?)
- scientific article; zbMATH DE number 3511563 (Why is no real title available?)
- scientific article; zbMATH DE number 1253982 (Why is no real title available?)
- scientific article; zbMATH DE number 1254016 (Why is no real title available?)
- scientific article; zbMATH DE number 1263398 (Why is no real title available?)
- scientific article; zbMATH DE number 976329 (Why is no real title available?)
- scientific article; zbMATH DE number 922674 (Why is no real title available?)
- scientific article; zbMATH DE number 3362881 (Why is no real title available?)
- Matrix multiplication via arithmetic progressions
- Nearly Optimal Algorithms for Canonical Matrix Forms
- On fast multiplication of polynomials over arbitrary algebras
- On the Asymptotic Complexity of Matrix Multiplication
- On the asymptotic complexity of rectangular matrix multiplication
- On the deterministic complexity of factoring polynomials over finite fields
- On the equivalence between Berlekamp's and Euclid's algorithms (Corresp.)
- ON THE REDUCTIBILITY OF POLYNOMIALS OVER A FINITE FIELD
- Probabilistic Algorithms in Finite Fields
- Shift-register synthesis and BCH decoding
- Solving sparse linear equations over finite fields
- Taylor expansion of the accumulated rounding error
- The complexity of partial derivatives
- Algorithm for calculating the roots of polynomials with coefficients in the ring of polynomials over an arbitrary integral domain
- Factoring polynomials over arbitrary finite fields
- Algorithms for exponentiation in finite fields
- Challenges of symbolic computation: My favorite open problems. With an additional open problem by Robert M. Corless and David J. Jeffrey
- Factoring polynomials of the form \(f(x^n) \in \mathbb{F}_q [x]\)
- Polynomial factorization over finite fields by computing Euler-Poincaré characteristics of Drinfeld modules
- Drinfeld modules with complex multiplication, Hasse invariants and factoring polynomials over finite fields
- Fast computation of generic bivariate resultants
- Deterministic polynomial factoring over finite fields: a uniform approach via \(\mathcal{P}\)-schemes
- Subexponential-time computation of isolated primary components of a polynomial ideal
- Subquadratic-time algorithms for normal bases
- Preimages of \(p\)-linearized polynomials over \(\mathbb{F}_p\)
- Interval partitions and polynomial factorization
- Fast algorithms for computing isogenies between ordinary elliptic curves in small characteristic
- Fast computation of special resultants
- Improving the algorithms of Berlekamp and Niederreiter for factoring polynomials over finite fields
- A note on Gröbner bases and Berlekamp's algorithm
- Constructive recognition of finite alternating and symmetric groups acting as matrix groups on their natural permutation modules.
- Deterministic distinct-degree factorization of polynomials over finite fields
- Sublinear root detection and new hardness results for sparse polynomials over finite fields
- Finding roots in \(\mathbb F_{p^n}\) with the successive resultants algorithm
- Constructing irreducible polynomials over finite fields
- Computing cardinalities of \(\mathbb{Q}\)-curve reductions over finite fields
- Polynomial Time Attack on Wild McEliece Over Quadratic Extensions
- Trading GRH for algebra: algorithms for factoring polynomials and related structures
- Hensel lifting and bivariate polynomial factorisation over finite fields
- Polynomial factorization over ${\mathbb F}_2$
- On design of circuits of logarithmic depth for inversion in finite fields
- Subquadratic Space Complexity Multiplication over Binary Fields with Dickson Polynomial Representation
- Fast algorithms for computing isogenies between elliptic curves
- Subquadratic Polynomial Multiplication over GF(2 m ) Using Trinomial Bases and Chinese Remaindering
- Complexity of computation in finite fields
- A subquadratic algorithm for minimum palindromic factorization
- scientific article; zbMATH DE number 1253982 (Why is no real title available?)
- scientific article; zbMATH DE number 1263216 (Why is no real title available?)
- The black-box Niederreiter algorithm and its implementation over the binary field
- Algebraic problems equivalent to beating exponent 3/2 for polynomial factorization over finite fields
- Computing isomorphisms and embeddings of finite fields
- Factoring multivariate polynomials via partial differential equations
- Modular equations for hyperelliptic curves
- Factoring polynomials over local fields. II
- A new faster algorithm for factoring skew polynomials over finite fields
- Deterministic polynomial factoring and association schemes
- Practical polynomial factoring in polynomial time
- On the Selection of Polynomials for the DLP Quasi-Polynomial Time Algorithm for Finite Fields of Small Characteristic
- Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier–Manin Operator
- On constructing circuits for transforming the polynomial and normal bases of finite fields from one to the other
- Character sums and deterministic polynomial root finding in finite fields
- Factoring polynomials over finite fields: A survey
- On the deterministic complexity of factoring polynomials
- Factoring polynomials over local fields.
- Skew differential Goppa codes and their application to McEliece cryptosystem
- Elimination ideal and bivariate resultant over finite fields
- Univariate polynomial factorization over finite fields with large extension degree
- Bivariate polynomial reduction and elimination ideal over finite fields
- A univariate attack against the limited-data instance of Ciminion
- First-degree prime ideals of composite extensions
- Explicit computation of isomorphisms between finite fields
- Factoring sparse polynomials fast
- Polynomial XL: a variant of the XL algorithm using Macaulay matrices over polynomial rings
- Faster modular composition
- Encounters in symbolic computation: ideas for the ages
- Plane curve germs and contact factorization
- Modular composition via factorization
- Improved cryptanalysis of SNOVA by solving multi-homogeneous systems via matrix transformations
- A degree bound for the c-boomerang uniformity
- Factoring polynomials using fewer random bits
- Fast rectangular matrix multiplication and some applications
This page was built for publication: Subquadratic-time factoring of polynomials over finite fields
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4396457)
