Why even/odd coordinates correspond to positive/negative signs in elliptic curves
Please explain why even/odd coordinates correspond to positive/negative signs.
Explain with example please and expect some questions in the comments.
Babaduras
Answer
- The questioner was satisfied with and accepted the answer, or
- The answer was evaluated as being 100% correct by the judge.
Kav10
-
“ 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?
-
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.
-
-
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
-
-
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
-
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).
-
-
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.
-
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?
-
-
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.
-
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.
-
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?
-
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.
-
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.
-
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.
-
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
-
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
- answered
- 997 views
- $15.00
Related Questions
- If both $n$ and $\sqrt{n^2+204n}$ are positive integers, find the maximum value of $𝑛$.
- Prove the following limits of a sequence of sets?
- Wierdly Rational Fractions
- Elementary num theory Q: or
- The last six digits of the number $30001^{18} $
- Prove that one of $(n+1)$ numbers chosen from $\{1,2, \dots, 2n\}$ is divisible by another.
- Solve $x^{83}\equiv 7\pmod {139}$
- Elementary group theory and number theory questions involving prime numbers, permutation groups and dihedral groups. Introduction to number theory questions
