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 subexponential
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 over a finite field, there is a deterministic subexponential time algorithm to find
a zero divisor.

(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.

In this paper, following the seminal work of Lenstra (1991)
on constructing isomorphisms between finite fields,
we further generalize classical Galois
theory
constructs like cyclotomic extensions, Kummer extensions,
Teichmuller subgroups, to the case of commutative
semisimple algebras with automorphisms. These
generalized constructs help eliminate the dependence on GRH.