Elliptic

Elliptic.md

Basic Group Structure of Elliptic Curves

We quickly go over various concepts in the study of elliptic curve groups. This records everything notable during my couse of study.

0. Projective Plane

When studying algebraic curves, it is often necessary to introduce an extension of the plane $\mathbb F\times\mathbb F$, by introducing an auxiliary variable $z$, to make the equation homogeneous, e.g. $$y^2z=x^3+axz^2+bz^3.$$ Now we can consider the triplet $(x:y:z)$ as a ratio. This adds the case where $z=0$ to the curve, which eases the analysis in the future. We call this extended space the projective plane $\mathbb{PF}^2$.

When viewed in the 3-dimensional space, $\mathbb{PF}^2$ is equivalent to all straight lines passing through the origin of the space. By setting $z=1$, we are effectively obtaining a section of the lines. Those that are parallel to the plane $z=1$ are considered to be the points at infinity. However, there is nothing to stop us from using a different plane, say $x+y+z=1$. In this case, we can set up coordinates on the new plane: $$\left{\begin{aligned}u&=x-y+z,\v&=x+y-z,\(w&=x+y+z=1).\end{aligned}\right.$$ (Of course, as long as theyare linear in the original coordinates, any is possible.) Making use of the equation of the plane, we can invert the coordinates: $$\left{\begin{aligned}2x&=u+v\2y&=w-u\2z&=w-v.\end{aligned}\right.$$ When turning back to affine coordinates, they become linear fractional transforms.

I. Elliptic Curves

We need to define elliptic curves first.

Definition. An elliptic curve is a non-singular algebraic curve over some field $\mathbb F$ of the form $$y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6,$$ where the variables $x,y$ and the coefficients $a_i$ belong to $\mathbb F$.

Usually, if the characteristic of the field is not $2$ or $3$, we can always perform a projective coordinate change and obtain the Weierstrass standard form: $$y^2=x^3+ax+b.$$

In the standard form, we can state the non-singularity as the non-vanishing of its discriminant $$\Delta=-16(4a^3+27b^2).$$ The coefficient $-16$ here is included as standard.

We usually consider the curve in a projective sense. Also, we may make use of the algebraic closure $\mathbb{\hat F}$ of the original field, so that Bezout's theorem always holds.

II. Group structure

Suppose we are given a non-singular curve $E: y^2=x^3+ax+b$. We can define a group operation $+$ on the points of $E$. First we specify the identity to be $O(0:1:0)$, which can be easily confirmed to be on the curve. Second, for any three $P,Q,R\in E$ that lies on a straight (projectivized) line, we say that $$P+Q+R=O.$$

What can we see from this definition? First we note the special case where one of the points is $O$ itself. This necessarily means that the straight line $\ell$ lies vertically. By the symmetry of the curve, the other two points is symmetric with respect to the $x$-axis. Therefore, we see that the inverse of each point is well defined, and we write the inverse of $P$ to be $-P$.

Next, we consider the case where no two points are the same. The slope of the straight line would then be $$k=\frac{y_P-y_Q}{x_P-x_Q}.$$ Thus, the line $\ell$ has equation $$\ell: y=k(x-x_P)+y_P.$$ We could then solve for the coordinates $(x,y)$. However, Viete's theorem provides a much simpler way. We first eliminate $y$ to obtain a cubic equation of $x$. The cubic coefficient is just $1$, and the quadratic one is $-k^2$. Therefore the three solutions of the equation sum to $k^2$. Since $P$ and $Q$ already are two of the intersections, we see that the new point $R$ has $x$ coordinate $$x_R=k^2-x_P-x_Q.$$ Now we can substitute this into the equation for $\ell$, and obtain $$y_R=k^3-2kx_P-kx_Q+y_P.$$

Another advantage of utilizing Viete's theorem is that no radicals appear in the expression, highlighting the fact that the third point is still on $E$ over $\mathbb F$, even if the field is not algebraically closed.

However, when the two given points are the same, how should we obtain a line? Here we should view the line as the limit of chords -- the tangent line. It is notable that this can be carried out and preseve the group structure, even when there is no differential structure available. We take the formal derivative of the curve, and get $$k=\left.\frac{\mathrm dy}{\mathrm dx}\right|_P=\frac{3x_P^2+a}{2y_P}.$$ We can then apply the calculation above, with the new definition of $k$.

For the sake of completeness, we claim that $O+O=O$. This can be calculated from the formal derivative of the projectivized curve at $O$, or intuitively viewed as a limit as the tangent point moves toward infinity.

The commutativity of the operation is evident from the definition. Now we have just to prove the associativity, $P+(Q+R)=(P+Q)+R$. This can be proven by carefully inspecting all the cases, and perform direct computation.

III. Examples

Let's take a look at some examples. They will be over various fields, and we will also see a simple application of the theory so far.

1. Over $\mathbb R$

Consider the curve $$C_1(\mathbb R): y^2=x^3-3x+6.$$ We note that $A(1,2), B(-2,-2)$ both lie on the curve. We compute, as an example, $A+B$ and $2B$.

Since $A$ and $B$ are different points, we can compute $k_{AB}$ using the first method, giving $$k_{AB}=\frac{-2-2}{-2-1}=\frac43.$$ Then by the formula for the coordinates, we get $$x_{-(A+B)}=\frac{25}9$$ and $$y_{-(A+B)}=\frac{118}{27}.$$ Therefore we have $$A+B=\left(\frac{25}9,\frac{118}{27}\right).$$

For $2B\equiv B+B$, we need to compute the slope of the tangent $$k_B=\frac{3\cdot(-2)^2+(-3)}{2\cdot (-2)}=-\frac94.$$ Plugging in the formulae, we obtain $$2B=\left(\frac{145}{16},\frac{1721}{64}\right).$$

2. Over $\mathbb F_7$

We consider again the same curve, but in a finite field: $C_1(\mathbb F_7)$. Directly enumerating all $49$ possible points (excluding the points at infinity, in which we know only $O$ is on the curve), we can list the elements of the curve. In particular, there are the following points: $(1,2)$, $(1,5)$, $(2,1)$, $(2,6)$, $(4,3)$, $(4,4)$, $(5,2)$, $(5,5)$, $(6,1)$ and $(6,6)$. Naming them $A_1$ to $A_{10}$, respectively, we can see that $A_1+A_2=O$, $A_1+A_3=A_7$, $A_1+A_1=A_8$, etc. Further, we can write out the whole addition table, and see that this group is in fact isomorphic to the cyclic group of order $11$¹. In particular, the multiples of the generator $A_1$ gives the sequence $O$, $A_1$, $A_8$, $A_4$, $A_{10}$, $A_6$, $A_5$, $A_9$, $A_3$, $A_7$, $A_2$, $O$...

The elliptic groups over finite fields play an important role in ECC encryption.

3. Over $\mathbb C$

If we simply switched the underlying field, the theory would be too mundane. Fortunately, there is a special function, the Weierstrass function, $\wp(z)$, that has a special property, making it inseparable with elliptic curves: $$\wp'(z)^2=4\wp(z)^3-g_2\wp(z)-g_3,$$ where $\wp'$ is the complex derivative, and $g_2, g_3$ are parameters. This makes the pair $(\wp,\wp')$ a parameterization of an elliptic curve.

We first define this function.

Definition. The Weierstrass elliptic function is a complex holomorphic function defined by the infinite series $$\wp(z;\omega_1,\omega_2)=\frac1{z^2}+\sum_{n^2+m^2\ne0}\left(\frac1{(z+m\omega_1+n\omega_2)^2}-\frac1{(m\omega_1+n\omega_2)^2}\right).$$

Here the sum can also be denoted as $\sum'$.

Differentiating this function term by term, and comparing the terms, we can see that the differential equation indeed holds, if $$g_2={60}\sum{^{'}}(m\omega_1+n\omega_2)^{-4}$$ and $$g_3={140}\sum{^{'}}(m\omega_1+n\omega_2)^{-6}.$$

Since it is evident that this function is doubly periodic, The parameter thus runs over a torus. By means of the Jacobi function, we can calculate the fundamental region back from $g_2$ and $g_3$.

For example, our curve

4. A simple application: Diophantine equations

Let's consider an equation with integral unknowns, $$\frac a{b+c}+\frac b{a+c}+\frac c{a+b}=4.$$ Although this looks unrelated to elliptic curves, we can establish the connection by turning this into a polynomial equation, and do a change of variables². The first step proceeds by multiplying both sides with the denominators: $$(a^3+b^3+c^3)-3(a^2b+ab^2+\text{four similar terms})-5abc=0.$$ Now, this is a homogeneous equation with degree $3$! This means we can find 'points at infinity' where $c=0$. There are three of them, but two are not rational. We want rational solutions, because since the equation is homogeneous, we can always multiply out the denominators to obtain integral values. The only rational point at infinity is $(1:{-1}:0)$.

This begins to look a bit like elliptic curves. We try and find some more points. The first few are $(0:{-1}:1)$, $({-1}:0:1)$ -- these follow from the symmetry of $a,b,c$ -- and $(1:1:{-1})$.

However, they are not even close to a solution. These are produced in the first step, where we multiply the equation with its denominator. Back in the original equation, these solutions causes zero division.

Do not give up! We are about to make a crucial change. Notice that the first three points we found are all inflection points. Intuitively, the tangent lines passes from one side of the curve to the other at that point. More rigorously, the tangent line has a tangent point of multiplicity greater than $2$ (by Bezout's theorem, this implies that the multiplicity is exactly $3$). This is necessary for a point to be an identity, since $O+O=O$. We now seek to find some transformation that brings the curve to be an elliptic one.

First, note that the curve, over the reals, has three points at infinity, each $60^\circ$ apart. This is not a charateristic of elliptic curves, and we want to remove these, by doing a coordinate change that takes two of them to the finite plane. At the same time, we want to keep $O=(1:{-1}:0)$ at infinity, since we are choosing it to be the additive identity. Therefore, introducing a parameter $t$, we consider planes of the form $$a+b+tc=1.$$ This expression is obvious when one draw this family of planes in three-dimensional space: they revolve around an axis in the direction of $O$³. On these planes, we want to make $O$ lie on the direction of the $y$-axis, by convention. Therefore, we choose the coordinates on the plane: $$\left{\begin{aligned}x_1&=a+b-tc\y_1&=a-b+tc\z_1&=a+b+tc.\end{aligned}\right.$$ I admit that I chose this purely out of aesthetic purposes. But such arbitrariness will be eliminated as we proceed. As long as the requirements stated above are satisfied, any other coordinate is acceptable.

Inverting the coordinates, we get $$\left{\begin{aligned}a&=\frac{x_1+y_1}{2}\b&=\frac{z_1-y_1}2\c&=\frac{z_1-x_1}{2t}.\end{aligned}\right.$$

Substituting, the curve becomes $$\begin{aligned} -&2 t^2 x_1 y_1 z_1\ &+\left(t^3+3 t^2-3 t-1\right) x_1^3\ &+\left(6 t^3+t^2\right) x_1^2 y_1\ &+\left(-3 t^3+2 t^2+3 t+3\right) x_1^2 z_1\ &+\left(6 t^3+t^2\right) x_1 y_1^2\ &+\left(-3 t^3-2 t^2+3 t-3\right) x_1 z_1^2\ &+\left(6 t^3-t^2\right) y_1^2 z_1\ &+\left(t^2-6 t^3\right) y_1 z_1^2\ &+\left(t^3-3 t^2-3 t+1\right) z_1^3=0. \end{aligned}$$ Miraculously, the $y^3$ term disappeared!! This is a good sign. We conclude that making $O$ lie at $(0:1:0)$ produces a $y^3$-free curve.

We now impose another obvious condition on our curve: we require it to be symmetric with respect to the $x$-axis. This is not yet true, and the curve is 'slanted', due to the appearance of odd order $y_1$'s. We want to eliminate those with a so-called 'sheer' transformation. Switching to affine coordinates, the general form of such transformation is: $$\left{\begin{aligned}x_2&=x_1\y_2&=y_1+sx_1-d\end{aligned}\right.,$$ where $s,d\in\mathbb Q$ are parameters. Expanding (!) we get $$x \left(6 d^2 t^3+d^2 t^2-12 d s t^3+2 d s t^2+2 d t^2-6 s t^3+s t^2-3 t^3-2 t^2+3 t-3\right)+6 d^2 t^3-d^2 t^2+x^2 \left(-12 d s t^3-2 d s t^2-6 d t^3-d t^2+6 s^2 t^3-s^2 t^2-2 s t^2-3 t^3+2 t^2+3 t+3\right)+x y \left(-12 d t^3-2 d t^2+12 s t^3-2 s t^2-2 t^2\right)+6 d t^3-d t^2+y \left(-12 d t^3+2 d t^2-6 t^3+t^2\right)+x^3 \left(6 s^2 t^3+s^2 t^2+6 s t^3+s t^2+t^3+3 t^2-3 t-1\right)+x^2 y \left(12 s t^3+2 s t^2+6 t^3+t^2\right)+t^3-3 t^2+\left(6 t^3+t^2\right) x y^2+\left(6 t^3-t^2\right) y^2-3 t+1$$

IV. Shoof's Algorithm

In the second example above, we calculated the points by enumerating all the elements of the plane. This is inefficient for large finite fields. Here, we introduce a method to count all the points on an elliptic curve that is relatively more efficient. This information is important when using a specific elliptic curve for cryptographic purposes, as the number of points directly determines the difficulty of hacking the encryption.

V. Further structures of the Curve over $\mathbb Q$

VI. Modularity

Footnotes

1. Ok, this particular fact is obvious once you see that there are $11$ elements. ↩

2. We can perform the group addition without transforming it into an elliptic curve, though. This works with every curve of genus $1$. ↩

3. We missed out the plane of $c=1$, if we want to do a full rotation, but this is no coordinate change, and thus we do not consider it. Also the $1$ on the RHS can be chosen as an arbitrary non-zero (rational) number, as this would only scale our curve. Scaling will be performed later anyway. ↩