Subquadratic-time factoring of polynomials over finite fields

DOI10.1090/S0025-5718-98-00944-2zbMath0902.11053OpenAlexW1979366382MaRDI QIDQ4396457

Erich L. Kaltofen, Victor Shoup

Publication date: 14 June 1998

Published in: Mathematics of Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1090/s0025-5718-98-00944-2

zbMATH Keywords

finite fieldsprobabilistic algorithmsunivariate polynomialsfactoringsubquadratic complexitybaby step/giant step

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Number-theoretic algorithms; complexity (11Y16) Polynomials over finite fields (11T06) Finite fields (field-theoretic aspects) (12E20) Polynomials, factorization in commutative rings (13P05)

Related Items (46)

Preimages of \(p\)-linearized polynomials over \(\mathbb{F}_p\) ⋮ Constructing irreducible polynomials over finite fields ⋮ Factoring multivariate polynomials via partial differential equations ⋮ On design of circuits of logarithmic depth for inversion in finite fields ⋮ Deterministic distinct-degree factorization of polynomials over finite fields ⋮ Modular equations for hyperelliptic curves ⋮ Complexity of computation in finite fields ⋮ Factoring polynomials of the form \(f(x^n) \in \mathbb{F}_q [x\)] ⋮ 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 ⋮ Interval partitions and polynomial factorization ⋮ Fast algorithms for computing isogenies between ordinary elliptic curves in small characteristic ⋮ Computing cardinalities of -curve reductions over finite fields ⋮ Computing isomorphisms and embeddings of finite fields ⋮ Fast rectangular matrix multiplication and some applications ⋮ Fast computation of special resultants ⋮ Improving the algorithms of Berlekamp and Niederreiter for factoring polynomials over finite fields ⋮ A new faster algorithm for factoring skew polynomials over finite fields ⋮ A note on Gröbner bases and Berlekamp's algorithm ⋮ 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 ⋮ Factoring polynomials over finite fields: A survey ⋮ On the deterministic complexity of factoring polynomials ⋮ Fast algorithms for computing isogenies between elliptic curves ⋮ Deterministic polynomial factoring and association schemes ⋮ Explicit computation of isomorphisms between finite fields ⋮ Factoring Polynomials over Local Fields II ⋮ On constructing circuits for transforming the polynomial and normal bases of finite fields from one to the other ⋮ Factoring polynomials over local fields. ⋮ The black-box Niederreiter algorithm and its implementation over the binary field ⋮ Modular composition via factorization ⋮ Subquadratic-time algorithms for normal bases ⋮ Polynomial factorization over finite fields by computing Euler-Poincaré characteristics of Drinfeld modules ⋮ Sublinear Root Detection and New Hardness Results for Sparse Polynomials over Finite Fields ⋮ 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 ⋮ Trading GRH for algebra: Algorithms for factoring polynomials and related structures ⋮ Character sums and deterministic polynomial root finding in 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 ⋮ Constructive recognition of finite alternating and symmetric groups acting as matrix groups on their natural permutation modules. ⋮ Hensel lifting and bivariate polynomial factorisation over finite fields ⋮ Polynomial factorization over ${\mathbb F}_2$ ⋮ Finding roots in with the successive resultants algorithm

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the deterministic complexity of factoring polynomials over finite fields
• Matrix multiplication via arithmetic progressions
• The complexity of partial derivatives
• On the asymptotic complexity of rectangular matrix multiplication
• On fast multiplication of polynomials over arbitrary algebras
• Connections between the algorithms of Berlekamp and Niederreiter for factoring polynomials over \(\mathbb{F}_ q\)
• Factorization of polynomials over finite fields and characteristic sequences
• A new polynomial factorization algorithm and its implementation
• Computing Frobenius maps and factoring polynomials
• A new efficient factorization algorithm for polynomials over small finite fields
• Constructing normal bases in finite fields
• ON THE REDUCTIBILITY OF POLYNOMIALS OVER A FINITE FIELD
• Solving sparse linear equations over finite fields
• On the equivalence between Berlekamp's and Euclid's algorithms (Corresp.)
• Addition requirements for matrix and transposed matrix products
• Probabilistic Algorithms in Finite Fields
• Fast solution of toeplitz systems of equations and computation of Padé approximants
• On the Asymptotic Complexity of Matrix Multiplication
• A New Algorithm for Factoring Polynomials Over Finite Fields
• Taylor expansion of the accumulated rounding error
• Fast Algorithms for Manipulating Formal Power Series
• Nearly Optimal Algorithms for Canonical Matrix Forms
• Shift-register synthesis and BCH decoding
• Factoring Polynomials Over Large Finite Fields
• Fast construction of irreducible polynomials over finite fields

This page was built for publication: Subquadratic-time factoring of polynomials over finite fields