secp256k1 – What’s the relationship between parity and the signal of the factors on the elliptic curve?


The X and Y coordinates of an elliptic curve (no less than within the context of cryptography) are not integers. They’re parts of a finite discipline. In secp256k1, that’s the modulo p = 2256-232-977 discipline. In your instance, that’s the modulo p = 11 discipline. Elliptic curves over totally different fields are additionally potential, together with ones which do not even look like integers in any respect (together with, say, sure polynomials!).

In these modulo fields, many normal arithmetic operations have a special that means. Addition, subtraction, and multiplication are carried out modulo p. I believe you perceive this already, however miss that it additionally applies to constants. -2 is the negation of 2, which modulo p = 11, equals 9. Thus, (3, -2) very a lot lies on the curve, because it’s simply one other approach of writing (3, 9).

It goes additional, although. Division within the discipline modulo p is not something like integer division. Given the truth that for instance 3×8 = 24 = 2 (mod p), and division is the reverse operation of multiplication is division, it has to carry that 2/8 = 3 (mod p), and 2/3 = 8 (mod p), however from an integer perspective, 2 is clearly not divisible by 3. The reply is that division modulo p is definitely multiplication with the modular inverse. Equally sq. roots are additionally nothing like regular sq. roots, however turn into modular sq. roots (the reverse operation of squaring).

Why do folks use the identical phrases/symbols for issues like negation, multiplication, division, sq. roots, in the event that they’re nothing just like the “regular” ones? As a result of for summary arithmetic, it really would not matter what discipline one works on, or what these precise operations correspond to. Elliptic curves could be outlined over any discipline, and their equations, addition formulation, properties, … typically maintain over all or a lot of them. This abstraction means mathematicians can describe these curves simply as soon as, after which one can instantiate them for no matter discipline one likes, so long as one makes use of no matter these operations imply for the chosen discipline.

So what do the phrases “optimistic” and “detrimental” seek advice from?

If -2 and 9 are the identical factor modulo 11, we clearly cannot use this reality to name some numbers optimistic or detrimental. Each discipline factor has each optimistic and detrimental integer representatives (a couple of even, as a result of -2 can also be equal to -13, -24, -35, or to 20, 31, 42, …).

The reality is, there simply would not exist a well-defined “optimistic” and “detrimental” for modulo fields. Nonetheless, it seems that it is nonetheless helpful to select some definition, in analogy with integers or actual numbers, in order that one could make statements like “for a given X coordinate on the curve there are two Y coordinates – one optimistic and one detrimental”. The truth is that it would not actually matter how one chooses this – it is only a conference – so long as it holds that negating a (nonzero) optimistic factor provides a detrimental factor, and vice versa.

There are a lot of totally different alternatives for these, and all are utilized in some context(s):

  • Name a discipline factor optimistic, if when represented as an integer in vary [0, p-1] it’s bigger than p/2, and detrimental if beneath p/2. Modulo 11 this implies [1, 2, 3, 4, 5] are detrimental, and [6, 7, 8, 9, 10] are optimistic. This additionally implies that 20 = 9 = -2 = -13 is optimistic, and 14 = 3 = -8 = -19 is detrimental.
  • Name a discipline factor optimistic, if when represented as an integer in vary [0, p-1] it’s even, and detrimental if odd. Modulo 11 this implies [2, 4, 6, 8, 10] are optimistic and [1, 3, 5, 7, 9] are detrimental. On this case, signal and parity are the identical factor.
  • Name a discipline factor optimistic if it has a sq. root, and detrimental if it would not. (this solely works if p mod 4 = 3). Modulo 11 this implies [1, 3, 4, 5, 9] are optimistic and [2, 6, 7, 8, 10] are detrimental.

Choosing a special definition will lead to totally different discipline parts being referred to as optimistic and detrimental, however for all of them, will probably be the case that among the many two Y coordinates for a given X coordinate on the curve, one can be optimistic and one can be detrimental.

So: decide no matter definition you want.

Again to your questions

What’s the relationship between parity and the indicators of factors on an elliptic curve?

If you happen to decide parity as signal, then they’re the identical factor. If you happen to do not, they’re actually unrelated.

Ought to I exploit the -Y level within the addition equation even when it’s not a part of the elliptic curve?

It’s a part of the curve. If (X, Y) is on the curve, then so is (X, -Y), if one takes under consideration that that negation signal is the sector’s negation operation, which is not essentially the identical as integer negation. Particularly, for modulo p fields, -Y = p-Y.

If we all know that the general public secret is a results of including G level to itself personal key variety of instances, how is it potential to use addition with a detrimental quantity, that’s, within the instance, so as to add G to itself -10 instances?

Including G to itself -10 instances is identical as including (-G) to itself 10 instances. Alternatively, you’ll be able to compute it by first including G to itself 10 instances, after which negating the consequence.

There’s a third possibility, by taking into consideration that G is a generator for the elliptic curve group, which has order n (on your small curve, n=17). Because of this each 17 additions of G you loop round (or, put in any other case, 17×G = Inf). Because of this going backwards 10 instances is identical as going ahead 7 instances, and (-10)×G = 7×G, or extra typically, (-a)×G = (n-a)×G.

Supply hyperlink


Please enter your comment!
Please enter your name here