Point halving on elliptic curves of even order

Question

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?

Answer 1

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_y) \quad\implies\quad 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}}{4(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} \iff 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} \iff Q$ is a singularity.