1
$\begingroup$

Can anyone tell me the specific equations and steps for dividing a point on an elliptic curve by 2?

For instance, I have the point $(P_x, P_y)$, and I would like to find the point $(R_x, R_y)$ which when doubled yields $(P_x, P_y)$.

It was suggested that I use the point doubling equations and solve, but I am looking for the specific equations and steps and perhaps a reference to thorough discussion of the topic.

Thanks for your time.

EDIT: I was under the impression that it would be the same steps for all curves. In this instance I am trying to do it on the secp256k1 curve.

$\endgroup$
  • $\begingroup$ I'm voting to close this question as off-topic because it is about general mathematics. $\endgroup$ – fkraiem Jan 27 '18 at 20:57
  • 3
    $\begingroup$ Even if we wanted doing this assignment thrown in without showing what has been attempted, we lack enough specifics on the curve. One way to do this (quite different from the one suggested) is to compute $i=2^{-1}\bmod q$ where $q$ is the group order, then multiply point $(Px, Py)$ by $i$. $\endgroup$ – fgrieu Jan 27 '18 at 21:21
  • $\begingroup$ I won't entirely dispute your down-vote, but the specific reason that I am posting it here is because you all (Crypto) seem to have the most relevant and thorough understanding of elliptic curves. As is evidenced by @fgrieu 's comment along with almost all of the rest of the discussion here. In short, I respect you all and appreciate your input / knowledge. I also was not able to find anything along these lines anywhere else. $\endgroup$ – ThereIsNoSky Jan 29 '18 at 3:30
  • $\begingroup$ @ThereIsNoSky maybe give us a little bit of context on why you need point halving ? $\endgroup$ – Ruggero Jan 29 '18 at 10:38
4
$\begingroup$

There are two strategies to do what you want.

The first one being to find the group order $q$ and then compute $i=2^{-1}\bmod q$. When you then multiply your point $P$ by $i$ you get $Q=[i]P$ with $[2]Q=[2i]P=[(2\cdot 2^{-1})\bmod q]P=P$ as desired. This general strategy works for any finite group (as long as $q$ is not even) and was quickly pointed out by fgrieu in the comments.

The second way goes as follows:

  1. Find out the equation for your curve. For secp256k1 this is $y^2=x^3+ax+b$ a.k.a. "Short Weierstrass Form".
  2. Go to the explicit formula database and select the relevant curve.
  3. Take the affine doubling equation and plug it into your favourite tool for solving algebraic equations and tell it to solve for the coordinates on the left side.
  4. You should now receive a result. Because all fields are equal when it comes to the transformations carried out, you can just take the resulting formula and "easily" translate it to work over your finite field.
$\endgroup$
  • $\begingroup$ Thank you VERY much for your help and your time. I knew that Crypto was the right place to post this. $\endgroup$ – ThereIsNoSky Feb 1 '18 at 3:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.