4
$\begingroup$

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!

$\endgroup$
0

1 Answer 1

6
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.