1
$\begingroup$

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.

$\endgroup$

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.