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

Improve this question
$\endgroup$
5
  • $\begingroup$ I'm voting to close this question as off-topic because it is about general mathematics. $\endgroup$
    – fkraiem
    Commented Jan 27, 2018 at 20:57
  • 6
    $\begingroup$ 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)=(q+1)/2$ where $q$ is the group order (assumed odd), then multiply point $(Px, Py)$ by $i$. $\endgroup$
    – fgrieu ♦
    Commented Jan 27, 2018 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
    Commented Jan 29, 2018 at 3:30
  • $\begingroup$ @ThereIsNoSky maybe give us a little bit of context on why you need point halving ? $\endgroup$
    – Ruggero
    Commented Jan 29, 2018 at 10:38
  • $\begingroup$ While the technique of multiplying by $(q+1)/2$ is generic, faster explicit formulas working on coordinates depend on the curve. Point halving is inexpensive for curves overs binary fields, so much that it's sometime used instead of doubling to speed-up point multiplication. But AFAIK that does not extend to secp256k1 or other curves on prime fields. $\endgroup$
    – fgrieu ♦
    Commented Mar 8, 2023 at 12:26

3 Answers 3

Reset to default
11
$\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.
Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you VERY much for your help and your time. I knew that Crypto was the right place to post this. $\endgroup$
    – ThereIsNoSky
    Commented Feb 1, 2018 at 3:00
3
$\begingroup$

Here are explicit equations in characteristic not $2$, from the paper "Division by 2 of rational points on elliptic curves" by Bekker and Zarhin (St. Petersburg Math. J. 29 (2018), 683-713).

If the elliptic curve $E$ has equation $y^2=p(x)$ where $p(x)$ is a degree-$3$ polynomial, then let $r_1,r_2,r_3$ be the roots of $p(x)$. For any point $P=(P_x,P_y)$ on $E$ with $P_x\notin\{r_1,r_2\}$, let $s_1$ and $s_2$ be any square roots of $P_x-r_1$ and $P_x-r_2$, respectively, and put $s_3:=-P_y/(s_1s_2)$. Write $u:=s_1+s_2+s_3$ and $v:=s_1s_2+s_2s_3+s_3s_1$. Then $R:=(P_x+v,-P_y-uv)$ is a point on $E$ such that $2R=P$.

Note that there are known formulas for the roots of a degree-$3$ polynomial, in terms of square roots and cube roots of certain elements. Also, the hypothesis $P_x\notin\{r_1,r_2\}$ can always be achieved by relabeling the $r_i$'s if needed. So this recipe really does yield explicit equations.

Improve this answer
$\endgroup$
0
$\begingroup$

For secp256k1, and in general for EC $y^2= x^3+7$ in a prime field, by coordinate values it will look like this:

enter image description here

enter image description here

enter image description here

enter image description here

Improve this answer
$\endgroup$
4
  • $\begingroup$ How would that be used? In particular, $\sqrt[3]2$ is not in the field $\mathbb F_p$, and when we take $\sqrt u$ for some quantity $u$ and that has some solution in the field, we have no criteria to select among the two there is. $\endgroup$
    – fgrieu ♦
    Commented Mar 9, 2023 at 7:11
  • $\begingroup$ @fgrieu - Yes, I agree with you that there is not a solution for every field, but for many fields it works correctly, and in particular for secp256k1. $\endgroup$
    – S. Payazati
    Commented Mar 9, 2023 at 8:38
  • $\begingroup$ How could that work for secp256k1 ? We have $p=2^{256}-2^{32}-977$, such that $x^3\equiv2\pmod p$ has no solution, hence $\sqrt[3]2$ is not defined in the field $\mathbb F_p$. And, as I pointed, each regular square root can take two values, so how would we choose? [update] We can rewrite $\sqrt[3]2\ 7^{2/3}$ as $\sqrt[3]{98}$ but this has 3 solutions; again, how do we choose? $\endgroup$
    – fgrieu ♦
    Commented Mar 9, 2023 at 8:59
  • 1
    $\begingroup$ @fgrieu - About sqrt choose any one of the solutions and check it with the first equation. $4⋅2^{2/3}⋅7^{1/3} = (64⋅2⋅49)^{1/3} = 6272^{1/3}$ this has 3 solutions! Choose any one of the solutions and check it with the first equation.. You at once need the ecdlp solution on a plate with a blue border :-) $\endgroup$
    – S. Payazati
    Commented Mar 9, 2023 at 9:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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