# How to prove that an elliptic curve point is smaller or greater than half of the curve's order?

Is it possible to tell if a point on an elliptic curve is less than half of the curve's order?

If I have a point $$𝐴 = [a]𝐺$$ on a curve with prime order q, is there an efficient way to know that $$a < q/2$$?

I understand that range proofs would work for this, but is there a quicker way? Specifically, I am working with secp256k1, but any advice is greatly appreciated.

To see the reduction to the elliptic curve discrete logarithm, suppose that I have a point $$P_0=[x_0]G$$ where the order of $$G$$ is $$q$$ and I wish to know $$x_0$$. I calculate $$2^{-1}\pmod q$$, calculate $$[2^{-1}]P_0$$ and run my magic algorithm. If the algorithm says that there exists an $$a$$ with $$0, then I know that $$x_0$$ is even other wise I know that is is odd. Writing $$b_0$$ for the low bit of $$x$$, I write $$x_1=(x_0-b_0)/2$$ and compute $$P_1=[2^{-1}](P_0-[b]G)=[x_1]G$$. I can now repeat the process to recover the low bit $$b_1$$ of $$x_1$$ and so on, terminating when $$P_n=G$$. This will take at most $$\log_2 q$$ steps.