Cousin Wu Ka Lok

First-year PhD student in the Computer Science Department at Stony Brook University. CTF, Maths enthusiast. A member of the Black Bauhinia (blackb6a) CTF team based in Hong Kong.

85 minute read ★★★☆☆

Last time we mentioned the basic concepts of Elliptic curves. However, there were some lingering questions about the weird representation of points in sage being \((x:y:1)\). In this post, we will answer this question by introducing the notion of projective space.

Prerequisites: Fundamental Concepts Underlying Elliptic Curves (Level 0): High-level Overview)

Introduction

The point at infinity raises many questions. For example, why is it represented as \((0:1:0)\) and other points as \((x:y:1)\)?

Equivalence Relations

We say a relation \(R\) over the set \(X\) is a subset of \(X\times X\). If \((a,b)\in R\), we write \(aRb\), or \(a\sim b\). Also say \(\sim\) is the relation.

Using the notion of relation, we can define an equivalence relation on X as a relation \(\sim\) such that

  1. Reflexivity: \(\forall a\in X, a\sim a\)
  2. Symmetry: \(\forall a,b\in X, a\sim b\implies b\sim a\)
  3. Transitivity: \(\forall a,b,c\in X, a\sim b,b\sim c\implies a\sim c\)

Example 1: Trivial and Diagonal Relations

The trivial relation \(S\times S\) (so \(a\sim b\) for every \(a,b\in S\)) and the diagonal relation \(\Delta=\{(a,a):a\in S\}\) (so we only have \(a\sim a\) for all \(a\in S\) and nothing else) are equivalence relations on \(S\).

On the other hand, the empty relation \(\emptyset\) is a relation, but not an equivalence relation. To see why, note that reflexivity requires \((a,a)\in R\) for all \(a\in X\), but empty relation is, obviously, empty.

This also disproves the misconception some students have when learning the subject: if we have symmetry and transivity, symmetry gives \(a\sim b\) and \(b\sim a\), then transitivity gives \(a\sim a\), so reflexivity is not needed, right? The empty relation is a counter-example to this.

Example 2: Fractions

Define a relation \(\sim\) on \(\mathbb{Z}-\{0\}\) as saying \((a,b)\sim (c,d)\) if \(ad=bc\). This in fact defines the equivalence of (non-zero) fractions by viewing \((a,b)\) as \(a/b\).

Proof

  1. Reflexivity: for \((x,y)\in(\mathbb{Z}-\{0\})^2\), \(xy=xy\) so \((x,y)\sim (x,y)\).
  2. Symmetry: for \((x_1,y_1)\) and \((x_2,y_2)\in(\mathbb{Z}-\{0\})^2\), \((x_1,y_1)\sim (x_2,y_2)\) \(\implies x_1y_2=x_2y_1\) \(\implies (x_2,y_2)\sim (x_1,y_1)\).
  3. Transivity: for \((x_1,y_1),(x_2,y_2),(x_3,y_3)\in(\mathbb{Z}-\{0\})^2\), if \((x_1,y_1)\sim (x_2,y_2)\) and \((x_2,y_2)\sim (x_3,y_3)\) \(\implies x_1y_2=x_2y_1\) and \(x_2y_3=x_3y_2\). Then\(\begin{align*} x_1y_2=&x_2y_1\\ x_1y_2y_3=&x_2y_1y_3&\text{ by multiplying both sides by }y_3\\ x_1y_2y_3=&x_3y_2y_1&\text{ by }x_2y_3=x_3y_2\\ x_1y_3=&x_3y_1&\text{Since }y_2\neq 0. \end{align*}\)

So \((x_1,y_1)\sim(x_3,y_3)\).

Exercise

For any \(a,b\in\mathbb{Z}\), say \(a\equiv b\) (mod n) if \(a-b\) is divisible by n, or \(\exists k\in\mathbb{Z}\) such that \(a-b=nk\). Verify that this is an equivalence relation.

Partitions

Let \(\equiv\) be an equivalence relation defined on the set X. Take \(a\in X\), denote the equivalence class of a: \([a]=\{k\in X: a\equiv k\}\) to be the set of elements equivalent to \(a\). Then \(\forall a,b\in X\), either\[ [a]=[b]\text{ or } [a]\cap[b]=\emptyset. \] This essentially show that the equivalence relation partitions a set X.

Proof

