0

Given an elliptic curve $E=\{ (x,y) \in \mathbb{F}_q^2 | y^2=x^3+ax+b \}$. Now deduce the general equation for doubling a point $P:=(x,y) \in E$.

---

Firstly I constructed the function f $f(x,y)=y^2-x^3-ax-b$. Then I tried to calculate there $\nabla f = (-3x^2-a,2y)$. The tangent line in $(x,y)$ is $(x+t*(-3x^2-a),y+t*2y)$ for a $t\in\mathbb{R}$. Then for a suitable t one gets $-(2P)=(x+t*(-3x^2-a),y+t*2y)$ and then by multiplicating the y-coordinate by -1 the double of P.

But when I plug the point -(2P) into the equation of the elliptic curve $y^2=x^3+ax+b$ I don't get a unique t out. I doubt if my solution works at all. How can I solve this?

unterbrause
  • 111
  • The tangent line touches the curve at $P$ as well as cutting it at $-2P$. So your equation has a single root at $-2P$ and a repeated root at $P$. Does this answer your question? – TonyK Mar 22 '14 at 11:06
  • Okay so far. The Problem is the following: This was asked on an exam. So there has to be a way of calculating this in an efficient way by hand. Is there no other way of deducing this doubling formula? – unterbrause Mar 22 '14 at 15:25
  • You made a fatal error! See my answer. – TonyK Mar 22 '14 at 16:37

1 Answers1

3

The tangent is perpendicular to $\nabla f$, not parallel to it: $$(x_P+2y_Pt, y_P+(3x_P^2+a)t)$$

Plug these values into the curve equation:

$$(y_P+(3x_P^2+a)t)^2 = (x_P+2y_Pt)^3+a(x_P+2y_Pt)+b$$

Expand all this out, and subtract the curve equation $y_P^2=x_P^3+ax_P+b$ itself, and you get

$$(3x_P^2+a)^2t^2=12x_Py_P^2t^2+8y_P^3t^3$$

Divide by the factor $t^2$ (which corresponds to the double root at $P$), and you get an equation linear in $t$, with root

$$t = \frac{(3x_P^2+a)^2-12x_Py_P^2}{8y_P^3}$$

Now just substitute this value of $t$ in the equation for the tangent.

Admittedly this is not something I would like to have to do in the pressure of an exam!

TonyK
  • 64,559