Given an elliptic curve $y^2 = x^3 + ax + b$ over a finite field $\mathbf{F}_p$, how can I retrieve the value of $y$ given the value of $x$?
My knowledge in this area is quite limited, so I understand this question might seems silly.
I'm currently working on an application that uses an elliptic curves library and I saw at some point that this value was retrieved via: $$(x^3 + ax + b)^{(p+1) >> 2} \mod p$$
the $>>$ means shift right though I am not sure what this means mathematically.
Does this make sense?
Thanks.
Call $C = x^3+ax+b$. You want to solve $y^2 = C$, which is a quadratic equation, specifically extracting a square root. There are lots of ways to extract square roots.
For instance, the way you mention is the first method described in this section of the Wikipedia article on numbers that are squares (quadratic residues). This only works if $p+1$ is divisible by $4$, but as a consequence of Fermat's little theorem.
It also links to a few efficient algorithms, including a full algorithm that uses the one you mentioned if $p+1$ is divisible by $4$.