2
$\begingroup$

Consider a Koblitz elliptic curve over a prime field $\mathbb F_p$, with equation $y^2=x^3+b$, prime order $n$ close to (but different from) $p$. This includes secp256k1, secp224k1, secp192k1, secp160k1, and for a toy example $p=241,b=13,n=211$.

Given $(x_P,y_P)$ for $P$ on the curve, classic point doubling formula allows to compute coordinates $(x_Q,y_Q)$ for $Q=[2]P$.

What are explicit formula or algorithm to compute $(x_P,y_P)$ from $(x_Q,y_Q)$, faster than the obvious point multiplication $P=[(n+1)/2]Q$ ?


This is a special case of Elliptic Curve - Divide by 2, which has no satisfactory answer with explicit formula.

$\endgroup$
1
  • $\begingroup$ This paper from Feb '23 (paying particular attention to example 2) should give formulae which only require the extraction of square roots and the usual arithmetic operations. $\endgroup$
    – Daniel S
    Commented Nov 10, 2023 at 12:29

1 Answer 1

2
$\begingroup$

Point halving in Secp256k1 - the others are similar.

Let $P = [\frac a 2]G$ i.e. we have $[2]P = [a]G = Q$. In words, $P$ is the halfpoint of $Q$.

Let $P = (p_x,q_x)$ and $Q = (q_x,q_x)$

We may expect that it has two solutions $$P =\big[\frac{a}{2}\big]G =\big[\frac{a + q}{2}\big] G \left(= \big[\frac{a}{2}\big] G + \big[\frac{ q}{2}\big] G \right), $$ however, the base point $G$ of the Bitcoin curve has odd order;

int("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141", 16)
115792089237316195423570985008687907853269984665640564039457584007908834671663

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

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

$$y-p_y = \lambda(x-p_x) => 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{r3}$$

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

    If we extend the equation \ref{r3}, we will get a monic cubic polynomial, so the coefficient of $x^2$ will be minus the sum of the roots (Vieta's Formula ($-b/a$)), and the leading coefficient is 1.

    \begin{align} x^{3} + 7 & = (\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^{2} \\ x^{3} + 7 & = \lambda^2 (x^2 - 2 x p_x + p_x^2) + 2 \lambda x p_y - 2 \lambda p_x p_y + p_y^{2} \\ 0 &= x^{3} + 7 - \lambda^2 (x^2 - 2 x p_x + p_x^2) - 2 \lambda x p_y + 2 \lambda p_x p_y - p_y \\ 0 &= x^{3} \color{red}{- \lambda^2 x^2} + \lambda^2 2 x p_x - \lambda^2 p_x^2 - 2 \lambda x p_y + 2 \lambda p_x p_y - p_y^{2} + 7\\ 0 &= x^{3} \color{red}{- \lambda^2 x^2} + (\lambda^2 2 p_x - 2 \lambda p_y)x + (- \lambda^2 p_x^2 + 2 \lambda p_x p_y - p_y^{2} + 7)\\ \end{align}

    as we can see the term for $x^2$ is $- \lambda^2$. Since the roots are the intersection point then $p_x$ will be a double point and $q_x$ will be a single point, by Vieata's formula $$\lambda^2 = 2 p_x + q_x \label{r4}\tag{4}$$

  2. Form equation using equation \ref{r4} and and replacing $x$ with $p_x$ in the equation \ref{r1};

    $$\lambda^{2} = 2p_x + q_x = \frac{9p_x^{\,4}}{4(p_x^{\,3} + 7)} \tag{5} \label{r5}$$

    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.


The validation with SageMath

#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

Try, online on SageMathCell

Note that this is a single test.

$\endgroup$
9
  • 1
    $\begingroup$ For prime curves, all points can be generator, so it is not matter which one we choose and I did not used the value of the base point. Because we combined the curve and the tangent line, so there is expected one linear solution. $\endgroup$
    – kelalaka
    Commented Oct 5, 2023 at 18:06
  • $\begingroup$ I admit I do not know how to solve $-p_x^{\,4}+4p_x^{\,3}q_x+56p_x+28q_x=0$ for $p_x$. Also, I see no reason it has a single solution, so we need a strategy to select the right $p_x$, and also to select $p_y$. Update (Nov 8): the code shows there is indeed a single solution. My intuition was bad! $\endgroup$
    – fgrieu
    Commented Nov 1, 2023 at 7:38
  • $\begingroup$ @fgrieu My calculations are per this article. My formulas do not verify yet. I'm reviewing all, from time to time. Quartic roots may be hard to use, however, I've used a library for the ray-tracing for the torus. I'm considering that the paper and my calculation are not correct. I'll look deeper. In the end, we can talk about performance about directly using scalar vs this. $\endgroup$
    – kelalaka
    Commented Nov 2, 2023 at 13:07
  • 1
    $\begingroup$ @fgrieu Ok. I've validated the formulas with SageMath. More explanation will come later. $\endgroup$
    – kelalaka
    Commented Nov 7, 2023 at 20:44
  • $\begingroup$ @kelalaka Thank you for the code. However, when I compare its speed with the traditional $P=[\frac{(n+1)}{2}]Q$ algorithm it reports that the second method is 6-7 times faster. Am I missing something? Is it the case that your method is efficiently parallelizable while the second method is not? $\endgroup$ Commented May 28 at 12:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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