Factoring polynomials over finite fields
- 1 October 1987
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 132-137
- https://doi.org/10.1109/sfcs.1987.25
Abstract
We propose a new deterministic method of factoring polynomials over finite fields. Assuming the Generalized Riemann Hypothesis (GRH), we obtain, in polynomial time, the factorization of any polynomial with a bounded number of irreducible factors. Other consequences include a polynomial time algorithm to find a nontrivial factor of any completely splitting even degree polynomial when a quadratic nonresidue in the field is given.Keywords
This publication has 5 references indexed in Scilit:
- Riemann hypothesis and finding roots over finite fieldsPublished by Association for Computing Machinery (ACM) ,1985
- Factorization of polynomials over finite fields and factorization of primes in algebraic number fieldsPublished by Association for Computing Machinery (ACM) ,1984
- Multilinear AlgebraPublished by Springer Nature ,1978
- On taking roots in finite fieldsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1977
- Factoring Polynomials Over Large Finite FieldsMathematics of Computation, 1970