We are given this encoding method for elliptic curves where we let $p$ be a prime and $M,s$ positive integers such that $p>Ms$. We let $E$ be the elliptic curve given by $Y^2=f(X)$, where $f(X)$ is a cubic polynomial.

The algorithm starts by letting $x=ms+1$. If $f(X)$ is a square in $\mathbb F_p$, the finite field which the elliptic curve is over, we then find $y$ such that $y^2=f(X)$, and set $P_m=(x,y)$.

My question is to find a formula for $m$ in terms of $P_m=(x,y)$ and $s$ assuming we have found some $x$ such that $f(X)$ is a square.

I started by assuming that $x=ms+k$ for $k\le s$ gives us that $f(X)$ is a square. Then $m=(x-k)s^{-1}$. I don't quite know what else is required for the full solution however. Do I need to consider the y-coordinate perhaps? I'm not really sure how I would go about doing that however.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.