Determine if an elliptic point is negative

Question

How to determine if an elliptic point $kG$ is negative? Is $k<0?$

By example, for $k=1234$, the coordinate of the point $1234G$ using secp256k1 = $X= 102884003323827292915668239759940053105992008087520207150474896054185180420338$ $Y= 49384988101491619794462775601349526588349137780292274540231125201115197157452$

Note: $1234 = 0x4D2 = 0b10011010010$

The coordinate of a negative point is equal to (x, -y).

So, $-1234G =$

$(102884003323827292915668239759940053105992008087520207150474896054185180420338,$ $\textbf{-49384988101491619794462775601349526588349137780292274540231125201115197157452})$

We're in a field, so we apply modulo prime: $$-y \; \% \;prime = prime - y$$

So, $-1234G = $

$(102884003323827292915668239759940053105992008087520207150474896054185180420338,$ $ \textbf{prime} - 49384988101491619794462775601349526588349137780292274540231125201115197157452)$

$= (102884003323827292915668239759940053105992008087520207150474896054185180420338,$ $\textbf{66407101135824575629108209407338381264920846885348289499226458806793637514211})$

Is there a trick to known which one correspond to -1234G or 1234G or more generally kG or -kG? Notes: We don't know k. I know that to uncompress a public key, we just know x, we use a bit to say take y less than p/2 or greater than p/2 but in this case it's always a positive k.

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

Answer 1

There is no usual and well-defined meaning to "negative" for a point $P$ of an elliptic curve on a finite field, as used in cryptography. If $P=k\,G$ for negative $k$, then $P=k'\,G$ for $k'=k\bmod n$, which is non-negative (it would be $k'=k+n$ if $0<|k|<n$ ), and $n$ is the order of the group (or of $G$ )

For a given $P$, we could uniquely define $k$ as the integer with the smallest absolute value and $P=k\,G$, then consider the sign of $k$. But

• that not usual
• if the group is cryptographically strong, there is no efficient algorithm to determine the sign of that $k$ from an arbitrary $P$. Argument: if there was such method, it could be used as a subprogram to solve the Discrete Logarithm Problem (that is find $k$ for a given random $P$ in the group generate by $G$ ), by binary search.