Factoring polynomials using fewer random bits

DOI10.1016/S0747-7171(08)80011-9zbMath0699.12027MaRDI QIDQ912919

Victor Shoup, Eric Bach

Publication date: 1990

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

zbMATH Keywords

factorization of polynomials over finite fieldsprobabilistic algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Polynomials over finite fields (11T06) Software, source code, etc. for problems pertaining to field theory (12-04)

Related Items

On Bivariate Polynomial Factorization over Finite Fields ⋮ On the deterministic complexity of factoring polynomials over finite fields ⋮ Bounds on tradeoffs between randomness and communication complexity ⋮ Distinct Degree Factorizations for Polynomials over a Finite Field ⋮ Factoring polynomials over finite fields: A survey ⋮ On the degrees of irreducible factors of polynomials over a finite field ⋮ Primality testing with fewer random bits

Cites Work

• Unnamed Item
• Equations over finite fields. An elementary approach
• Probabilistic Algorithms in Finite Fields
• A New Algorithm for Factoring Polynomials Over Finite Fields
• Factoring Polynomials Over Large Finite Fields
• The NP-completeness column: An ongoing guide