8
$\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$
4
$\begingroup$

Supposed $Q = (q_x,q_y)$ is a point on elliptic curve $E$ defined by $y^{2} = x^{3} + ax^{2} + bx + c$. To find the half point $P$ of $Q$, we need to do the following:

  1. Write down the equation for the derivative of $E$ at $P$. letting $\lambda$ be the derivative, we have
    $\lambda = \dfrac{3x^{2} + 2ax + b} {2(x^{3} + ax^{2} + bx + c)^{1/2}} \tag{1} \label{1}$
  2. Write down the equation for the tangent line to $E$ at $P$:
    $y-p_y = \lambda(x-p_1) => y = \lambda(x - p_x) + p_y \tag{2}$.
  3. Write the equation for the intersection of the tangent line with E:
    $y^{2} = (\lambda(x - p_x) + p_y)^{2} = x^{3} + ax^{2} + bx + c \tag{3}$.
  4. Write down $\lambda$ in terms of $p_x$:
    The equation from (3) comes out to a monic cubic polynomial. Since it is monic, the sum of the roots add up to minus the coefficient of $x^{2}$. The roots are the intersection points. Hence $p_x$ will be a double root, and $q_x$ will be the third root. If you simplify this equation, you will see that the coefficient of the $x^{2}$ term is $a - \lambda^{2}$. Therefore $2p_x + q_x = \lambda^{2} - a $ and so $\lambda^{2} = 2p_x + q_x + a \tag{4} \label{4}$
  5. Set equation from (4) and equation from (1) equal to eachother.
    Combining equation $\eqref{4}$ with the equation for $\eqref{1}$ and replacing $x$ with $p_x$, we get
    $\lambda^{2} = 2p_x + q_x + a = \dfrac{(3p_x^{2} + 2ap_x + b)^{2}}{2(p_x^{3} + ap_x^{2} + bp_x + c)} \tag{5} \label{5}$.
    Simplifying this equation and moving everything over to the left hand side will yield a quartic polynomial in $p_x$. The roots of this polynomial are the x-coordinates of the half points of Q..

The relationship between the half points of $Q$ is the same as the relationship between the roots of $\eqref{5}$. It will change depending on the nature of $E$. Here are a few things we can say for certain.

  1. Since neither $q_y$ nor $p_y$ make an appearance in this quartic polynomial, each quartic polynomial will actually give the halves for two separate points. The quartic from $\eqref{5}$ gives us the half points of $Q = (q_x,q_y)$ as well as the half points of $-Q=(q_x,-q_y)$.

  2. To find out if a half point exists for a point $Q$, there is a value you can calculate based on $a,b,c$ of $E$ and $q_x$. This procedure can be found on page 5 of Quartic Equations and 2-division on Elliptic Curves (Most of the results from this answer are directly from this paper).

  3. If the points on E make up an odd ordered group, then each point $Q$ only has one point $P$, and hence the quartic equation will only have one root. This follows from the fact that elements in odd groups have unique square roots.In this case, the factors of the quartic polynomial will be a linear equation and an irreducible resolvent cubic.

  4. Equation (5) is equal to $(x-s)^{2}(x-t)^{2} <=> Q$ is a 2-torsion point. In this case, $Q$ will have two distinct halves, one where $x=s$ and another where $x=t$. $-Q$ will also have halves with these x-coordinates.

  5. Equation (5) is equal to $(x-s)^{4} <=> Q$ is a singularity.
$\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
  • 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
  • 1
    $\begingroup$ @irakliy - I updated the answer with more info. $\endgroup$ – hlz2103 Jan 22 at 2:29

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.