Take \(a,b\in X\) and let \(\equiv\) to be the equivalence relation.
If there are any elements, say \(c\), such that \(c\) is both in \([a]\) and \([b]\), then we have that\[
a\equiv c\text{ and } b\equiv c.\] By symmetry of equivalence relations, we get \(c \equiv b\). Then by transitivity, we get \(a\equiv b\). Now consider any elements \(k\in [b]\). We get \(b\equiv k\), so by the same argument, we get \(a\equiv k\), so \([b]\subseteq[a]\).
Similarly, every element in \([a]\) is equivalent to b, so \([a]\subseteq[b]\).
In this case we have \[[a]=[b].\]
If there are no common elements in \([a]\) and \([b]\), then by definition \([a]\cap[b]=\emptyset\).

Quotient Set

Given a set \(X\) and an equivalence relation \(\sim\) on \(X\), we can define the quotient set \(X/\sim\) to be the set of equivalence classes \(\{[a]: a\in X\}\).

Example

As an example, take the mod equivalence relation on \(\mathbb{Z}\), i.e. for any \(a,b\in\mathbb{Z}\), say \(a\equiv b\) (mod n) if \(a-b\) is divisible by n. This partitions the integers into \(n\) equivalence classes. The equivalence classes are the \(n\) different remainders of integers when dividing by \(n\). This gives us the quotient set \(\mathbb{Z}/n\mathbb{Z}=\{[x]:x\in\mathbb{Z}\}\) which we can take the representative \([x]\) for \(x=0,1,\cdots,n-1\), so we can view \(\mathbb{Z}/n\mathbb{Z}=\{0,1,\cdots,n-1\}\).

Well-Defined Functions on Quotients

Given a function \(f\) on the set \(X\) and a equavalence relation \(\sim\) on \(X\), we can construct a “function” \(\tilde{f}\) on the quotient set \(X/\sim\) by setting \(\tilde{f}([x])=f(x)\). This is problematic, however, because if we pick two elements \(a,b\) from the same equivalence class \([x]\), then since \([a]=[b]\), the definition gives \(\tilde{f}([a])=\tilde{f}([b])\), which means that we will need \(f(a)=f(b)\).

The property that every representative of the same equivalence class should map to the same value is not trivial. This property is called well-definedness. A function is well-defined on the quotient when the value of the function is independent of the choice of representative.

It turns out that in general, functions defined this way are not well-defined. However when we deal with sets with additional structures such as groups and rings, this construction of \(\tilde{f}\) on certain equivalence relations will give a well-defined function. For example, the multiplication of integers mod \(n\), constructed using the ordinary integer multiplication, is well-defined.

Non-Example

Let us look at an example of non well-defined function1.

We define a function on non-zero fractions: write the fraction as \(\frac{a}{b}\), and set \(f(\frac{a}{b})=b\). This function is not well defined, because for example \(f(\frac{1}{2})=2\), but \(f(\frac{2}{4})=4\), and \(\frac{1}{2}=\frac{2}{4}\). When we fix this by changing the definition to: \(g(\frac{a}{b})=b/\gcd(a,b)\), this will be well-defined, because dividing by the gcd gives us the reduced form of fractions, which is unique.

Projective Space

Now we are ready to talk about the projective space. Instead of considering the points in the space \(K^n\) (where \(K\) is a field), we can consider the lines in \(K^n\), with the condition that it must pass through the center.

For example, let’s consider the real euclidean plane \(\mathbb{R}^2\). The lines that pass through the center will all have the form \(y=kx\), where \(k\in\mathbb{R}\) is the slope, or it may also be \(x = 0\) for the vertical line. We can also just use a point \(P=(x,y)\) to represent a line by constructing the unique line passing through \(P\) and the origin.

In this case, if we have two points \(P\) and \(Q\), with \(P,Q\) and the origin being colinear, then \(P\) and \(Q\) will define the same line, so we can consider them to be equivalent. If \(P=(x,y)\) and \(Q=(x',y')\), then \(P\) and \(Q\) define the same line if and only if there exists a non-zero integer \(\lambda\) such that \(y=\lambda x\) and \(y'=\lambda x'\). Of course \((0,0)\) can not define a line in this way.

Using this construction, we just made the real projective line \(\mathbb{P}^1(\mathbb{R})\). We can generalize this construction by using the point construction.

Definition of Projective Space

