# How to determine whether a point is greater than n/2?

How can we determine if a private key associated with a point, on an EC, is less than or greater than 1/2 $$n$$, where $$n$$ is the order?

• The first step to determining something is defining it. How do you define that a point $P$ of the curve is "less than $n/2$"? Do you mean $\exists x\in\mathbb N$ with $x\cdot G=P$ and $x<n/2$, where $G$ is some given point of the curve? Or something else? In the first case, hint: what must be the cost of such algorithm relative to one finding $x$?
– fgrieu
Aug 4 at 6:35
• yes that is what i mean. Where x is less than n/2. Aug 4 at 19:55
• Please edit the question clarifying that Aug 4 at 20:21
• This is sort of ill defined, since $[x]P = [x+n]P$. (@fgrieu's definition is ok though) Aug 8 at 7:53

How can we determine if a private key associated with a point, on an EC, is less than or greater than $$1/2 n$$, where $$n$$ is the order?
The obvious way is to compute the discrete log of the private key (achievable in $$O( \sqrt{n} )$$ steps, and compare.
In addition, it can be shown that there isn't a significantly cheaper way - given an Oracle that, given a point, computes where the discrete log is greater than or less than $$1/2 n$$, we can compute the discrete log with $$\log_2{n}$$ queries (plus some relatively cheap operations); hence this Oracle cannot be cheaper than $$1 / \log_2{n}$$ times as cheap as the above naïve approach.