As I am studying ordinary (non-supersingular) binary elliptic curves in the Guide to ECC book by Hankerson (Section 3.1, page 81), for point doubling, the equations presented in the book are:

$x_3 = \lambda^2 + \lambda + a = {x_1}^2 + \frac{b}{{x_1}^2}$

$y_3 = {x_1}^2 + (\lambda + 1) x_3 $

$\lambda = x_1 + y_1/x_1$

I have some questions to confirm my understanding, and I really appreciate elaboration on this:

  1. To my understanding, $\lambda$ is a gradient. Then, if I have the information about the result of point doubling (i.e., $x_3, y_3$), can I calculate $\lambda$ as $\lambda = x_3 + y_3/x_3$ instead of $\lambda = x_1 + y_1/x_1$? Or isn't it possible, and I should use other equations (like point halving? But I can not find the formula in the book).

  2. Unrelated to the above question, the value of $a$ and $b$ is always known, right? So for calculating $x_3$, I can use either $\lambda^2 + \lambda + a$ or ${x_1}^2 + \frac{b}{{x_1}^2}$ and it will always be correct. Is that true?


1 Answer 1

  1. One can think of $\lambda$ as the (formal) gradient of the tangent to the curve at the point $(x_1,y_1)$, but this will not be the same as the gradient of the tangent to the curve at the point $(x_3,y_3)$. You should instead use the formulae for point halving (see pages 7-8 of this paper by Pornin for example).

  2. Yes, that is correct. To see the equivalence note that by the curve equation $$y_1^2=x_1y_1+x_1^3+ax_1^2+b$$ so that $$\lambda^2=x_1^2+\frac{y_1^2}{x_1^2}=x_1^2+\frac{y_1}{x_1}+x_1+a+\frac b{x_1^2}$$ and $$\lambda^2+\lambda+a=\left(x_1^2+\frac{y_1}{x_1}+x_1+a+\frac b{x_1^2}\right)+\left(x_1+\frac{y_1}{x_1}\right)+a=x_1^2+\frac b{x_1^2}.$$

  • $\begingroup$ Thank you very much for your response! I will look into that. One question, just realized I have come across the paper previously, but I thought that the paper was not very "authoritative" because the equation for Point Doubling is slightly different (i.e., $y_3 = \lambda (x_1 + x_3) + x_3 + y_1$) than Hankerson's (see Page 7 about Point Addition (and point doubling)). It looks like a point addition equation to me. Would you say that the paper is a good reference to study binary elliptic curves? $\endgroup$
    – prairie99
    May 16, 2023 at 9:22
  • 2
    $\begingroup$ I am happy to endorse the Pornin paper as an good reference for the study of binary elliptic curves. The different form of the addition equation again follows from straightforward identities. $\endgroup$
    – Daniel S
    May 16, 2023 at 9:26
  • $\begingroup$ Then, does it mean I can use the above equation interchangeably with Hankerson's, right? Thank you very much for your explanation! I was afraid that the Point Doubling will have different characteristics so that I can't use $y_1$ for that. $\endgroup$
    – prairie99
    May 16, 2023 at 9:27
  • 2
    $\begingroup$ @prairie99: I second the recommendation for the Pornin paper when the goal is efficiency and constant-timeness (that's independently of The Bear being our user#28). [update] The formulas page 7 should be OK (it's only later that the paper proposes a coordinate system that I think is new, and definitely leads to formulas different from the formulas for Cartesian coordinates). $\endgroup$
    – fgrieu
    May 16, 2023 at 9:28

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.