# Distinguishing EC Public Key from random

I recently read the post Distinguishing x25519 public keys from random? and found myself wondering why, for a randomly chosen x, the result of the function $$x^3+ax^2+x$$ is a square in 50% of cases and not in the other 50%. I understand that in a finite field with an odd prime order, a randomly chosen x is a square in 50% of cases, but I don't see how this directly translates to the above claim. Any help is appreciated. Thank you!

Argument towards $$x^3+ax^2+x$$ being a square modulo $$q$$ for around 50% of $$x$$ when $$a,q$$ are the parameters in Curve25519: we know $$y^2\equiv x^3+ax^2+x\pmod q$$ defines a proper elliptic curve group. By Hasse's bound it's order (number of elements) $$N$$ is* such that $$\bigl|N-\left(q+1\right)\bigr|\,\le\,2\sqrt q\tag{1}\label{fgr1}$$ The elements can be classified as:

• the unity of the group (aka point at infinity).
• $$(x,y)=(0,0)$$, in which case $$x^3+ax^2+x\equiv0\pmod q$$ thus $$x^3+ax^2+x$$ is a square modulo $$q$$
• other points $$(x,y)\in[0,p]$$ with $$y^2=x^3+ax^2+x\equiv0\pmod q$$.

Therefore there are $$N-2$$ points of the later kind. They go in pairs sharing the same $$x\bmod q\ne0$$, because if point $$(x,y)$$ satisfies the curve's equation and $$x\bmod q\ne0$$, then $$(x,q-y)$$ is a different point that also satisfies the curve's equation.

Therefore there are $$1+(N-2)/2=N/2$$ values of $$x\in[0,q)$$ with $$x^3+ax^2+x\bmod q$$ a square. That's a proportion $$r=N/(2q)$$.

Dividing $$(\ref{fgr1})$$ by $$2q$$, we get $$\Biggl|\,\frac N{2q}-\left(\frac12+\frac1{2q}\right)\Biggr|\,\le\,\frac1{\sqrt q}\tag{2}\label{fgr2}$$ thus $$\Biggl|\,r-\frac12\Biggr|\,\le\,\frac1{\sqrt q}+\frac1{2q}\tag{3}\label{fgr3}$$ And since $$q$$ is 255-bit, $$r\approx1/2$$ for all practical purposes.

* More precisely, for Curve25519, $$p=2^{255}-19$$ and $$N=8\ell$$ with $$\ell=2^{252}+ 27742317777372353535851937790883648493$$