Given a field \(K\), define the Projective \(n\)-space to be the set \(\mathbb{P}^n(K)=\{(x_0,\cdots,x_n)\in K^{n+1}-\{0\}: x_i\in K\}/\sim\), where we declare \((x_0,\cdots,x_n)\sim(y_0,\cdots,y_n)\) if there exists \(\lambda\in K-\{0\}\) such that \((x_0,\cdots,x_n)=(\lambda y_0,\cdots,\lambda y_n)\).

We can denote the set of equivalence class as \([x_0:\cdots:x_n]\) or \([x_0,\cdots,x_n]\), and they are called the homogeneous coordinates.

Real Projective Line

Take \([a,b]\in \mathbb{P}^1(\mathbb{R})\).

If \(b\neq 0\), we have \([a,b]=[a/b,1]\), and we can actually rewrite as \([x,1]\), where \(x\in\mathbb{R}\).

If \(b=0\), then \(a\neq 0\) so we can rewrite \([a,0]=[1,0]\).

In summary, we have \(\mathbb{P}^1(\mathbb{R})=\{[x,1]: x\in\mathbb{R}\}\sqcup\{[1,0]\}\).

Different Interpretations

We can describe \(\mathbb{P}^1(\mathbb{R})\) as the set of all lines that pass through the origin. Note that \([a,b]=[\lambda a, \lambda b]\) exactly means that \((a,b)\) and \((\lambda a, \lambda b)\) lies on the same line (that passes through the center). Then \([a,1]\) gives the line \(x=ay\) and \([1,0]\) gives the horizontal line \(y=0\).

Another interpretation is that since \(\{[x,1]: x\in\mathbb{R}\}\) is really just \(\mathbb{R}\) (since the second coordinate does nothing), we can regard \(\mathbb{P}^1(\mathbb{R})\) as \(\mathbb{R}\), but with an extra point \([0,1]\) we shall call the point at infinity. Some may denote this as \(\mathbb{R}\cup\{\mathcal{O}\}\), where we use \(\mathcal{O}\) to denote the point at infinity.

Taking the line interpretation, for each line that passes through the center we can pick a point on the upper part of the unit circle (since such a line will pass through the unit circle at 2 points, so we pick the upper part). The points \((-1,0)\) and \((1,0)\) represent the same line, so we can join them together (identify them as the same point), and we see that in fact \(\mathbb{P}^1(\mathbb{R})\) is really the same as the unit circle. Since circle is compact, \(\mathbb{P}^1(\mathbb{R})\) (with the quotient topology of \(\mathbb{R}^2\)) is also compact.

\(\mathbb{P}^2(K)\)

How about \(\mathbb{P}^2(K)\)? It consists of the points \([x,y,z]\). If \(z \neq 0\), then we can just divide the whole thing by \(z\) to get \([x/z,y/z,1]\), and we can map these points \([a,b,1] \mapsto (a,b)\in K^2\). If \(z=0\), then since we cannot divide by zero, we consider the points \([x,y,0]\) the points at infinity.

In fact, if \(y\neq 0\) we can divide by \(y\) to get \([a,1,0]\), and further \(x=0\) we get \([0,1,0]\). So when \(z=0\), the remaining coordinates resemble \(\mathbb{P}^1(K)\)! So In summary we have the following disjoint union: \[ \mathbb{P}^2(K)=K^2\sqcup\mathbb{P}^1\]

We can also make a general statement of \(\mathbb{P}^n(K) = K^n\sqcup\mathbb{P}^{n-1}(K)\) with the same argument.

Affine Space

We also have one space, the usual \(K^n\), which we will call it the affine \(n-\)space \(\mathbb{A}^n(K)=\{(x_1,\cdots,x_n):x_i\in K\}\).

Homogeneous Polynomials

Polynomials over Affine Space

For an affine space \(\mathbb{A}^n(K)\), we can define a polynomial \(f(x_1,\cdots,x_n)\) as the set the formal sum of the form \(\displaystyle\sum_{d=1}^N\sum_{i_1+\cdots+i_n = d} a_{i_1i_2\cdots i_n} x_1^{i_1}\cdots x_n^{i_n}\), where \(a_{i_1\cdots i_n}\in K\). The degree of a polynomial is the highest sum of the exponents of the variables with non-zero coefficients. For example, \(f(x,y)=xy^3 + x^2 + xy + y + 1\) has degree 4.

There is a polynomial evaluation function \(\phi_f:\mathbb{A}^n(K)\to K\) by mapping \((a_1,\cdots,a_n)\mapsto f(a_1,\cdots,a_n)\). Then we can talk about the the set of points \(V(f)=\{P\in\mathbb{A}^n(K): f(P)=0\}\), aka the roots. This can give us an example of an affine variety, but we shall discuss this next time.

