Determine if a public key point y is negative or positive, odd or even?

Question

Take an elliptic curve cryptography public key (x, y) and its additive inverse (x, -y). How do you identify which is the positive point and which is the negative point?

Examples:

Private key 1 -> (x, y)

x = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798L

y = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8L

-y = 0xb7c52588d95c3b9aa25b0403f1eef75702e84bb7597aabe663b82f6f04ef2777L

Private key 2 -> (x, y)

x = 0xc6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5L

y = 0x1ae168fea63dc339a3c58419466ceaeef7f632653266d0e1236431a950cfe52aL

-y = 0xe51e970159c23cc65c3a7be6b99315110809cd9acd992f1edc9bce55af301705L

Private key 3 -> (x, y)

x = 0xf9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9L

y = 0x388f7b0f632de8140fe337e62a37f3566500a99934c2231b6cb9fd7584b8e672L

-y = 0xc77084f09cd217ebf01cc819d5c80ca99aff5666cb3ddce4934602897b4715bdL

Also, how can you identify which public key is odd and which is even?

For example: private key 1 x,y is odd, private key 2 x,y is even (based with pub key).

CodesInChaos · Answer

Elements of finite fields don't really have a sign. But depending on context you can define a property that's different for $x$ and $-x$ (when $x$ is not $0$) and call that property sign.

Some possible choices:

A number is called a square (or Quadratic residue) if there is another number which produces it when squared. Since positive real numbers are squares, identifying square field elements with a positive sign is a natural choice.

The Legendre symbol is 0 for 0, +1 for squares and -1 for non-squares. The Legendre symbol of the product of two numbers is the product of the two Legendre symbols, which mirrors how signs behave under multiplication.

You can even define $i = sqrt{-1}$ to get some kind of complex numbers. Imaginary values of the $y$ coordinate of an elliptic curve correspond to its twist.
You can use the least significant bit. Computing this is very cheap, you only need to look at that one bit. This approach is often used to store the "sign" of a compressed elliptic curve coordinate.
Values smaller than $p/2$ have one sign, values greater than $p/2$ the other. I believe Bitcoin uses this convention to define canonical signatures.

You can extend any of these definitions from the underlying field to the elliptic curve defined over that field by defining the sign of the point as the sign of its $y$ coordinate.

user27950 · Answer

In finite fields there is no distinction between positive and negative numbers. This implies that you also do not have positive or negative points in an elliptic curve over a finite field.  But you can nevertheless distinguish the two points by looking at the least significant bit.
For instance, this will be used by the point compression method.

Determine if a public key point y is negative or positive, odd or even?

2 Answers

Add your own answers!

Ask a Question