How to determine proportion of quadratic residues in elliptic curve group? I'm using a 'try and increment' method to hash to an Elliptic Curve point, explained below.

With security parameter $k$, EC equation $y^2 = x^3 + ax + b \mbox{ mod } q$, we have:

$ u = sha256(\mbox{message}) $

$\mbox{for } i = 0 \mbox{ to } k - 1, \mbox{ do:} $

$ \quad x = (u + i) \mbox{ mod } q$

$ \quad \mbox{if } x^3 + ax + b \mbox{ is a quadratic residue in } \mathbb{F}_q \mbox{ then }$

$ \quad \quad \mbox{ return } Q = (x, \sqrt{(x^3 + ax + b}) $

$ \mbox{return Q = nil, nil}$ 

With the EC group generator order $n$ and the field order $q$, I would imagine that the proportion of $x \in \mathbb{F}_q$ that do not result in quadratic residues is calculated $\frac{q - n}{q}$, which would be negligible, and hence require a very small security parameter, but I have read (for example here and here?) that the proportion is close to $\frac{1}{2}$, which would require use of a much larger $k$. This is also stated here, with $p$ as $q$ and $E$ as the EC group:


  An element $a$ of $\mathbb{F}_p$ is said to be a quadratic residue if there exists a nonzero $b \in \mathbb{F}_p$ such that $b^2 \equiv a \mbox{ mod }p$. In $\mathbb{F}_p$, there are exactly $(p-1)/2$ quadratic residues.
  
  Finding points $(x, y)$ on $E$ amounts to finding those values of $x$ such that $x^3 + ax + b$ is a quadratic residue modulo $p$; hence we might expect $x^3 + ax + b$ to be a square modulo $p$ about half of the time.


How large should the security parameter be?

How do I work the proportion of $x$ coordinates, knowing $n$ and $q$, that will not result in $x^3 + ax + b$ that is a quadratic residue?
I have read that the proportion is close to $\frac{1}{2}$


That is, in fact, correct; it is (for large $p$) extremely close to $\frac{1}{2}$; hence if you need your hashing process to fail with probability at most $2^{-64}$, you need your parameter $k \ge 64$


  I would imagine that the proportion of $x \in \mathbb{F}_q$ that do not result in quadratic residues is calculated $\frac{q - n}{q}$, which would be negligible


I believe that's where you're getting confused; you appear to be reasoning "we know there must be $n-1$ solutions to $y^2 = x^3 + ax + b$; there are $q$ possible values of $x$, and as $q \approx n$, then almost every possible value $x$ must be part of a solution.

The part that you're missing is that, for (almost) every value of $x$ which is a solution, there are two possible $y$ values that correspond to it; that is, if the pair $(x,y)$ is a solution to $y^2 = x^3 + ax + b$, then so is $(x, -y)$.  The sole exception to this is if $(x, 0)$ is a solution, there are at most 3 possible $x$ values that satisfy this; as 3 is tiny compared to $q$, we can ignore this for this analysis.

Because of this, there are approximately $(n-1)/2$ possible $x$ values that are possible solutions to the equation; that is, that result in a quadratic residue.  Because $n \approx q$, $(n - 1) / 2 / q \approx \frac{1}{2}$