-1

Thank you all very much in advance!

I will explain best with an example what is not clear to me.

Consider the elliptic curve a = 1, b = 2, p = 11 of order 16.

enter image description here

Also let's consider the "opposite" (negations of each other) two points of this elliptic curve (2, 1) and (2, 10) = (2, -1) as starting points. These are the points for which we will do the multiplication.

For both of these two points, the order is 8 (we can only get 8 out of 16 points if we multiply them). I took this example arbitrarily just to make it as small as possible.

By multiplying (2, 1) we get the following points (next to the points are numbers that indicate the number by which (2, 1) must be multiplied to get it):

enter image description here

By multiplying (2, -1) we get the following points (next to the points are numbers that indicate the number by which (2, -1) must be multiplied to get it):

enter image description here

Until multiplying by 4 (in both cases) everything is as I expect. Multiplication just gives opposite points (the negation of each other) since we are working with the opposite points. For example, 2 * (2, 1) gives (8, 4) and 2 * (2, -1) gives (8, -4) = (8, 7) since it is the opposite (negation) of (8, 4). Same for multiplying by 3. This works literally the same as in case of working with an elliptic curve over real numbers. So everything is clear.

However, what confuses me is that after multiplying with 4 we're starting to sort of go backwards.

For example, multiplying (2, 1) by 5, we get (5, 2), which is also the 3rd point when multiplying (2, -1) (that is, 3 * (2, -1) = (5, 2)). This also applies in the opposite way. Multiplying (2, -1) by 5, we get (5, -2), which is also 3rd point when multiplying by (2, 1).

It turns out that we are actually going backwards, which is different from the case when we work with the real numbers where we would just keep going by the principle before multiplying by 4 forever, so that there would be no such "repetition" of points

Also, it looks like multiplying by 4, i.e. the point (10, 0) actually represents that TURNING POINT. Better said, up to that point everything goes like with real numbers, however, from there, we start going backwards.

