This question is inspired by an old question of Greg Kuperberg, about how small is the first prime $p$ which makes a given monic polynomial $P$ with integral coefficient have a (simple) root modulo $p$. Now "small" makes sense w.r.t. something, some notion of size of polynomials. In Greg's question the size is measured by the degree $n$ of $P$ and the $L^1$-norm (or $L^\infty$-norm of its coeffcients, but I will rather use as measure of size the degree $d$ and the product $M$ of the primes $p$ dividing the discriminant of $P$ (in short $M$ is the *radical of the discriminant* of $P$): this is essentially equivalent to Greg's notions but more in line with the literature on the subject.

This being said the result of Weinberger alluded to by Greg is, under GRH, the following:

Theorem : For any $\epsilon>0$, and for any monic polynomial $P$ with integral coefficients, of degree $n$ and radical of discriminant $M$, there is always a prime $p = O(n^{2+\epsilon} (\log M)^{2+\epsilon})$ not dividing $M$ such that $P$ mod $p$ has a root (necessarily simple).

The theorem is proven in this paper of Weinberger (though not stated this way -- near the end of the argument the author stops calculating and just says that the bound is polynomial. I hope my calculation of his bound is correct), and the proof is surprisingly simple. In fact it is so simple that it puzzles me, avoiding all the complications of Lagarias-Odlyzko's effective Chebotarev's theorem (to which the result is closely related, as Greg says) by working with the field $K=\mathbb Q[X]/(P(x))$ even if it is nor Galois (assuming $P$ is irreducible, which one can of course do) rather than its normal closure $L$, which is Galois but can have degree as large as $n!$, which is bad for the polynomial estimate.

To understand better the scope of the method, I ask the following, kind of opposite, question:

Is it true (under GRH or any standard conjecture) that for any monic irreducible polynomial $P$ with integral coefficients, of degree $n$ and radical of discriminant $M$, there is always a prime $p$ not dividing $M$ less than a fixed polynomial in $n$ and $\log M$, such that $P$ mod $p$ has no simple roots ?

(or at least less than a function of $n$ and $\log M$, polynomial in $n$ - I don't really care about the dependence in $M$)?