Find coordinate $y$ of an elliptic curve point

Question

If I have an elliptic curve over a finite filed $F_p$ ($p$ is prime) defined as $$ y^2 \equiv x^3 + ax + b\pmod p,$$ such that $4a^2 + 27b^2 \neq 0$ and suppose I have only given the coordinate $x$, how can I fast find the $y$ coordinate? I mean if I for example want to write an application, or just don't want to check respectively every possible value. A my second question is: is any upper bound of $y$ value?

Answer 1

Given $x$, if you write $n\equiv x^3+ax+b \bmod p$, and assuming that $n$ is a quadratic residue modulo $p$ (which you can check quickly using quadratic reciprocity), then all you are asking is how to find a square root of $n$ modulo $p$, efficiently. One such method is Cipolla's algorithm. The wikipedia page for Cipolla's algorithm explains the method itself, and its speed in computing a square root.