Using partial smoothness of $p-1$ for factoring polynomials modulo $p$

Abstract:

Let an arbitrarily small positive constant $\delta$ less than $1$ and a polynomial $f$ with integer coefficients be fixed. We prove unconditionally that $f$ modulo $p$ can be completely factored in deterministic polynomial time if $p-1$ has a $(\ln p)^{O(1)}$-smooth divisor exceeding $p^\delta$. We also address the issue of factoring $f$ modulo $p$ over finite extensions of the prime field $\mathbb {F}_p$ and show that $p-1$ can be replaced by $p^k-1$ ($k\in \mathbb {N}$) for explicit classes of primes $p$.