What is the projective space?

Question

In Elliptic Curve Cryptography, using the projective space is often mentioned to accelerate the computations and to represent the point at infinity. But What is the Projective space exactly ? How can we represent the curve in such space ?

Answer 1

Let us consider this beautiful elliptic curve:

She is defined in a plane ($\mathbb{R}^2$).

1. From a plane to a projective space

For an affine plane $\mathbb{A}^2 = \{(x,y): x,y \in \mathbb{K}\}$, we can define its projective space as follow:

$$ \mathbb{P}^2 = \{(x:y:z): x,y,z \in \mathbb{K}\}\backslash(0:0:0) \sim $$

Where $\sim$ is the equivalence relation such that: $$\sim : (a:b:c) \sim (a':b':c') \iff \exists \lambda. (a,b,c) = (\lambda a', \lambda b', \lambda c')$$

In other words, all the points on the same line going though the origin $(0:0:0)$ are equivalent with respect to $\sim$.

It may seem complicated so let us use some figures. Here we have a projective space.

Each points on the same green line (passing through the origin) are equivalent due to the $\sim$ relation. Each points on the same orange line (passing through the origin) are equivalent due to the $\sim$ relation.

We can divide this space into 2 sets. The points with $z=0$ (in orange) and the points with $z \neq 0$ (in green).

Let us have a look at the green set. If we consider the lines (or equivalent points), one can remark that they all intersect the plane $\{z=1\}$ (See diagram below). Thus all the points in the green area have an equivalent into the plane $\{z=1\}$.

The only points that does not satisfy this property are those which equivalence line is parallel to the plane $\{z=1\}$. In other words, the points where $z=0$.

Let us have a look at those points. Using the same principle as with the green space, one can see that each line going through the origin cut the line $\{z=0, y=1\}$. Therefore with one exception, all the points in the orange plane have an equivalent on the line $\{z=0, y=1\}$.

Note that the exception are the points parallel to the line $\{z=0, y=1\}$, in other word, the $x$ axis. Because they form a line, they are all equivalent with respect to $\sim$ therefore, they are all equivalent to $(1:0:0)$.

In the end, all the points in the projective space $\mathbb{P}^2$ have an equivalent in the plane $\{z = 1\}$ or on the line $\{y = 1, z = 0\}$ or to $(1:0:0)$.

2. Going back to the curve

In the projective space, the equation of the elliptic curve is: $$y^2\ z = x^3 + a\ x\ z^2 + b\ z^3$$ (The degree of each term of the polynomial must be 3: $deg(y^2\ z) = deg(y^2) + deg(z) = 3$ etc.)

We can now represent the points of the elliptic curve in this space. Due to the equivalence relation of this projective space, we can just display those on the different subdivisions (plane $\{z = 1\}$, line $\{y = 1, z = 0\}$ and $(1:0:0)$).

for $(1:0:0)$ (point)

$(1:0:0)$ is not part of the curve as $y^2\ z = 0$ and $x^3 + a\ x\ z^2 + b\ z^3 = 1$

for $z = 1$ (plane)

This is the simplest form, by replacing $z$ by its value in the equation we get: $y^2 = x^3 + a\ x+b$. Therefore the representation of the elliptic curve will be the same as the one above but projected on the plane $\{z = 1\}$.

for $z = 0$

$$z = 0 \implies y^2\ z = 0 \implies x^3 + a\ x\ z^2 + b\ z^3 = x^3 = 0 \implies x = 0$$ The points that satisfy this equations are the one of the form $(0:\lambda:0)$.
Or $(0:\lambda:0) \sim (0:1:0)$ This is the missing point that can not be represented using the plane representation: the point at infinity $P_\infty$.

Thus, we can finally represent our elliptic curve in its projective space as bellow.

Remarks

As a quick reminder, here is what a curve really looks like in a finite field: not as smooth as one would expect...

$$y^2 = x^3 - 2 x + 1 \text{ over } \mathbb{Z}_{89}$$