  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.
