  Let $\tilde{f}(X)\in\mathbb{Z}[X]$ be a degree-$n$ polynomial such that
$f(X):=\tilde{f}(X)\bmod p$ factorizes into $n$ distinct linear factors over
$\mathbb{F}_p$. We study the problem of deterministically factoring $f(X)$ over
$\mathbb{F}_p$ given $\tilde{f}(X)$. Under the generalized Riemann hypothesis
(GRH), we give an improved deterministic algorithm that computes the complete
factorization of $f(X)$ in the case that the Galois group of $\tilde{f}(X)$ is
(permutation isomorphic to) a linear group $G\leq \mathrm{GL}(V)$ on the set
$S$ of roots of $\tilde{f}(X)$, where $V$ is a finite-dimensional vector space
over a finite field $\mathbb{F}$ and $S$ is identified with a subset of $V$. In
particular, when $|S|=|V|^{\Omega(1)}$, the algorithm runs in time polynomial
in $n^{\log n/(\log\log\log\log n)^{1/3}}$ and the size of the input, improving
Evdokimov's algorithm. Our result also applies to a general Galois group $G$
when combined with a recent algorithm of the author.
  To prove our main result, we introduce a family of objects called linear
$m$-schemes and reduce the problem of factoring $f(X)$ to a combinatorial
problem about these objects. We then apply techniques from additive
combinatorics to obtain an improved bound. Our techniques may be of independent
interest.
