20.11.2008

In this paper we develop techniques that eliminate the need of the Generalized Riemann Hypothesis (GRH) from various (almost all) known results about deterministic polynomial factoring over finite fields. Our main result shows that given a polynomial f(x) of degree n over a finite field k, we can find in deterministic poly(n^{log n}, log |k|) time either a nontrivial factor of f(x) or a nontrivial automorphism of k[x]/(f(x)) of order n. This main tool leads to various new GRH-free results, most striking of which are:

1. Given a noncommutative algebra A of dimension n over a finite field k. There is a deterministic poly(n^{log n}, log |k|) time algorithm to find a zero divisor in A. This is the best known deterministic GRH-free result since Rónyai (1990) first studied the problem of finding zero divisors in finite algebras and showed that this problem has the same complexity as factoring polynomials over finite fields.
2. Given a positive integer r > 4 such that either 4|r or r has two distinct prime factors. There is a deterministic polynomial time algorithm to find a nontrivial factor of the r-th cyclotomic polynomial over a finite field. This is the best known deterministic GRH-free result since Evdokimov (1989) showed that cyclotomic polynomials can be factored over finite fields in deterministic polynomial time assuming GRH.