Halving a point on an elliptic curve

Question

I have come across a few scholarly articles on halving points on an elliptical curve (https://eprint.iacr.org/2011/461.pdf, for example) but it doesn't work with my curve. Can anyone explain to me how to halve a point on the elliptical curve y^2 = x^3 + 7?

Answer 1

It’s really quite easy, once you’ve drawn the picture: take your point, call it $P=(a,b)$, and see what points $(\xi,\eta)$ on the curve have their tangent passing through $-P=(a,-b)$. After differentiating to get $2y\frac{dy}{dx}=3x^2$, you get $$\frac{dy}{dx}\Big\vert_{(\xi,\eta)}=\frac{3\xi^2}{2\eta}=\frac{\eta+b}{\xi-a}\,,$$ after which you clear of fractions, replace $\eta^2$ by $\xi^3+7$, then solve for $\eta$ in terms of $\xi$, square and again replace, giving you a sextic (I think) with two extraneous roots, for a quartic in $\xi$.

Answer 2

To perform point having on the curve secp256k1 or similar Koblitz curve over a prime field forming an elliptic curve of prime order, use that $Q=2*P\iff P=((n+1)/2)*Q$, where $*$ is scalar multiplication, and $n$ si the order of the elliptic curve group.