Factoring polynomials using fewer random bits

DOI10.1016/S0747-7171(08)80011-9MaRDI QIDQ912919zbMATH OpenFDO

Authors Eric Bach, Victor Shoup

Publication date 1990

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

Full work available at URL https://doi.org/10.1016/S0747-7171(08)80011-9

zbMATH Keywords

factorization of polynomials over finite fieldsprobabilistic algorithms

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 922258
• scientific article; zbMATH DE number 3880116
• Factoring Multivariate Polynomials over Large Finite Fields
• On the deterministic complexity of factoring polynomials over finite fields
• Subquadratic-time factoring of polynomials over finite fields

Cites work

• A New Algorithm for Factoring Polynomials Over Finite Fields
• Equations over finite fields. An elementary approach
• Factoring Polynomials Over Large Finite Fields
• scientific article; zbMATH DE number 3750146 (Why is no real title available?)
• Probabilistic Algorithms in Finite Fields
• The NP-completeness column: An ongoing guide

Cited in

(18)

• On the degrees of irreducible factors of polynomials over a finite field
• Primality testing with fewer random bits
• Polylog depth circuits for integer factoring and discrete logarithms
• On the security of modular exponentiation with application to the construction of pseudorandom generators
• Realistic analysis of some randomized algorithms
• scientific article; zbMATH DE number 1643928 (Why is no real title available?)
• Efficient Factoring Based on Partial Information
• Polynomial Factorization and Nonrandomness of Bits of Algebraic and Some Transcendental Numbers
• scientific article; zbMATH DE number 1542868 (Why is no real title available?)
• Generating random factored ideals in number fields
• Factoring a binary polynomial of degree over one million
• Distinct Degree Factorizations for Polynomials over a Finite Field
• scientific article; zbMATH DE number 1418483 (Why is no real title available?)
• On Bivariate Polynomial Factorization over Finite Fields
• Factoring polynomials over finite fields: A survey
• Bounds on tradeoffs between randomness and communication complexity
• Toward a theory of Pollard's rho method
• On the deterministic complexity of factoring polynomials over finite fields

This page was built for publication: Factoring polynomials using fewer random bits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q912919)