Uniform bound for the number primes $p$ s.t. a polynomial has a root modulo $p$ It is well known that for a given polynomial $f \in \mathbb{Z}[x]$  the number of primes $p$ s.t. $f$ has a root modulo $p$ is infinite. In fact, one can even write down a formula for the density of such primes (e.g. D. Berend, Y. Bilu "Polynomials with roots modulo every integer"). 
Now suppose that $f = \sum_{i=0}^d a_ix^i$ is irreducible, the degree $d$ is fixed and all $a_i \leq N^C$ for some constant $C$. Is it possible to prove the uniform bound (e.g. whith the constant depending only on $d$ and $C$ and $N$ large)
$$
\pi(N, f) = \Omega_{d, C}(\frac{N}{\log N}),
$$
where $\pi(N, f)$ means the number of primes less than $N$ s.t. $f$ has a root modulo $p$? 
The aforementioned paper cites a general density formula due to Lagarias and Odlyzko which seem to provide such a bound assuming GRH. It's of course highly desirable to drop this assumption.
 A: As Joel has pointed out this kind of question is delicate, and in fact even in the case $d=2$ no such result is known (for any fixed $C>0$).  To see this, suppose that $p$ is a prime for which the quadratic character $\chi(n) = (\frac{n}{p})$ has a Siegel zero.  That is there is a $\beta >1-\epsilon/\log p$ with $L(\beta,\chi)=0$.  Of course we expect that there is no such character, but this is an important open problem.  
Now by the proof of the prime number theorem in arithmetic progressions (see Davenport's book on multiplicative number theory; this is called Page's theorem I think) we have 
$$
\psi(N,\chi) \sim - \frac{N^{\beta}}{\beta}, 
$$ 
where $\psi(N,\chi) =\sum_{\ell \le N} \chi(\ell) \Lambda(\ell)$.  Thus 
$$ 
\sum_{\ell \le N, \chi(\ell)=1} \Lambda(\ell) \sim \frac 12 \Big( N- \frac{N^{\beta}}{\beta}\Big).
$$ 
If $N\le p^{1/C}$ then the RHS is $\ll \epsilon N$.  
To see the implication for your question, take $f(x)= x^2-p$ if $p\equiv 1\pmod 4$, and $f(x)=x^2+p$ if $p \equiv 3\pmod 4$.  Then by quadratic reciprocity, if $f(x)\equiv 0 \pmod{\ell}$ has a solution, then $(\frac{\ell}{p})=1$.  We have just shown that there are few primes $\ell$ below $N$ for which this happens.  
A: What you are looking for is probably the effective Chebotarev theorem that B. Winckler made completely explicit.
Since the paper is in French, here are the two main theorems.
Let $L/K$ be a Galois extension of number fields, $d_L$ the absolute discriminant of $L$, $n_L$ the degree of $L$ over $\mathbb{Q}$. Let $G$ be the Galois group of this extension and $C$ a subset of $G$ that is stable under conjugation. For all $x>1$, let $\pi_C(x)$ denote the number of prime ideals $\mathfrak{p}$ of $K$ of norm less than or equal to $x$, that do not ramify in $L$ and such that $\bigl(\frac{L/K}{\mathfrak{p}}\bigr)\in C$. Let $\beta$ denote the possible positive zero of $\zeta_L$ such that $0<1-\beta<\frac{1}{4\ln(d_L)}$.
Winckler proves the following unconditional result.

Theorem 1 (Effective Chebotarev theorem)
  For all $x\ge \exp\bigl(8n_L(\ln(150867d_L^{44/5}))^2\bigr)$,
  $$ \left|\pi_C(x)-\frac{|C|}{|G|}\mathrm{Li}(x)\right| \le \frac{|C|}{|G|}\mathrm{Li}(x^\beta) + C_0 x \exp\left(-\frac{1}{99}\sqrt{\frac{\ln(x)}{n_L}}\right)$$
  where $C_0 = 783846699796966 < 7.84\cdot 10^{14}$.

He also gives a conditional version.

Theorem 2
  Assume that the Riemann hypothesis holds for $\zeta_L$. Then for all $x\ge 2$,
  $$ \left|\pi_C(x)-\frac{|C|}{|G|}\mathrm{Li}(x)\right| \le \frac{|C|}{|G|}\sqrt{x}\left[\left(32+\frac{181}{\ln(x)}\right)\ln(d_L)+\left(28\ln(x)+330+\frac{1655}{\ln(x)}\right)n_L\right]\text{.}$$

A bound on the coefficients will give you a bound on the discriminant.
EDIT: as remarked by Joël, this does not solve the problem.
A: That's a very interesting question and I'd like to know the answer.
Unfortunately, I don't think the unconditional version of Effective Chebotarev will give you anything for your particular problem. The problem is not the chebotarev formula itself, which gives you the desired bound all right, but with the restriction on the range, which in your case gives you that the formula you want is true over a range that is empty. Indeed, the range of the formula for $\pi(f,x)$ is $$x>\exp(8 n_L \log(150867 d_L^{44/5})^2),$$ according to the paper quoted by Aurel (the explicit values of the constants don't matter here, so one could as well quote Lagarias-Odlyzko, or Serre's IHES paper on Chebotarev). Here $L$ is the splitting field of your polynomial $f$, $n_L$ is degree, $d_L$ its absolute discriminant. Now $n_L$ is bounded by $d!$ if $d$ is $deg(f)$ which you suppose constant, so that is no problem. However with your hypothesis on the size of coefficients the best bound that you can expect for $d_L$ is $d_L=O(N^{C'})$ where $C'$ is a constant depending of $C$ and $d$. This gives you a range of the form 
$x > \exp (c (\log N)^2))$ where $c$ is a constant (depending on $C$ and $d$). You want to apply the theorem for $x=N$, hence you have to assume that $N> exp(c (\log N)^2))$ which is true for at most finite many values of $N$ (possibly none). Hence the Chebotarev approach doesn't work.
(Edited:) For an other approach, besides trying and proving GRH, I would suggest looking at sieve methods. But I'm really no expert... 
