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.
Publication Year: 1987
Publication Date: 1987-10-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 17
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot