  We prove, without recourse to the Extended Riemann Hypothesis, that the
projection modulo $p$ of any prefixed polynomial with integer coefficients can
be completely factored in deterministic polynomial time if $p-1$ has a $(\ln
p)^{O(1)}$-smooth divisor exceeding $(p-1)^{{1/2}+\delta}$ for some arbitrary
small $\delta$. We also address the issue of computing roots modulo $p$ in
deterministic time.
