On the deterministic complexity of factoring polynomials over finite fields

DOI10.1016/0020-0190(90)90195-4zbMath0696.68072OpenAlexW2020306558MaRDI QIDQ911294

Victor Shoup

Publication date: 1990

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://digital.library.wisc.edu/1793/59000

zbMATH Keywords

factorizationirreducible polynomials

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Polynomials over finite fields (11T06)

Related Items (30)

Using partial smoothness of 𝑝-1 for factoring polynomials modulo 𝑝 ⋮ Computing Frobenius maps and factoring polynomials ⋮ Sieve algorithms for perfect power testing ⋮ Deterministic root finding over finite fields using Graeffe transforms ⋮ Finding elliptic curves with a subgroup of prescribed size ⋮ On isomorphism testing of groups with normal Hall subgroups ⋮ Constructing normal bases in finite fields ⋮ Algorithms in Algebraic Number Theory ⋮ Root repulsion and faster solving for very sparse polynomials over \(p\)-adic fields ⋮ Univariate polynomial factorization over finite fields ⋮ Homomorphic polynomial public key encapsulation over two hidden rings for quantum-safe key encapsulation ⋮ Algebraic algorithms for variants of subset sum ⋮ On Bivariate Polynomial Factorization over Finite Fields ⋮ Unnamed Item ⋮ On the computation of the HNF of a module over the ring of integers of a number field ⋮ Calculating the set of orders of elements in the finite linear groups ⋮ Smoothness and factoring polynomials over finite fields ⋮ Computational problems in the theory of finite fields ⋮ Distinct Degree Factorizations for Polynomials over a Finite Field ⋮ Deterministic polynomial factoring over finite fields: a uniform approach via \(\mathcal{P}\)-schemes ⋮ Factoring polynomials over finite fields: A survey ⋮ Searching for Primitive Roots in Finite Fields ⋮ Subquadratic-time factoring of polynomials over finite fields ⋮ Faster polynomial multiplication over finite fields using cyclotomic coefficient rings ⋮ Unnamed Item ⋮ On a New Factorization Algorithm for Polynomials Over Finite Fields ⋮ Factoring polynomials over arbitrary finite fields ⋮ Character sums and deterministic polynomial root finding in finite fields ⋮ On the degrees of irreducible factors of polynomials over a finite field ⋮ A Generalised Successive Resultants Algorithm

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Factoring polynomials using fewer random bits
• Factoring polynomials and primitive elements for special primes
• Equations over finite fields. An elementary approach
• Analysis of a simple factorization algorithm
• Fast multiplication of polynomials over fields of characteristic 2
• Improving an algorithm for factoring polynomials over a finite field and constructing large irreducible polynomials
• Probabilistic Algorithms in Finite Fields
• A New Algorithm for Factoring Polynomials Over Finite Fields
• Factoring Polynomials Over Large Finite Fields

This page was built for publication: On the deterministic complexity of factoring polynomials over finite fields