Homogeneous Polynomials

Can this be mimicked to the projective space? Given \(f(x_0,\cdots,x_n)\), we may, carelessly, consider the root of \(f(P)=0,\), where \(P\in\mathbb{P}^n(K)\). This is problematic, however, because \(\lambda P \sim P\) for any non-zero \(\lambda\in K\), but \(f(P)=0\) in general does not mean \(f(\lambda P)=0\).

We say the function \(\phi_f: \mathbb{P}^n(K)\to K\) by \(\phi_f(P)=f(P)\) is not well-defined, because the value will depend on the choice of the representative \(P\) in the equivalence class.

This is why we can only consider polynomials in which the above holds.

Definition:

We say a polynomial \(f(x_1,\cdots,x_n)\) is homogeneous of degree d if all the terms \(a_{i_1i_2\cdots i_n} x_1^{i_1}\cdots x_n^{i_n}\) has the property that \(a_{i_1i_2\cdots i_n}\in K\) and \(i_1+\cdots+i_n=d\).

Equivalently, for all \(\lambda\in K\), \(f(\lambda x_1,\cdots,\lambda x_n)=\lambda^n f(x_1,\cdots,x_n)\).

Exercise

Proof that the two conditions are indeed equivalent.

For a homogeneous polynomial \(f\), and \(P\in\mathbb{P}^n(K)\), we really have \(f(P)=0\) implying \(f(\lambda P)=0\) for all \(\lambda\in K\). So we can make sense of the roots of homogeneous polynomials in projective space. We can also have the notation \(V(f)=\{P\in\mathbb{P}^n(K): f(P)=0\}\) where \(f\) is a homogeneous polynomial. This is a projective variety, and we will also delay the discussion of this.

Homogenization

For any polynomial \(f(x_1,\cdots,x_n)\), we can convert it to a homogeneous polynomial \(F(x_0, x_1,\cdots,x_n)\) of degree \(d\) (\(d\) equal to the largest degree of terms in \(f\)) by doing \(F(x_0,\cdots,x_n)=x_0^d f(\frac{x_1}{x_0}\cdots,\frac{x_n}{x_0})\), or you may just think of the operation as multiplying each term by an appropiate power of \(x_0\), so that the end result has degree \(d\). This is called the homogenization of the polynomial.

We can convert \(F(x_0, x_1,\cdots,x_n)\) to \(f(x_1,\cdots,x_n)\) easily by \[ f(x_1,\cdots,x_n)=F(\mathbf{1},x_1,\cdots,x_n).\]

Example

For \(f(x,y) = y^2 - x^3 + 1\), the homogenization of \(f(x,y)\) will be \(F(x,y,z) = y^2z - x^3 + z^3\) (\(z\) is moved to the third coordinate for simplicity). Then \(F(x,y,1) = y^2-x^3+z^3 = f(x,y)\).

Exercise

Show that any homogeneous polynomial \(F(x_1,\cdots,x_n)\) of degree \(d\) satisfies the following:\[ d\cdot F=\sum\limits_{i=1}^n x_i \frac{\partial F}{\partial x_i}\]

Elliptic Curves as Homogeneous Polynomials

For elliptic curves in (short) Weierstrass form \(f(x,y) = y^2 -( x^3 + Ax + B)\), the homogenization is \(F(x,y,z)=y^2z -( x^3 + Axz^2 + Bz^3)\). Now for any \((x,y)\in \mathbb{A}^2(K)\), we have an inclusion \(i: \mathbb{A}^2(K)\hookrightarrow \mathbb{P}^2(K)\) by \((x,y)\mapsto [x,y,1]\). So for those points, \(F(i(x,y)) = f(x,y)\).

If \(z=0\), then \(F(x,y,0) = -x^3\). Since \(F(0,y,0) = 0\) for any \(y\neq 0\) ( \(y=0\) is not allowed), there is only 1 point of infinity (out of the others in the form \([x,y,0]\)) that is also in the elliptic curve, namely \([0,1,0]\).

This suggests that we should define elliptic curves using projective space as: given the polynomial \(f(x,y) = y^2 - (x^3 + Ax+B)\) in short Weierstrass form, the elliptic curve is the set of points that satisfy \(F(x,y,z)=0\), i.e. \[ E(K) = \{ P\in \mathbb{P}^2(K): F(P)=0 \} \]

