2
$\begingroup$

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.

  • 0
    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?2010-12-10

1 Answers 1

4

Call C = x3+ax+b. You want to solve y2 = 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 is 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.