2

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?

Tom V
  • 31
  • Hi, and welcome to the site :) ! It would be better if you could write where exactly the procedure fails for you can show that 1) you show that you have tried the problem yourself and 2) the community can assist you better. – Nick A. May 09 '18 at 04:39
  • There is no procedure I have right now. I found some procedures that do not work in my situation. Highlighting those procedures and how they do and don't work could lead to a very long post. – Tom V May 09 '18 at 04:49
  • Did you start with a specific point, or are you looking for a general formula? – Lubin May 09 '18 at 04:50
  • I am looking for a general formula. It seems that doubling a point P(x,y) means finding the tangent at P(x,y) and finding the point on the tangent line that intersects the curve. I kind of want the inverse. I want the tangent line (or tangent lines, if there is more than one) that are tangents to the curve that go through P(x,y) – Tom V May 09 '18 at 04:54

2 Answers2

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$.

Lubin
  • 62,818
  • Thank you for your response. I understand the differential 3x^2/2y, but not much of the rest. I will spend much of the night looking up your "quite easy" math and trying to understand it. – Tom V May 09 '18 at 05:33
  • Actually, I don't necessarily need to completely understand the math. Do you believe you can reliably halve a point on the curve y^2=x^3+7? That is, given a point Q(x,y) on an elliptic curve, can you reliably find a point P(x,y) where Q = 2P? – Tom V May 09 '18 at 05:45
  • Yes, absolutely, but you’ll need to solve that quartic. Ordinarily this will involve solving equations that you (and I) don’t know how to do. Is your base a finite field, by the way? That would make matters far easier, but if your base is the rational numbers (as it appears to be), after you supply the coordinates of the original point $(a,b)$, it looks to be a Galois extension of degree twelve. And why in the world do you want to do this, anyhow? – Lubin May 09 '18 at 12:52
0

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.

fgrieu
  • 1,758