Up to 4 Different Points within ECDSA/Public Key Recovery technique In the answer to this question, it is stated that:


  Rearranging this equation you get rP = sR - mG, or P = (s/r)R - (m/r)G. Thus, it seems we can just compute the public key from the message and the signature. Unfortunately, there can be up to 4 different points R for which R.x mod n = r (in practice, the number is almost always 2).


How is it possible that there could be up to 4 different points for R? And why would it most often be 2 different points?
Negating an elliptic curve point means negating its Y coordinate (modulo the field size p), so -(x,y) = (x,-y). This implies that if you have a point R for which R.x mod n = k (where n is the curve order), then the same will be true for -R.

Furthermore, and with negligable probability, it is possible that both R.x and R.x + n are valid X coordinates (only when R.x &lt; p-n). In that case, there are 4 possible points ((r, y1), (r,-y1),(r+n,y2),(r+n,-y2)).