Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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... –  J. M. Dec 10 '10 at 18:24
1  
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
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. –  J. M. 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

1 Answer 1

up vote 5 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.