Introducing the Elliptic Curve

An elliptic curve is a non-degenerated cubic 2-D curve. In general, this is of the form:

ax^3+bx^2y+cxy^2+dy^3+ex^2+fxy+gy^2+hx+iy+j=0

Here a to j are constants, and a point (x, y) is on the curve if they satisfies the above equation. Although there are 10 coefficients, we should say the curve has 9 degree of freedom, because if we multiply all the coefficients by the same number it is still the same curve.

Let’s have some plots

Why is it called elliptic curve? Is the shape of such curves looking like an ellipse? Let us show a few examples. This is a simpler curve, which is a bit less funny.

cubic1

Not exactly very neat, but compare with the one below it is still quite ordinary. We simply have a more negative x coefficient:

cubic2.png

It is not two curves, it is one. Even though it contains two parts, one closed and another going far far away from the origin. But cubic curves are not limited to two components. This time we add a x^2 y term.

cubic3

This curve contains 3 components instead of just two. If you want to play with more such curves, you can search the web for some online plotting sites, and you can easily create many more examples.

That the curve can contain 3 components should not be too surprising: if we have three straight lines

a_1 x - y + b_1 = 0,
a_2 x - y + b_2 = 0, and
a_3 x - y + b_3 = 0,

then we can multiply all of them to give a “curve” containing exactly the three straight lines above:

(a_1 x - y + b_1)(a_2 x - y + b_2)(a_3 x - y + b_3) = 0

This expands to the above general form. So the general form of elliptic curve encompasses the “three straight line” case, and that can of course contains three disjoint components (three parallel straight lines).

Standardizing the elliptic curve

Having so many different forms make it hard to visualize the curve and to derive formulas. So we prefer something simpler. We will restrict our attention to cubic curves of the following form, called the Weierstrass standard form:

y^2 = x^3 + a x + b .

Traditionally there is a factor of 4 in the x^3 term, but we will drop it. The above form can be transformed to the traditional form by the transformation x = 4X, y = 4Y, which makes the above:

\displaystyle Y^2 = 4X^3 + \left(\frac{a}{4}\right)X + \frac b {64} .

Because this can be converted back with the transformation X = x/4, Y = y/4, the two forms are in a way equivalent.

Interestingly, any cubic curve can be transformed in a similar fashion to the above standard form. But instead of multiplying by a constant, we need a rational formula involving both x and y. So we don’t lose so much by considering only cubic curves of this standard form.

Let’s plot again. There can only be 4 possible forms. The curve may contain a single component:

standard1

Or it may contain two:

standard2

Or it may have a cusp:

standard3

Or it may have a node:

standard4

I hope you agree with me that it is a whole world simpler. The simplicity comes from the fact that we are essentially taking square root of a simple one-variable cubic function.

The last two cases are the “degenerated” cases that we said at the beginning that we would exclude. They happen when the discriminant of the cubic function is 0. But what is the “discriminant”? If the cubic function has three roots (counting multiplicity) \sigma_1, \sigma_2 and \sigma_3, the discriminant is (\sigma_1 - \sigma_2)^2(\sigma_2 - \sigma_3)^2(\sigma_3 - \sigma_1)^2. To say that it is not zero is equivalent to saying that no two roots coincide. For the cubic function in the standard form, the discriminant is given by:

\Delta = -4a^3 - 27b^2 .

I found it a fun exercise to verify it.

Elliptic Curve and Ellipse

Back to our original question. No, it definitely doesn’t look like an ellipse. Then why is it called “elliptic curve”? I will not give an answer here, as it diverts us too far from our aim to understand elliptic curve cryptography, and also as I don’t fully understand it. For interested readers, I’d suggest starting from the article in the Mathematics Magazine, called “Why Ellipses are not Elliptic Curves“. Here is a short summary for busy readers who however demand some ideas. If the following is too confusing for you to read, it is still okay: just skip over it, we will not need it.

  • Studying perimeters of ellipses give the elliptic integral, with no analytical evaluation.
  • We can slightly change the form of the integral to give other integrals with no way to evaluate analytically. Three kinds of such “standard” integrals are sufficient to express a large class of similar integrals arising from physical phenomenons.
  • Inverting one of the standard kind of elliptic integrals gives elliptic functions. They have very similar properties as trigonometric functions like sine and cosine.
  • But when extending such functions to the domain of complex numbers, such elliptic function has a property that is unlike sine and cosine: it is doubly periodic. (Trigonometric functions are periodic in the real direction, standard elliptic functions are periodic in both the real direction and the imaginary direction.) More than that: of all doubly periodic functions in the complex plane, only elliptic functions are holomorphic (i.e., differentiable everywhere except at points where the function becomes infinite).
  • One way to build such doubly periodic function is to have an infinite series of two dimensions. E.g., to generate a function of periods z_1 and z_2, we can use \sum_{m\in \mathbb{Z}} \sum_{n\in \mathbb{Z}} f(z + mz_1+nz_2), where the function f is chosen to be a simple holomorphic function that makes the series converge for most numbers.
  • One of the standard form of such series sum, called the Weierstrass elliptic function \wp(z), is found to be most useful and can generate all the possible elliptic functions.
  • It is also found that \wp(z) satisfies \wp'(z)^2=4\wp(z)^3+g_1\wp(z)+g_2. Put it another way, (x, y)=(\wp(z), \wp'(z)) is on the cubic curve y^2 = 4x^3 + g_1x + g_2. So such curves are called elliptic curves.

It is lucky that they are none of our business. We instead want to know what we can do with the elliptic curve, in a way related to making better discrete logarithms. What we need is to intersect the curves with straight lines.

September 2017
Isaac To

Prev: DH review    Up    Next: EC and Line