# Probability when representing message as a point on elliptic curve

There is a very popular method to represent a message $$m$$ (number) as a point on elliptic curve over a finite field:

1. Set $$i = 0$$
2. Check whether $$m'=m\cdot K+i$$ is on elliptic curve. If not, try again for $$i+1$$. If it is, compute such $$y$$ for $$m'$$ and you have point $$(m', y)$$

And it is very often said that chances of failure is $$\frac{1}{2}^{k}$$, because chances of point not being on elliptic curve is $$\frac{1}{2}$$. However, I can't find at least a brief proof of that.

• This answer indicates that How to create an EC point from a plaintext message for encryptiont Dec 4, 2023 at 16:35
• That is: $x^3+ax+b$ is a square approximately half (QR/QNR) of all $x$, i.e. 50%. Therefore with only around $2^{-\kappa}$ probability this method will fail to embed a message to a point on $E$ over $\mathbb{F}_q$. Dec 4, 2023 at 16:48

I'll restrict to a curve of equation $$y^2\equiv x^3+ax+b\pmod p$$ with prime $$p$$.
For a given integer $$z\in[0,p)$$, consider the number of integer solutions $$y\in[0,p)$$ for $$y^2\equiv z\pmod p$$. By Euler's criteria, there are
• $$2$$ for $$(p-1)/2$$ values of $$z$$ known as quadratic residues modulo $$p$$ (those with $$z^{(p-1)/2}\bmod p=+1\,$$). Notice that if $$y$$ is a solution, that $$p-y$$ is another.
• $$1$$ if and only if $$z=0$$. That solution is $$y=0$$.
• $$0$$ for $$(p-1)/2$$ values of $$z$$ known as quadratic non-residues modulo $$p$$ (those with $$z^{(p-1)/2}\bmod p=p-1\,$$).
Under the first order approximation that one of the question's $$m'$$ for a certain $$i$$ yield $$z=(m'^3+am'+b)\bmod p$$ with probably of falling in either of the three cases mostly like for a random $$z$$, it would follow there's a solution $$y$$ making $$(m′,y)$$ on the curve with probability $$\frac12+\frac1p$$ (corresponding to the cases of $$2$$ or $$1$$ solutions). That probability converges to $$\frac12$$ for large $$p$$. Under the assumption that the probability is mostly independent for consecutive $$i$$, that yields probability near $$\left(\frac12\right)^k$$ of not finding a solution after trying $$k$$ values of $$m'$$, as asked.
This yields the correct result, but is far from rigorous. In particular, should we look at it closer, for curves of cryptographic interest, values of $$a$$, $$b$$ and $$p$$ are such that the case $$(x^3+ax+b)\bmod n=0$$ happens for no value of $$x$$. And the number of integers $$x\in[0,p)$$ such that the integer $$z=(x^3+ax+b)\bmod n$$ is among the cases with $$2$$ solutions is $$(n-1)/2$$, where $$n$$ is the order of the curve (that is the number of points on the curve plus the point at infinity), not $$(p-1)/2$$. However, by Hasse's theorem, $$\left|n-1-p\right|\le\sqrt p$$, thus $$n/p$$ converges to $$1$$ when $$p$$ grows, thus we have, rigorously now, a probability converging to $$\frac12$$ for large $$p$$ and random $$i$$. I know no proof that the probability is mostly independent for consecutive $$i$$, but that works well in practice.