Number theory | Minimalist Mathematician

Category: Number theory

This post aims to clarify some of the background on elliptic crves over finite fields. I want to give some intuition on what an elliptic curve is, where the point at infinity comes from, and some cool things you can do with elliptic curves. In this post, we are working over a field $K$ , and its multiplicative group $K^*$ .

Elliptic curves are defined over the projective plane $\mathbb{P}$ . Simply put, on a regular plane, parallel lines never intersect. The projective plane can be thought of as a regular plane, with an extra point called the point at infinity where parallel lines intersect. We need to define what we mean by a curve on $\mathbb{P}$ . We need that if $(x : y : z)$ is on the curve, then $(\lambda x : \lambda y : \lambda z)$ also is, for all $\lambda \in K^*$ . In particular, if $F(x, y, x) = 0$ is the equation of a projective curve, then $F$ must satisfy $F(x, y, z) = 0 \Rightarrow F(\lambda x, \lambda y, \lambda z) = 0$ . So $F$ needs to be a homogeneous polynomial.

For now, we will assume that $char(K) \neq 2, 3$ , that is, $1 + 1 \neq 0, 1 + 1 + 1 \neq 0$ . Then one can simplify the general homogeneous polynomial of degree 3 as follows: $F(x, y, z) = ax^3 + bx^2y + cx^2z + \dots = yz^2 - x^3 - Axz^2 - Bz^3$ . You can see that this looks similar to the equation for an elliptic curve I gave last time.

First, we want to find the point at infinity. We want $F(x, y, z) = 0$ , and we know that the point at infinity is where $z = 0$ . But this implies that $x = 0$ , so the point at infinity is $(0 : 1 : 0)$ , since scalar multiples are the same point. We call this point $O$ , and it is on every elliptic curve.

The one additional condition we place on an elliptic curve is that the points must be non-singular. This means that $\nabla F(x : y : z)$ is non-zero. Again, we work with $F(x, y, x) = y^2z - x^3 - Axz^2 - Bz^3$ . We can calculate $\frac{\partial F}{\partial x} = -3x^2 - Az^2, \frac{\partial F}{\partial y} = 2yz, \frac{\partial F}{\partial z} y^2 - 2Axz - 3Bz^2$ . Then we have that $\nabla F(0, 1, 0) = (0, 0, 1)$ , which is non-zero. Hence the point at infinity is on every elliptic curve.

Now, let’s get back to finding the equation of a general elliptic curve. For all the affine points, $z \neq 0$ . Hence $F(x, y, z) = \frac{1}{z^3} F(x, y, z) = 0$ . Thus $(\frac{y}{z})^2 = (\frac{x}{z})^3 + A(\frac{x}{z}) + B \Rightarrow \tilde{y}^2 = \tilde{x}^3 + A\tilde{x} + B$ . This is called the $\emph{affine equation}$ of an elliptic curve. Now we have almost managed to properly define elliptic curves.

For the affine points, we have that $y^2 = x^3 + Ax + B$ . Hence a point $(x, y)$ is non-singular if and only if $3x^2 = A \neq 0$ or $2y \neq 0$ . Using this, we can deduce that the equation defines an elliptic curve if and only if $4A^3 + 27B^2 \neq 0$ . We call $A^3 + 27B^2 = \Delta$ the discriminant of the elliptic curve.

To finish up, I will mention two applications of elliptic curves. They can be used to share a secret key with a similar method as the discrete logarithm Diffie-Hellman key exchange. They can also be used to factor large integers, using an algorithm called Lenstra Elliptic Curve Factorisation. This method is based on adding points of elliptic curves. A basic outline of the algorithm is as follows. Given an integer $n$ , choose an elliptic curve $E$ over $\mathbb{F}_n$ and a point on this curve. Add this point to itself until calculating the sum gives a non-invertible denominator $d$ . Then applying Euclid’s Algorithm, you get $gcd(n, d) \neq 1$ as a non-trivial factor of $n$ .

April 28, 2014

Elliptic Curves – Part 1

I first came across the term elliptic curves when I was 12 and we watched a documentary about how Andrew Wiles proved Fermat’s Last Theorem. The documentary is one if the main reasons I decided to study mathematics. Up to that point I never really understood that there was research going on in mathematics. Unfortunately, I can’t remember the name of this film, but it mentioned something that has fascinated me since then: elliptic curves.

In the film they were portrayed as some magical, mysterious mathematics that one needed a PhD and 7 years of solitary study to understand. I’m sure that is correct, but I plan on giving you only some basic intuition, not complete understanding, on elliptic curves here.

First of all, elliptic curves are not ellipses. They did however arise when mathematicians studied some problems in classical geometry about ellipses, hence the name. An elliptic curve is a relation $y^2 = x^3 + Ax + B$ . Graphed over the real numbers, an elliptic curve looks like any of these pictures.

Some examples of elliptic curves.

Here I will only talk about elliptic curves over finite fields, as these are used in number theory, and we were talking about Fermat’s Last Theorem. So, over a finite field $\mathbb{F}_p$ , an elliptic curve is a finite set of points satisfying $y^2 = x^3 + Ax + B$ , plus one special point called the point at infinity. For now, I won’t go into what exactly the point at infinity is or where it comes from, but I’ll explain that in my next post.

Let’s see an example. Take the elliptic curve $E: y^2 = x^3 + x + 2$ over $\mathbb{F}_5$ . Then, for each $x \in \{0, 1, 2, 3, 4 \}$ we check if there are solutions $(y, -y)$ to the relation. If yes, we have found two points $(x, y)$ and $(x, -y)$ on the curve. For this example, we find that the elliptic curve consists of points $\{ (1,2),(1,3),(4,0) \}$ in addition to the point at infinity.

The points of an elliptic curve over a finite field form a group. We call the group law addition and the point at infinity, O, is defined to be the identity. We then define the sum of two points $A$ and $B$ using geometric notions. Take into account the picture above of an elliptic curve over the real numbers. We can see that any line tangent to the curve or intersecting the curve would intersect the elliptic curve in two (if it is vertical) or three points, counting multiplicities. If it intersects the curve twice, we define a third point of intersection to be the point at infinity.

Using the geometric intuition, we define the sum of two points $A$ and $B$ as follows: find the line through $A$ and $B$ . Calculate the third point of intersection of this line with the curve. Then reflect this point in the x-axis and you get the point $A + B$ . If $A = B$ , calculate the tangent at $A$ and then proceed in the same way. Finding the slope and tangent to this curve is done purely algebraically. The slope is defined as $\displaystyle \frac{y_1 - y_2}{x_1-x_2}$ and from this and one point, the equation of the line can be found. The slope of the tangent is found by taking the implicit derivative of the expression for the curve.

In my next post, I will discuss where the point at infinity comes from and why the addition operation is defined the way it is. We will also look at the structure of the group of points on an elliptic curve.

Minimalist Mathematician

Category: Number theory

May 3, 2014

Elliptic Curves – Part 2

April 28, 2014

Elliptic Curves – Part 1