[math-fun] "smallest" degree n irreducible polynomial over GF(p)

Let $n = 2^{e_0} q_1^{e_1} \cdots q_i^{e_i}$ be the prime factorization of $n$. Let $p$ be an odd prime. Is it true that $\exists k$ such that $x^n+k$ is irreducible over GF($p$) $\iff$ $(2^{min(e_0,2)} q_1 \cdots q_i) | (p-1)$ ? Are there similar criteria for "larger" polynomials such as $x^n + k_1 x + k_0$ ?