# Extracting the value of $y$ from $x$ in an elliptic curve over a finite field

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.

-
Right shift is equivalent to dividing by 2. So right-shifting twice is the same as dividing by $2^2=4$ : 24 >> 2 == 6 Now as to why $p$ can't be even... –  Guess who it is. Dec 10 '10 at 18:24
Shift right is the same as division by 2. The result follows by an application of Fermat's little theorem. –  Qiaochu Yuan Dec 10 '10 at 18:25
As for "why couldn't they be straightforward?": bit-twiddling is a cheaper operation than integer division, and it looks like the computing environment you are using does not optimize division operations when the divisor is a power of 2. –  Guess who it is. Dec 10 '10 at 18:32
p can't be even because it is a large prime, but can I be certain that the (p+1) will divide by 4? Does the presented operation actually retrieve the value of y? –  dankilman Dec 10 '10 at 18:36