6
$\begingroup$

I am trying to understand how point halving on elliptic curves of even order works. Specifically: suppose $g$ is an elliptic curve, and $G$ is a generator point on this curve. The order of group generated by $G$ is even and equal to $q$. Suppose also that $A = x \cdot G$. I know $A$ but I don't know $x$.

My questions are:

  1. What algorithm(s) could I use to calculate $A' = \frac{A}{2}$ such that $2 \cdot A' = A$?
  2. When $x$ is odd, is the division undefined? Would the halving algorithm detect odd points?
  3. When $x$ is even, my understanding is that there are two solutions $A' =\frac{x}{2} \cdot G =\frac{x + q}{2} \cdot G$. Is there an algorithm that would consistently differentiate between the first and second solutions?
$\endgroup$
3
$\begingroup$

Point-halving on a group generated by an elliptic curve of even order, $G$, can happen, but it can only definitely happen for points that exist in an odd subgroup of $G$. If $x$ is an element of $G$, and $G$ has odd order, then $x$ also has odd order since the order of element divides the order of the group that it's in and even numbers do not divide odd numbers. Hence there are no even ordered points in odd ordered subgroups, and no guarantee that an even ordered point can be halved.

To reiterate - if $A$ exists in an odd subgroup of $G$, then you can half it like any other point, otherwise there is no guarantee that it's half exists.

An algorithm for point-halving can be found in this book, in algorithm 3.8.1 in section 3.6.1:

Also of potential interest: Proof that in finite group $G$, $x$ has a square root if and only if $|G|$ is odd - since groups generated by elliptic groups are finite, and since addition is the group operation, then $2*P = P + P$ , which is analogous to $P^2$.

$\endgroup$
  • 1
    $\begingroup$ It may of interest to note that $\gcd(q,k)=1$ needs to hold if one wants to divide a point by $k$ in a (sub-)group of order $q$ (the order having to be even for halving follows from that). $\endgroup$ – SEJPM Dec 29 '18 at 10:23
  • $\begingroup$ A couple of clarifying questions: (1) do you mean section 3.6.1 in the book (I don't think section 3.8.1 exists there)? (2) for points that exist in odd subgroups of $G$ are there always two solutions? I'm assuming only one of them could be found using the algorithm, but the second solution still exists - right? $\endgroup$ – irakliy Jan 6 at 8:56
  • $\begingroup$ 1)Algorithm 3.8.1 in section 3.6.1. I’ll change the answer to reflect that. 2)Points that can be halved will always only have one solution. $\endgroup$ – hlz2103 Jan 6 at 9:56
  • $\begingroup$ I'm sorry, I'm not sure I fully understand. It seems like for any point $A$ which can be halved such that $A = 2 \cdot A_1$ there should exist another point $A_2$ such that $A = 2 \cdot A_2$. And the relation between these points is that if $A_1 = a \cdot G$ then $A_2 = (a + \frac{q}{2}) \cdot G$. Or am I missing something? $\endgroup$ – irakliy Jan 7 at 6:41
  • 1
    $\begingroup$ But they both require a lot of background knowledge. I do intend to come back to this answer and give a more thorough response, but I need to do some reading first. $\endgroup$ – hlz2103 Jan 11 at 15:07

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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