So it goes as expected until some points. After that points, it starts to go backwards until we reach the beginning, that is, (2, 1)/(2, -1) point in our example. In other words, until we make the whole circle, when everything starts from the beginning.

  1. Why is this happening? Why do we have this circular behavior?
  2. What must be specific about a point (in this example (10, 0)) for it to be a turning point? I thought that, in this example, 4 * (2, 1) and 4 * (2, -1) must give the same lambda for the point to be a turning point (since that's the only difference between working on a finite field and on real numbers), but that's not the case , that is, the same lambda is not obtained.
Improve this question
14
  • This elliptic curve is not a cyclic group, meaning it's not possible to write every point on it as some multiple of a generator. Things will work much more naturally when you do use a cyclic group (like a=1 b=3, over the same field), and even better when using a prime-ordered group (like a=1 b=5, over the same field). This explains why you're not reaching all points on the curve, though isn't really an answer to your question. I suggest retrying with a=1 b=5 and see if the result is still unexpected to you. However, I suspect there will not be much more to say than "it just is".
    – Pieter Wuille
    Nov 21 at 17:14
  • In this case, the order of the point you started with is 8 (as there are only 8 points reachable as multiples of your starting point). Multiplying with 3 and multiplying by 5 is not the same thing; they're each others negation. So you observe that 3*G = -(5*G). That is entirely expected, as 3 = -5 mod 8, so 3*G = (-5)*G = -(5*G). On a prime-ordered curve this will be modulo the curve order (as on such curves the order of every non-infinite element is equal to the curve order).
    – Pieter Wuille
    Nov 21 at 17:19
  • Perhaps the answer to your question is just that once you're past half the starting point's order, you'll start to see the same X coordinates (but opposite Y coordinates), as you're effectively going through their negations ([1,2,3,4,5,6,7] mod 8 = [1,2,3,4,-3,-2,-1] mod 8). This is true for every cyclic group (not just elliptic curve groups). Even though the curve itself isn't cyclic in this case, the subgroup generated by the multiples of your starting point are.
    – Pieter Wuille
    Nov 21 at 17:32
  • In case the point order is even (as is the case here), it holds that 4 = -4 mod 8, so 4*G = -4*G. Thus, in such groups, it must hold that the halfway point (starting point times half its order) is its own negation. That implies its Y coordinate must be 0, as (X,Y) = (X,-Y) implies Y=-Y, or Y=0. And you can indeed see that is the case here!
    – Pieter Wuille
    Nov 21 at 17:35
  • 1
    You do both. 5 equals -3, 6 equals -2, 7 equals -1, when operating modulo 8 (as happens in a cyclic group of order 8). If you'd actually compute say 45*G you'll end up with the same point as 5*G or -3*G, because modulo 8, all these numbers are the same.
    – Pieter Wuille
    Nov 21 at 18:43

1 Answer 1

Reset to default
1

The points on an elliptic curve, combined with the point at infinity, and the point addition operation, define a group. I consider explaining why that is outside of the scope of this site, but it follows from a number of properies this set and operation has, such as associativity and every element having a negation.

The subset of a group of elements obtained by repeatedly adding a specific element (called the generator) to itself, also forms a group. This group is always cyclic (meaning that every element can be written as a multiple of some specific element - this is obviously true if the group itself is the subset of elements generated that way).

It is a standard result in group theory that every cyclic group is either infinite (in which case it behaves like addition over the integers) or finite (in which case it behaves like additions over the intergers modulo the size of the group).

Since we're working over a finite field, there can only be a finite number of elements our group has. Thus, inevitably, the group obtained by repeatedly adding a particular curve point to itself must be a finite cyclic group. In your example, the one of order 8. If we'd be working over the reals instead, then depending on the starting point it could be an infinite cyclic group too (but not necessarily; e.g. (1,2) on y2 = x3 + x + 2 over the reals defines a cyclic group of order 4, consisting of [(1,2), (-1,0), (1,-2), infinity]).

Since our group is a finite cyclic group of order 8, it must behave identical to the integers modulo 8. In other words, 5G is the same as (-3)G, which is -(3G), which is the negation of 3G, which has the same X coordinate as 3G. This holds for all points, so [1G, 2G, 3G, 4G, 5G, 6G, 7G, 8G] = [1G, 2G, 3G, 4G, -3G, -2G, -1G, 0G]. But it's also equal to [-7G, -6G, -5G, -4G, -3G, -2G, -1G, 0G], or anything else that is equal modulo 8. You can say that it "reverses" after 4G, but all that's happening is that 5G and -3G necessarily have the same X coordinate.

Overall, the bottom line is that when working over a finite cyclic group, as this must be, the second half of group elements obtained are the same as the first half, but negated and in reverse order.

Improve this answer
8
  • Literally everything is clear to me. I understand (and know from earlier) the concepts of groups, cyclic subgroups etc. I also understand that in context of integers mod n (let's say 8), for example: ... -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, it would correspond to the ... 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4 ... and it is cyclic group since it repeats. In context of EC I also understand it all if we look at things in the following way.
    – LeaBit
    Nov 21 at 20:46
  • If we consider that this: ... -3*(2,1), -2*(2,1), -1*(2,1), 0*(2,1), 1*(2,1), 2*(2,1), 3*(2,1), 4*(2,1), 5*(2,1), 6*(2,1), 7*(2,1), 8*(2,1), 9*(2,1), 10*(2,1), 11*(2,1) ... is equal to this (which it is): ... 5*(2,1), 6*(2,1), 7*(2,1), 0*(2,1), 1*(2,1), 2*(2,1), 3*(2,1), 4*(2,1), 5*(2,1), 6*(2,1), 7*(2,1), 0*(2,1), 1*(2,1), 2*(2,1), 3*(2,1) .... Thus, again cyclic group. However, what confuses me is that -a*G is also a*(Gx, -Gy), so -3*(2, 1) is not just 5*(2, 1) but also 3*(2, -1). Therefore, we are working (in some way) with a completely different point and that confuses me.
    – LeaBit
    Nov 21 at 20:46
  • I hope I have now explained what is confusing me. It seems completely ridiculous, but for some reason I can't understand it, even though it all seems completely logical... I don't know how to get it over my head.
    – LeaBit
    Nov 21 at 20:46
  • 1
    -3 * P = (3 * -1) * P = 3 * -1 * P = 3 * (-1 * P) = 3 * (-P). Multiplying P by -3 is the same as multiplying the negation of P (which means negating its Y coordinate) with 3.
    – Pieter Wuille
    Nov 21 at 21:07
  • 1
    Just to let you know that I finally got it
    – LeaBit
    Nov 21 at 21:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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