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

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

• Can you give the point doubling formula for this curve? Commented Dec 18, 2020 at 8:43
• Anyway, the answer to the second question is surely negative. For otherwise the DLP would be trivial :-) Commented Dec 18, 2020 at 8:56
• More seriously, if the order of $G$ is an odd number $\ell=2k-1$, then $\frac12aG$ exists for all $a$. This is because $\frac12 G=kG$. And if the order is even then $\frac12P$ either does not exist, or it has two possible answers. Again killing this line of attack to the DLP. Commented Dec 18, 2020 at 8:58
• There are researches on this Quartic equations and 2-division on elliptic curves. Also, you can see this post Point halving on elliptic curves of even order on Cryptography.SE Commented Dec 18, 2020 at 12:02
• What @Mummytheturkey said is, of course, correct. But in the crypto side, in characteristic two, there is something called "halve-and-add" -algorithm (in addition/contrast to the more common "double-and-add"). I don't remember the details, but it offered some advantage in some situation. Anyway, on an abelian group of odd order halving is a well-defined process :-) Commented Dec 19, 2020 at 5:48

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}$$

1. 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}$$

1. 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}$$

1. 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}$$

2. 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