What is the relationship between parity and the sign of the points on the elliptic curve?

Question

EDIT: I found out that the answer on the second question is just to do 10 * -G, that is, 10 * G(X, -Y) instead of -10 * G. However, I still do not understand relation between parity and the sign of the point.

I know that a private key is some random 256 bit number, which multiplied with G (generator point), gives a public key (a point on the curve). Multiplication denotes adding G point to itself private key number of times. For every X coordinate, 2 Y coos exist, EVEN and ODD. Also, these two point are negations of each other, so (X, Yeven) + (X, Yodd) = Inf and (X, Yodd) + (X, Yeven) = Inf.

For example, in the elliptic curve:

a=2
b=4
p=11
G=(2, 4) 

... for the point (3, 2) the negation is (3, 9) and vice versa. Also, (3, 2) + (3, 9) = Inf and (3, 9) + (3, 2)= Inf.

This is completely clear to me because in the equation for adding two points of the elliptic curve, in this case we will get below / zero (0), so division will not be possible, and the result is Inf.

However, in many articles I see that they talk about POSITIVE and NEGATIVE Y coordinate, not even and odd.

According to them, there exists pair of points (X, Y) (X, -Y) and, from it, the equations (X, Y) + (X, -Y) = Inf and (X, -Y) + (X, Y) = Inf. That is, for every (X, Y) exist its negation -(X,Y) = (X,Y).

So in the previous example, for the point (3, 2) exists -(3, 2) = (3, -2) and an equations (3, 2) + (3, -2) = Inf and (3, -2) + (3, 2) = Inf.

This makes no sense to me because the point (3, -2) is not part of the elliptic curve at all and elliptic curve is only "in the context" of the positive numbers.

1. How is it possible? What is the relationship between parity and the signs of points on an elliptic curve? Should I use the -Y point in the addition equation even if it is not part of the elliptic curve?

Also, all these articles says that we can get a negation of some point by doing - private_key * G. Since the private key for the (3, 2) is 10, they say that we should just use -10 and -10 * (2, 4) to get (3, 9).

2. If we know that the public key is a result of adding G point to itself private key number of times, how is it possible to apply addition with a negative number, that is, in the example, to add G to itself -10 times?

Answer 1

First some background

The X and Y coordinates of an elliptic curve are not integers. They are elements of a finite field. In secp256k1, that is the modulo p = 2²⁵⁶-2³²-977 field. In your example, that is the modulo p = 11 field. Elliptic curves over different fields are also possible, including ones which don't even look like integers.

In these modulo fields, many standard arithmetic operations have a different meaning. Addition, subtraction, and multiplication are performed following a modulo p step. I think you understand this already, but miss that it also applies to constants. -2 is the negation of 2, which modulo p = 11, equals 9. Thus, (3, -2) very much lies on your curve, as it's just another way of writing (3, 9). Note that our choice of treating [0, 1, ..., 10] as the "right" way of representing these field elements is also just a convention - there is nothing special about this choice. All elliptic curve formulas work just fine with the other representations too.

It goes further, though. Division in the field modulo p isn't anything like integer division. Given the fact that for example 3×8 = 24 = 2 (mod 11), and division is the reverse operation of multiplication is division, it has to hold that 2/8 = 3 (mod 11), and 2/3 = 8 (mod 11), but from an integer perspective, 2 is clearly not divisible by 3. The answer is that division modulo p is actually multiplication with the modular inverse. Similarly square roots are also nothing like normal square roots, but become modular square roots (the reverse operation of squaring).

Why do people use the same terms/symbols for things like negation, multiplication, division, square roots, if they're nothing like the "normal" ones? Because for abstract mathematics, it actually doesn't matter what field one works on, or what these exact operations correspond to. Elliptic curves can be defined over any field, and their equations, addition formulas, properties, ... generally hold over all or many of them. This abstraction means mathematicians can describe these curves just once, and then one can instantiate them for whatever field one likes, as long as one uses whatever these operations mean for the chosen field.

So what do the terms "positive" and "negative" refer to?

If -2 and 9 are the same thing modulo 11, we clearly can't use this fact to call some numbers positive or negative. Every field element has both positive and negative integer representatives (infinitely many even, because -2 is also equal to -13, -24, -35, or to 20, 31, 42, ...).

The truth is, there just doesn't exist a well-defined "positive" and "negative" for modulo fields. However, it turns out that it's still useful to pick some definition, in analogy with integers or real numbers, so that one can make statements like "for a given X coordinate on the curve there are two Y coordinates - one positive and one negative". The reality is that it doesn't really matter how one chooses this - it's just a convention - as long as it holds that negating a (nonzero) positive element gives a negative element, and vice versa.

There are many different possible choices for these, and all are used in some context(s):

• Call a field element positive, if when represented as an integer in range [0, p-1] it is smaller than p/2, and negative if above p/2. Modulo 11 this means [1, 2, 3, 4, 5] are positive, and [6, 7, 8, 9, 10] are negative. This also means that 20 = 9 = -2 = -13 is negative, and 14 = 3 = -8 = -19 is positive.
• Call a field element positive, if when represented as an integer in range [0, p-1] it is odd, and negative if even. Modulo 11 this means [1, 3, 5, 7, 9] are positive and [2, 4, 6, 8, 10] are negative. In this case, sign and parity are basically the same thing.
• Call a field element positive if it has a square root, and negative if it doesn't. (this only works if p mod 4 = 3). Modulo 11 this means [1, 3, 4, 5, 9] are positive and [2, 6, 7, 8, 10] are negative.

Picking a different definition will result in different field elements being called positive and negative, but for all of them, it will be the case that among the two Y coordinates for a given X coordinate on the curve, one will be positive and one will be negative.

So: pick whatever definition you like.

Back to your questions

What is the relationship between parity and the signs of points on an elliptic curve?

If you pick parity as sign, then they are the same thing. If you don't, they're really unrelated.

Should I use the -Y point in the addition equation even if it is not part of the elliptic curve?

It is part of the curve. If (X, Y) is on the curve, then so is (X, -Y), if one takes into account that that negation sign is the field's negation operation, which isn't necessarily the same as integer negation. Specifically, for modulo p fields, -Y = p-Y.

If we know that the public key is a result of adding G point to itself private key number of times, how is it possible to apply addition with a negative number, that is, in the example, to add G to itself -10 times?

Adding G to itself -10 times is the same as adding (-G) to itself 10 times. Alternatively, you can compute it by first adding G to itself 10 times, and then negating the result. It's also equivalent to subtracting G 10 times from the point at infinity (where point subtraction is the same as point addition with negation of the operand).

There is a third option, by taking into account that G is a generator for the elliptic curve group, which has order n (for your small curve, n=17). This means that every 17 additions of G you loop around (or, put otherwise, 17×G = Inf). This means that going backwards 10 times is the same as going forward 7 times, and (-10)×G = 7×G, or more generally, (-a)×G = (n-a)×G.