Is there an efficient formula for computing point halving on elliptic curves in $\operatorname{char}F=p\ne2$?

Question

Consider the elliptic curve in $F_p$ and let $n$ be the order of the group.

1. Suppose the curve is the same as bitcoin: $y^2 = x^3 + 7$, I have a point $P=(x,y)$，how to compute $\frac{1}{2}P$.

2. Suppose $P=aG$ for some base point $G$(we know the points $P,G$, but the coefficient $a$)，then is there efficient method to compute $\lfloor\frac{a}{2}\rfloor$G

Answer 1

Case $P = \lfloor \frac a 2 \rfloor G$;

As said in the comments if possible this can help to break the DLog.

Case $P = \frac a 2 G$;

We may expect that it has two solutions $$P =\frac{x}{2} \cdot G =\frac{x + q}{2} \cdot G$$, however, the base point $G$ of the bitcoin curve has odd order. Therefore

int("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141", 16)
115792089237316195423570985008687907852837564279074904382605163141518161494337

Therefore if there exists half of a point then it is unique.

1. The derivative of the equation $y^2 = x^3 + 7$

$\lambda = \dfrac{3x^{2}} {2(x^{3} + 7)^{1/2}} \tag{1} \label{1}$

2. Write down the equation for the tangent line to $E$ at G:

$$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} + 7 \tag{3}\label{3}$$

4. Write down $\lambda$ in terms of $p_x$:

   If we extend the equation \ref{3} we will get a monic cubic polynomial, so the coefficient of $x^2$ will be the minus the sum of the roots. Therefore, $p_x$ will be double and $g_x$ will be a single root. $$(\lambda (x - p_x) + p_y)^{2} = x^{3} + 7$$ $$\lambda^2 (x - p_x)^2 + 2 \lambda (x - p_x) p_y + p_y = x^{3} + 7$$ as we can see the term for $x^2$ is $\lambda$. Since the roots are the intersection point then $p_x$ will be a double point and $g_x$ will be a single point, so $2 p_x + q_x = \lambda^2$ $$\lambda^2 = 2 p_x + q_x \label{4}\tag{4}$$

5. Form equation using equation \ref{4} and and replacing $x$ with $p_x$ in the equation \ref{1};

   $$\lambda^{2} = 2p_x + q_x = \dfrac{9p_x^{4}}{4(p_x^{3} + 7)} \tag{5} \label{5}$$ Simplify this equation and move everything over to the left-hand side will yield $$ (2p_x + q_x)(4(p_x^{\,3} + 7)) = 9p_x^{\,4}\\ -p_x^4 + 4 p_x^3 q_x + 56 p_x + 28 q_x= 0$$ a quartic polynomial in $p_x$. The roots of this polynomial are the x-coordinates of the half points of $G$. We are in the odd case, the factors of the quartic polynomial will be a linear equation and an irreducible resolvent cubic.

Small, SageMath Validation;

#Secp256K1 prime
p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
#Secp256K1 order
q =  115792089237316195423570985008687907852837564279074904382605163141518161494337
#One of the roots
t = 82764486716702815285605477501188164702466527314352175978120539775788537185277
print("Expected root ", t)


#define ring of polynomials
R.<x> = PolynomialRing(GF(p),'x')

# x-coordinate of Q where Q = [2]P
qx =  Integer(84538659774007663836420160802839342215744092791779235474817172502887599548487)


#From equation (5)
g = (2 *x + qx)*(4*(x^3+7)) - (3*x^2)^2

gRoots = g.roots()

print("The roots of quartic = ", gRoots)

gEvalAt_t = ((2 *t + qx)*(4*(t^3+7)) - (3*t^2)^2 ) % p

print( "gg(t) =", gEvalAt_t)

Outputs

Expected root  82764486716702815285605477501188164702466527314352175978120539775788537185277
The roots of quartic =  [(82764486716702815285605477501188164702466527314352175978120539775788537185277, 1)]
gg(t) = 0

---

Note: this result is similar to this article

• Quartic equations and 2-division on elliptic curves, George H. Hitching, 2018