5
$\begingroup$

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 ?

$\endgroup$
12
$\begingroup$

Let us consider this beautiful elliptic curve:

enter image description here

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.

enter image description here

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\}$.

enter image description here

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\}$.

enter image description here

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)$.

enter image description here

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 = 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.

enter image description here

Remarks

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

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

| improve this answer | |
$\endgroup$
  • $\begingroup$ @Cryptostasis I don't have a blog $\endgroup$ – Biv Oct 24 '16 at 20:44
  • $\begingroup$ @Biv, In general case, we have: $(a:b:c) \sim (a':b':c') \iff \exists \lambda,d,e. (a,b,c) = (\lambda^d a', \lambda^e b', \lambda c')$ $\endgroup$ – Meysam Ghahramani Oct 24 '16 at 20:49
  • $\begingroup$ @Cryptostasis and this is clearly meant as a helpful ressource, so it would be kinda wasted on a blog, because exposure would be pretty low probably... But here it is really high. $\endgroup$ – SEJPM Oct 24 '16 at 22:21
  • $\begingroup$ @Cryptostasis The help center explicitly encourages answering one's own question. $\endgroup$ – yyyyyyy Oct 25 '16 at 2:52
  • 2
    $\begingroup$ @Biv I know that this thread is very old, but I wanted to thank you for this answer. It's very clear and has helped me a lot. I also wanted to ask whether you made these drawings, and if so, how? $\endgroup$ – Alex Mar 31 '18 at 14:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.