Why even/odd coordinates correspond to positive/negative signs in elliptic curves

Whereas uncompressed public keys have a prefix of 04 ,compressed public keys start with either a 02 or a 03 prefix. Let’s look at why there are two possible prefixes: because the left side of the equation is y^2 , that means the solution for y is a square root, which can have a positive or negative value. Visually, this means that the resulting y coordinate can be above the x-axis or below the x-axis. As you can see from the graph of the elliptic curve in Figure 4-2, the curve is symmetric, meaning it is reflected like a mirror by the x-axis. So, while we can omit the y coordinate we have to store the sign of y (positive or negative), or in other words, we have to remember if it was above or below the x-axis because each of those options represents a different point and a different public key. When calculating the elliptic curve in binary arithmetic on the finite field of prime order p, the y coordinate is either even or odd, which corresponds to the positive/negative sign as explained earlier. Therefore, to distinguish between the two possible values of y, we store a compressed public key with the prefix 02 if the y is even, and 03 if it is odd, allowing the software to correctly deduce the y coordinate from the x coordinate and uncompress the public key to the full coordinates of the point.


Please explain why even/odd coordinates correspond to positive/negative signs.
Explain with example please and expect some questions in the comments.

Answer

Answers can only be viewed under the following conditions:
  1. The questioner was satisfied with and accepted the answer, or
  2. The answer was evaluated as being 100% correct by the judge.
View the answer
Kav10 Kav10
1.9K
  • “ Conversely, if the y-coordinate is odd, the result after reduction modulo p can be positive or negative, depending on whether the original y-coordinate was positive or negative.” How can result of modulo operation be negative?

    • Kav10 Kav10
      0

      Probably better to ignore that part of my response. When I mentioned "positive or negative," I was referring to the sign of the original y-coordinate, not the result of the modulo operation itself.

  • Kav10 Kav10
    0

    Let's consider the Z11 finite field, where integers are taken modulo 11, we have: 0≡11≡22≡−11(mod11) 1≡12≡23≡−10(mod11) 2≡13≡24≡−9(mod11) 3≡14≡25≡−8(mod11) 4≡15≡26≡−7(mod11), So, for instance, we cannot consider the number 4 here to be positive, becasue it equals -7.

    • Ok, anyway don’t see any logic here. Could you please share some more examples where I can clearly see relation of even odd numbers with signs please? I’m really struggling to understand it

  • Kav10 Kav10
    0

    Please see this, same question as you asked here, https://bitcoin.stackexchange.com/questions/41662/on-public-keys-compression-why-an-even-or-odd-y-coordinate-corresponds-to-the-p

    • That’s actually why I came here, I didn’t get the explanation. List of modulos says nothing to me. 0 = 7 = 14 = -7 1 = 8 = 15 = -6 2 = 9 = 16 = -5 So what? I don’t see a pattern here, both odd and even numbers have negative congruent numbers, so both can’t be called positive or negative, aren’t them? Next “ Despite that, the square root still has two solutions. For example, 3^2 = 9 = 2, 4^2 = 16 = 2. Thus both 3 and 4 are square roots of 2.” and what does it tell us? It is very obvious

    • Kav10 Kav10
      0

      The modulos example says that you cannot say 2 is positive, see that it equals -5. Basically, when talking about modolus in a finite field, we cannot say positive or negative. So, when there are two solutions, one is odd and one is even, like the example regarding 3^2=9=2, 4^2=16=2 (all mod 7).

  • Kav10 Kav10
    0

    It has very simialar examples, but more details. Let me know if that makes it more clear. If not I can try to provide more examples.

  • Kav10 Kav10
    0

    When we say "negative congruent numbers," we're not referring to the numbers being negative in the usual sense but rather to the fact that they are congruent to negative numbers modulo the modulus.

    • I understand that there are two solutions, but why exactly even corresponds to negative, and odd to positive?

  • Kav10 Kav10
    0

    For example, in Z7 , when we say −7, we don't mean "-7" as a negative number but rather as "7 less than a multiple of 7." Similarly, when we say −6, we mean "6 less than a multiple of 7." So, in the context of modular arithmetic, "negative congruent numbers" don't carry the usual meaning of negativity, they just represent numbers that are congruent to negative numbers modulo the modulus.

  • Kav10 Kav10
    0

    In a finite field Fp, where p is a prime number, the concept of "negative" or "positive" isn't directly applicable because all arithmetic is done modulo p, and the numbers wrap around within the range 0 to p−1.

    • Kav10 Kav10
      0

      That is just to distinguish between the two possible values of y. The concept of negative and positive causes the confusion. It is different from the traditional positive and negative signs.

    • Here is my example, correct me please if I’m wrong. Let’s consider 9 mod 10. Bot 3^2=9 (mod 10) and 7^2 = 49 = 9 (mod 10). So both 3 and 7 and square roots of 9. Why are they both odd?

    • Kav10 Kav10
      0

      That is correct. In your example, both are odd. This example is probably not related to an elliptic curve. When one is odd and one is even, we need a way to say which one we are referring to.

    • Kav10 Kav10
      0

      The evenness or oddness of the y-coordinate relates to the representation of points on the curve and not directly to the properties of the square roots modulo p.

    • Kav10 Kav10
      0

      When dealing with elliptic curves we often perform arithmetic operations on points on the curve. One such operation is point addition, which involves finding the sum of two points on the curve. In this process, we might need to find the inverse of a point P, denoted as −P, which requires negating the y-coordinate of P. For example: Suppose we have this elliptic curve y^2≡x^3+7 mod 17 defined over the finite field F17. Consider a point P with coordinates (2,6) on this curve.

    • Kav10 Kav10
      0

      To negate the y-coordinate of P, we compute −P=(2,−6), where −6 is the additive inverse of 6 mod 17. In this case, −6 ≡ 11 mod  17. When we reduce 11 modulo 17, we get 11. Now, −P has coordinates (2,11). In this example, when we negate the y-coordinate of the point P, we ensure that the resulting y-coordinate is either even or odd modulo 17, which is needed for the arithmetic operations involved in elliptic curve cryptography.

    • My main problem was that I didn’t consider curve over prime field, indeed in prime field you can get only even and odd roots. But still don’t see any connection of signs and even/odd

    • Let’s consider bitcoin elliptic y^2 = x^3 + 7 mod17. When x = 8, x^3 + 7 = 519 mod17 = 9. So y^2 = 9 will have two solutions : 3 and -3. -3 after mod 17 will become 14. So here even number corresponds to negative sign, while odd to positive. If we consider x = 10. x^3 + 7 = 1007 mod 17 = 4. Again y^2 = 4 has two roots : 2 and -2. After mod -2 becomes 15, so in this case even number is positive, and odd is negative. These are valid points on the curve

    • Kav10 Kav10
      +1

      It is not the case that always negative correspond to even or to odd or vice versa. It depends on the elliptic curve. It is a way to point to which one we are storing as the public key prefix. Looks like now you are comfortable with only odd and even solutions for elliptic curves over prime fields. The +/- sign depends on the case.

  • Ok, so just not to spend your time, I will tip you of course. Just give me 3-4 examples with coordinates, where we have negative and positive coordinates and how they equal to even odd numbers, I think I need some examples to Understand

The answer is accepted.
Join Matchmaticians Affiliate Marketing Program to earn up to a 50% commission on every question that your affiliated users ask or answer.