Given an integer polynomial, is there a small prime modulo which it has a root? I am looking at a paper by Pascal Koiran on the computational complexity of certifying the solvability of integer polynomial equations in several variables.  With the aid of some important theorems in algebraic geometry, Koiran reduces everything to the following univariate question:  Suppose that $f \in \mathbb{Z}[x]$ is a polynomial of degree $D$, and suppose that the $\ell_1$ norm of the coefficients (or the $\ell_\infty$ norm or anything in between; they are all equivalent for this purpose) is bounded by $R$.  Then it is a theorem of Lagarias, Odlyzko, and Weinberger that there is a prime
$$p = \exp(\text{poly}(\log D,\log R))$$
modulo which $f$ has a root.   The only catch is that they assume the generalized Riemann hypothesis.  It could be somewhat easier to prove that there is a prime power $q$ of this size and a root in $\mathbb{F}_q$.  That seems just as good in context, but in any case there is a prime $p$ that does the job.  This theorem is closely related to the "effective Chebotarev density theorem" of Lagarias, Odlyzko, et al.
Koiran needs an ample supply of such primes, but my question is about just finding one.  My hunch at the moment is that it is still an open problem to find a $p$ in the range given above unconditionally, in particular without GRH.  What is the current status of the question?  Could it be easier just to find a root than to establish full effective existential Chebotarev (rather than the density result), or are these equivalent results?  Is it viewed as difficult for the same reasons that GRH is difficult, or is GRH just one possible approach?
(By the way, you can get an interesting but inadequate bound unconditionally as follows:  $f(x)$ only attains a unit value at most $2D$ times, so choose some other $x$ with $|x| \le D$ and then pick a prime divisor of $f(x)$.)
 A: My paper
Chebyshev's method for number fields, J. de Théorie des Nombres de Bordeaux, 12 (2000) 81-85.
has some elementary bounds that can be made effective and also some references. Lagarias and Odlysko also have a version of their theorem without using GRH which is, as expected, much weaker than the version with GRH. I don't think this kind of problem is equivalent to GRH but is certainly much easier with it.
You mention obliquely that it might be enough for your purposes to have just prime powers. Depending on what you are after, it might be a much easier problem.
A: I am sorry to parasite this venerable question with something which is less an answer than another question, but is the theorem of Lagarias, Odlyzko, Weinberger you mention even proved under GRH ? (you ask if it is true without GRH).
I assume the paper of Pascal Koiran you refer to is this one. One finds indeed in section 5 the theorem you state, and the proof is essentially a
reduction to Lemma 3 of this article by Adleman and Odlyzko (and not by Lagarias and Odlyzko). Now there seems to be a problem in the proof of Lemma 3,
already in the first six lines of that proof. There a prime-counting function $S(x)$ (it counts the primes $p$ up to $x$ with multiplicity $1$ if $P$ has no root mod $p$, $0$ if $P$ has one root mod $p$, $-1$ if $P$ has 2 roots, etc.) and it is said without further justification that the bound $S(x) =  x^{1/2} (n \log x + \log D_P)$ (where $n$ is the degree of $P$ and $D_P$ its discriminant)
follows from Theorem 1.1 of Lagarias-Odlyzko (that is the famous effective Chebotarev under GRH). But I don't see to which Galois extension of number fields this theorem is applied. It has to be an extension of $\mathbb Q$ since the result is counting prime numbers, not prime ideals in some extension. Let $K$ denotes the field generated by a root of $P$, and $L$ its splitting field; then the theorem would give more or less what is stated if applied to $K/\mathbb Q$, but it can't be applied to that extension because in general it is not Galois. If instead
applied to $L/\mathbb Q$, which is Galois, then the degree $n$ has to be replaced
by the degree of $L$ which my be as large as $n!$, ruining the estimate.
So I am perplexed... Since there are at least two people here having thought on this kind of results, what am I missing?
