Factoring polynomials using fewer random bits
Let F be a field of q elements, \(q=p^ n\), p a prime. Two new probabilistic algorithms for factoring polynomials over F that make efficient use of random bits are presented. The first algorithm, based on an algorithm of Berlekamp, factors a polynomial of degree d using \(d \log_ 2 p\) random bits and produces in polynomial time a complete factorization with a probability of failure of no more \(1/p^{(1- \epsilon)d/2},\) \(0<\epsilon <1\). The second algorithm is based on a method of Cantor and Zassenhaus. It also uses \(d \log_ 2 p\) random bits and fails to produce a complete factorization with probability of failure no more than \(1/q^{(1-\epsilon)d/4}\).
- 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
- 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)
