Elliptic curves: point doubling

After the introduction of the first two simple point operations on elliptic curves in simple Weierstrass form, we can now look at some more interesting operations available to us. Last of the three "primitive" operations specified for points of the elliptic curve is the point doubling operation. It should be the same as if we wanted to sum not two distinct but rather two equal points. As usually, I would like to encourage anyone to give me a feedback, especially about the visualizations used.

To derive the formulas for performing point doubling on elliptic curve in simple Weierstrass form, we look at the formulas used for point addition[1] and think about what will happen if we move the two points we are adding infinitesimally close together. The line going through those points will become a tangent line touching the elliptic curve at given point. The situation can be seen in Picture 1.

Picture 1: Point doubling of the point $P\approx[-0.94,1.75]$ on the elliptic curve $y^2=x^3-2x+2$. Deriving the slope of the tangent line at given point is rather easy. First, we look at the elliptic curve in the $y>0$ domain and rewrite (just for this derivation) the elliptic curve as simple function: $y=\sqrt{x^3+ax+b}$ Here, the slope of a tangent to this function is the value of the derivative of this function at given point. Therefore we derive the derivative: $y'=\left(\sqrt{x^3+ax+b}\right)'$ Firstly, we rewrite the square root as fractional exponent: $y'=\left((x^3+ax+b)^{\frac{1}{2}}\right)'$ Secondly, we use the chain rule[2] of $\left(f(g(x))\right)'=\left(f'(g(x))\right)\cdot g'(x)$ to get the derivative function: $y'=\left(\frac{1}{2}(x^3+ax+b)^{-\frac{1}{2}}\right)\cdot(3x^2+a)$ And see what can be canceled-out: $y'=\frac{3x^2+a}{2(x^3+ax+b)^{\frac{1}{2}}}$ $y'=\frac{3x^2+a}{2\sqrt{x^3+ax+b}}$ Given that $y=\sqrt{x^3+ax+b}$, we can simplify it even more: $y'=\frac{3x^2+a}{2y}$ And also, as the $2y$ part contains proper sign, we do not need to derive the slope separately for $y<0$ as this formula will work for all $y$ values. Then we continue with calculating the intersection like we did with two distinct points: $d=\frac{3x^2+a}{2y}$ In the original formula for point addition we used the term $-P_x-Q_x$ but now we are left with only point $P$, therefore we need to use $-P_x-P_x$, which boils down to $-2P_x$: $R_x=d^2-2P_x$ The Y coordinate is calculated using the same formula as with point addition: $R_y=-P_y-d(R_x-P_x)$ And these are our formulas for point doubling on elliptic curve in simple Weierstrass form over $\mathbb{R}$. Now let's have a look into the same problem over $\mathrm{GF}(p)$.

Picture 2: Many smooth elliptic curves in the form $y^2=x^3-2x+2+23n, n\in Z$ wrapped around the finite field $\mathrm{GF}(23)$ in X, Y and Z coordinates. For elliptic curve in simple Weierstrass form over a finite field, the situation is more complex. We need to acknowledge that not only the X and Y coordinates are wrapped over the finite field, but the values of the elliptic function get wrapped as well. The full set of all curves actually involved is: $\forall l,m,n\in Z~\forall x,y\in\mathbb{R}: (y+lp)^2=(x+mp)^3+a(x+mp)+b+np$ Of course, only some of these curves hit the rational points of given finite field. You can see the visualization of few of them in Picture 2 and you definitely should see the Video 1 where it is displayed in detail.

When finding the tangent line for our doubling operation, we use a tangent line to the specific elliptic curve, which produced given rational point over the finite field.

Picture 3: Point doubling of the point $P=[12,21]$ on the elliptic curve $y^2=x^3-2x+2$ over the finite field $\mathrm{GF}(23)$. The tangent line and whole point doubling can be seen in Picture 3. In order to calculate the slope of the tangent line, all we need is to use the same formula, but instead of using the arithmetic division we use the multiplicative inverse of denominator over given finite field: $d=\frac{3x^2+a}{2y}$ $d=\left((3x^2+a\right)\mod p)\cdot\left((2y)^{-1}\mod p\right)\mod p$ Calculating the multiplicative inverse is out of scope of this article but you can look for decent explanation of the extended Euclidean algorithm for finding the greatest common divisor of two numbers, which is typically used for calculating the multiplicative inverse over a finite field $\mathrm{GF}(p)$.

Although this might look rather complex to an untrained eye, if you watch the second part of Video 1, you can see it really is as simple as walking the straight line on the torus and looking for rational points on the way.

Video 1: Point doubling on elliptic curve $y^2=x^3-2x+2$ over $\mathbb{R}$ and $\mathrm{GF}(23)$.  

Thank you for keeping up with our mini-series about elliptic curves and prepare for the ride to infinity next week! And yes, everything explained so far should lead to more secure communication - but we are not there yet.

References

1. https://trustica.cz/2018/03/15/elliptic-curves-point-addition/

2. Wikipedia contributors. (2018, March 18). Chain rule. In Wikipedia, The Free Encyclopedia. Retrieved 22:02, March 20, 2018, from https://en.wikipedia.org/w/index.php?title=Chain_rule&oldid=830985913