# 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}$

• Oh of course, yep I was completely missing that y^2 = ( - y )^2, thank you!!! Dec 1 '16 at 15:16
• This may or may not be interesting. There are precisely $(n-n_0-1)/2+n_0$ possible $x$-values, where $n_0$ is the number of points where the $y$-coordinate is zero. It may not be obvious that this is an integer, but noting that points have $y$-coordinate 0 if and only if they have order 2, it follows immediately. Dec 1 '16 at 16:20

The answer above is the best explanation but just for reference, the formal proof I was looking for was found quite easily once I realised my question applied to odd-ordered finite fields too, and is as follows, taken from this document from ETH Zurich.

The theorem is:

Let $$q$$ be an odd prime power, and $$a \in \mathbb{F}_q$$, then:

• $$a \in QR(q), \iff a^{(q-1)/2} = 1$$
• $$a \in QNR(q), \iff a^{(q-1)/2} = -1$$
• $$| QNR(q) | = \frac{q-1}{2} = | QR(q) |$$

And the essence of the proof is:

1: A polynomial of degree $$d$$, with coefficients from a field $$R$$, can have at most $$d$$ roots in $$R$$. 2: Lagrange's Theorem: In a finite group $$G$$, $$x^{|G|} = 1$$ for any $$x \in G$$.

On the one hand, by Fact 1, the polynomial $$x^{q-1} -1 = 0$$ cannot have more than $$q - 1$$ roots by Legrange's theorem, because all the elements in $$\mathbb{F}_q^*$$ are roots.

Consequently, since $$x^{q-1} - 1 = ( x^{(q-1)/2} + 1 ) ( x^{(q - 1)/2} - 1 )$$ and the ring of polynomials over $$\mathbb{F}_q$$ has no (non-trivial) zero divisors, again Fact 1 implies that both factors $$( x^{(q-1)/2} + 1 )$$ and $$( x^{(q-1)/2} - 1 )$$ must have exactly $$\frac{q-1}{2}$$ roots.

• Actually, that doesn't actually prove what you're interested in, as it leaves open the possibility, even though half of the possible values between 0 and q-1 are QRs, perhaps $x^3 + ax + b$ is a QR anomalously often or rarely. To show that doesn't happen is essentially Hasse's theorem (which I implicitly invoked by stating that $q \approx n$) Dec 1 '16 at 17:44
• @bekah, very good explanation about roots of $X^{q-1}-1=0$ and their classification in QR and QNR in a finite field K. However when one necessitate to choose random points on an EC, the traditionnal algorithm is "Try and Increment" as you describe above. Another alternative is to the deterministic construction as mentionned here: eprint.iacr.org/2009/226.pdf Dec 2 '16 at 15:41
• @RobertNACIRI thanks, sadly I don't have $q \equiv 2 \mbox{ mod }3$ so I'm not sure it's possible to use Icart's function in this case! Try and Increment is doing the job :) Dec 3 '16 at 21:16