Least prime for which a square-free integer is a non-residue

Suppose $a$ is a square-free integer and $\left(\frac{a}{p}\right)=1$ for the primes $p\leq k$. I'll call $a$ a quasi-square of order $k$. What I am interested in is the maximum value of $k$ in terms of $a$. For instance if $a$ is a prime which is $1$ mod $4$ then by quadratic reciprocity, we are really asking about the least non-residue mod $a$. So on the GRH we have $k=O((\log a)^2)$. But if we think about these symbols as coin flips, then I would suspect that after about $\log_2 a$ primes we should see a $-1$. So, since the $n$'th prime is about $n\log n$ one might guess that $k$ should be not much larger than $(\log_2 a)(\log\log a)$. Is this reasonable? Is there a well-known conjecture which suggests this? Does it hold on average?

Edit: As further justification, if we look at all $N\leq a\leq 2N$ then checking that $\left(\frac{a}{p}\right)=1$ rules out half of the integers in this range. So we should be run out of integers after about $\log_2 N$ primes. Of course the squares will remain, but that should be it.

• What you call a quasi-square is known in the literature as a pseudosquare. See, e.g., MR2282926 Wooding, Kjell; Williams, Hugh C. Doubly-focused enumeration of pseudosquares and pseudocubes. Algorithmic number theory, 208–221, Lecture Notes in Comput. Sci., 4076, Springer, Berlin, 2006. Jul 8 '15 at 0:41

For fixed $a$, the function $\big( \frac ap \big)$ defines a Dirichlet character (mod $4a$) (and often modulo a smaller modulus). More precisely, the Jacobi symbol $\big( \frac an \big)$ defines such an extension of the Legendre symbol to all odd $n$ (simply by multiplicativity), and that extension is a Dirichlet character.
So everything you know about least nonresidues of Dirichlet characters holds here: unconditionally there is a prime $p \ll a^{1/4\sqrt e+\epsilon}$ for which $\big( \frac ap \big)=-1$, and on GRH there is such a prime $p \ll \log^2 a$, as you've noted. I don't remember the heuristic for what the best possible bound should be, but the order of magnitude $\log a \cdot \log\log a$ or $\log a\cdot(\log\log a)^2$ seems plausible.