On the deterministic complexity of factoring polynomials
The problem considered is factoring polynomials over finite fields. In 1970 Berlekamp published an algorithm solving this problem in probabilistic polynomial time. It is still an open question whether there exists a deterministic polynomial time algorithm, even under the extended Riemann hypothesis (ERH). Since 1992, several authors have given, under ERH, efficient algorithms for special classes of polynomials or for polynomials over special fields. This paper continues this line of research for deterministic polynomial time algorithms under GRH. The paper contains such a result which applies to polynomials which do not satisfy a very stringent condition. The other one conjectures that the class of polynomials satisfying this condition is empty.
- Smoothness and factoring polynomials over finite fields
- scientific article; zbMATH DE number 799779
- Factoring polynomials over finite fields
- Trading GRH for algebra: algorithms for factoring polynomials and related structures
- On the deterministic complexity of factoring polynomials over finite fields
- A Deterministic Algorithm for Factorizing Polynomials of Fq [X]
- Algorithmic number theory. 1st international symposium, ANTS-I, Ithaca, NY, USA, May 6-9, 1994. Proceedings
- An improved algorithm for computing logarithms over<tex>GF(p)</tex>and its cryptographic significance (Corresp.)
- Comments on search procedures for primitive roots
- Computing Frobenius maps and factoring polynomials
- Factoring polynomials and primitive elements for special primes
- Factoring polynomials modulo special primes
- Factoring polynomials over finite fields
- Factoring Polynomials Over Large Finite Fields
- Factoring polynomials over special finite fields
- Galois Groups and Factoring Polynomials over Finite Fields
- Generalized riemann hypothesis and factoring polynomials over finite fields
- scientific article; zbMATH DE number 3167868 (Why is no real title available?)
- scientific article; zbMATH DE number 4152517 (Why is no real title available?)
- scientific article; zbMATH DE number 4065121 (Why is no real title available?)
- scientific article; zbMATH DE number 3237990 (Why is no real title available?)
- scientific article; zbMATH DE number 3265895 (Why is no real title available?)
- On Hensel factorization. I
- On the Efficiency of Algorithms for Polynomial Factoring
- Subquadratic-time factoring of polynomials over finite fields
- Smoothness and factoring polynomials over finite fields
- Deterministic analysis of aleatoric methods of polynomial factorization over finite fields
- Deterministic polynomial factoring over finite fields: a uniform approach via \(\mathcal{P}\)-schemes
- Integers and polynomials: comparing the close cousins \(\mathbb Z\) and \(\mathbb F_q[x]\)
- Schemes for deterministic polynomial factoring
- Deterministic root finding over finite fields using Graeffe transforms
- Trading GRH for algebra: algorithms for factoring polynomials and related structures
- scientific article; zbMATH DE number 994059 (Why is no real title available?)
- scientific article; zbMATH DE number 799779 (Why is no real title available?)
- Factoring polynomials over finite fields using balance test
- On the Complexity of the Montes Ideal Factorization Algorithm
- scientific article; zbMATH DE number 7559413 (Why is no real title available?)
- Boshernitzan’s condition, factor complexity, and an application
- Deterministic polynomial factoring and association schemes
- Practical polynomial factoring in polynomial time
- A generalized successive resultants algorithm
- Factoring polynomials over finite fields: A survey
- Counting roots for polynomials modulo prime powers
- Efficient algorithms for finite \(\mathbb{Z}\)-algebras
- On the deterministic complexity of factoring polynomials over finite fields
- An explicit separation of relativised random polynomial time and relativised deterministic polynomial time
This page was built for publication: On the deterministic complexity of factoring polynomials
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5928878)
