Effective Chebotarev Density Let $K$ be a number field, and $p$ be a rational prime. Then the Chebotarev Density Theorem implies we can find primes $v$ and $w$ of $K$ of degree 1 which are split and nonsplit respectively in $K[\sqrt{p}]$. What is the best known effective (upper) bound for the norms of the least such primes (not assuming GRH)? In particular, is there a bound which is asymptotically strictly less than $\sqrt{p}$ (times a constant coming from the field $K$)?
EDIT: I'd like to clarify, in response to the comments below. The situation I'm wondering about is when we fix K, and let p vary. So when K is a cyclotomic field (adjoin, say, the qth root of unity for a prime q), I'm asking about the least prime which is a quadratic nonresidue (resp. residue) mod p, which is 1 mod some fixed prime q, and I'm hoping that there is a bound of the form $\sqrt{p}$ times (something in terms of q). Under GRH this is true --- in fact under GRH, we can get a bound of the shape $(\log p)^2$ times constants coming from K.
 A: The paper:
J. C. Lagarias, H. L. Montgomery and A. M. Odlyzko, A bound for the least prime ideal in the Chebotarev density theorem, Invent. Math. 54 (1979) 271-296 
gives a bound of the form $c \sqrt p$ for some unspecified $c$. 
My paper with J. Vaaler:
The least nonsplit prime in Galois extensions of Q, J. Number Theory, 85 (2000), 320-335.
gives an effective constant (when $K=\mathbb Q$, but the argument should generalize). Actually, the quadratic field case of our argument is already in Gauss. Our paper has a bunch of other references, including what you can get with GRH. Improving the square root bound without GRH is a big open problem.
The paper also gives me Erdos number 2 :-) 
EDIT: As in GH's answer, the natural quantity for the bounds is the discriminant, so $p$ needs to be replaced by $p^n, n=[K:\mathbb Q]$, in the case of $K(\sqrt p)$. Here is an example where this will make a big difference. Take $K$ to be the cyclotomic field of $p$-th roots of unity where $p \equiv 3 \mod 4$, so the quadratic extension is non trivial. The OP asks for degree one primes, these are primes above rational primes $l \equiv 1 \mod p$, so they have norm $l > p$ and you can't expect a $\sqrt p$ bound.
A: I assume $\sqrt{p}$ is not contained in $K$, then the bound you are looking for is available. 
Let $\chi$ be the ray class character attached to the quadratic extension $K(\sqrt{p})/K$, then the $L$-function $L(s,\chi)$ has conductor essentially $p$. By a recent result of Venkatesh (Theorem 6.1 in Annals of Math. 172 (2010), 989-1094) we have the subconvex bound $L(s,\chi)\ll |s|^N p^{1/4-1/200}$ on the criticial line $\Re s=1/2$, where $N>0$ is a constant. It follows, by a simple Mellin transformation technique, that for any fixed smooth function $V:(0,\infty)\to\mathbb{C}$ of compact support we have
$$\sum_{\mathfrak{m}\subset\mathcal{O}_K}\chi(\mathfrak{m})V(N\mathfrak{m}/X)\ll p^{1/4-1/200} X^{1/2}.$$
Therefore the absolute value of the left hand side is smaller than $X$ for some $X\gg p^{1/2-1/100}$, where the implied constant depends only on $K$ and $V$. This implies that $\chi$ takes both values $\pm 1$ on prime ideals with norm $\ll p^{1/2-1/100}$.
Perhaps one can complement this with Vinogradov's trick, see Corollary 9.19 in Montgomery-Vaughan: Multiplicative number theory I.
EDIT: As the OP pointed out, all the $p$'s above should be replaced by $p^{(K:\mathbb{Q})}$.