This will consist of \(\{[x,y,1]: f(x,y)=F(x,y,1)=0\}\subset \mathbb{P}^2(K)\), and the point at infinity \([0,1,0]\). \([x,y,1]\) can be mapped back to \((x,y)\in \mathbb{A}^2(K)\), and \([0,1,0]\) is a special point we call the point at infinity \(\mathcal{O}\).

Example

In sage, we can use the projective coordinates to represent a point in the elliptic curve.

Non-Singular Elliptic Curves

With the projective space description above, we can finally define a “differentiable” elliptic curve.

We say a curve \(C\) (defined by a single equation \(f(x_1,\cdots,x_n)=0\)) is singular at a point \(P\in C\) if \(\frac{\partial f}{\partial x_i}(P)=0\) for all \(i\in\{1,\cdots,n\}\). Otherwise the curve is non-singular at \(P\).

If the curve is non-singular at all points, it is called a non-singular curve. If the curve is singular at some points, it is called a singular curve.

Remark:

Note that the partial derivatives of polynomials can always be defined as \(\frac{dx^n}{dx}= nx^{n-1}\). However, if the characteristic of the field is \(n\), then \(\frac{dx^n}{dx}=0\). In any case, for polynomial \(f\), we always have that \(\frac{\partial f}{\partial x_i}\) is a polynomial, so everything is good.

Now we can prove the following result: An elliptic curve defined by the short Weierstrass equation \(y^2=x^3+Ax+B\) non-singular at all points if and only iff the discriminant is non-zero.

Proof

First we will show that the point at infinity is never singular: The homogeneous equation of \(C\) is \(F(x,y,z)=y^2z-x^3-Axz^2-Bz^3=0\). We have that \(\frac{\partial F}{\partial z}=y^2-2zAx-3z^2B\), so \(\frac{\partial F}{\partial z}(0,1,0)=1\) which is not zero.

Now say \(P\in E\) is not the point at infinity. Then the curve is singular iff \(\frac{\partial f}{\partial x}(P)=\frac{\partial f}{\partial y}(P)=0\) for some point \(P\).

Let \((x_0,y_0)\) be a singular point. then taking partial derivatives leave us with \(2y_0 = 3x_0^2+A=0\), which gives \(y_0=0\) and \(A=-3x_0^2\). Substituting it back to the original curve we have \(0 = y_0^2 = x_0^3 + (-3x_0^2)x_0 + B\), so \(B=2x_0^3\). The discriminant gives \[ \Delta = 4(-3x_0^2)^3+27(2x_0^3)^2=27\cdot 4(x_0^6-x_0^6)=0. \]

If \(\Delta=0\), then the equation \(x^3+Ax+B\) has a double root \(x_0\). This happens when the derivative at \(x_0\) is zero. Now the derivative of \(x^3+Ax+B\) at \(x_0\) is \(3x_0^2+A\), which is the same as \(-\frac{\partial f}{\partial x}(x_0,0)\), so \(\frac{\partial f}{\partial x}(x_0,0)=0\).

Then let’s consider \((x_0,0)\), we have \(\frac{\partial f}{\partial y}(x_0,0)=0\), and \((x_0,0)\) is a point in the curve since \(f(x_0,0) = 0^2 - (x_0^3 + Ax_0 + B) = 0\) (since \(x_0\) is a root to the cubic polynomial). This shows that \(\Delta=0\) implies \((x_0,0)\) is a singular point, so \(E\) is singular.

  1. A non well-defined function is actually NOT a function, since you have one input mapping to many outputs, so non well-defined function is a misnomer. To understand the intricacies, readers can refer to the definition of function using relations: we say relation \(R\) of \(X\times Y\) is a function if \(\forall x\in X, y_1,y_2\in Y, (x,y_1)\in R\) and \((x,y_2)\in R\), implies \(y_1=y_2\), so each \(x\) can only map to one value of \(y\). Further, \(\forall x\in X\), there exists some \(y\) such that \((x,y)\in R\) (so every \(x\) is mapped). Then we can use \(y=f(x)\) to denote \((x,y)\in R\). ↩

You may also enjoy

Zetta-CTF: 🥥

38 minute read ★★☆☆☆

The following challenge is from the Zetta-CTF PHP: Horrific Puzzle, during the VXCON in Hong Kong, 27 Apr - 28 Apr 2019. The challenge is named 🥥. btw no one...