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.

  • 1
    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...2010-12-10
  • 1
    Shift right is the same as division by 2. The result follows by an application of Fermat's little theorem.2010-12-10
  • 1
    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.2010-12-10
  • 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.