In this work we relate the deterministic
complexity of factoring polynomials (over
finite
fields) to certain combinatorial objects we
call
m-schemes. We extend the known conditional
deterministic subexponential time polynomial
factoring algorithm for finite fields to get an
underlying m-scheme. We demonstrate how the
properties of m-schemes relate to improvements
in
the deterministic complexity of factoring
polynomials over finite fields assuming the
generalized Riemann Hypothesis (GRH). In
particular, we give the first deterministic
polynomial time algorithm (assuming GRH) to
find a nontrivial factor of a polynomial of
prime
degree n where (n-1) is a smooth number.