0
$\begingroup$

I have been given a textbook which defines the addition of two points on an elliptic curve and the doubling of a point on an elliptic curve. This textbook explains elliptic curves in projective space where $z=1$ and it expresses the points on the curve as affine points of the form $[x,y,1]$ but it never really explains why we want to do this.

I have looked over many solutions of which only explain the addition of two points $P$ and $Q$ as the following:

We find the line between the points, find the point of intersection on the curve and finally reflect it over the x axis.

Example of what I mean

The textbook I have been given says that for adding two points P and Q we use the group operation $P\bigoplus Q=O*(P*Q)$ where $O$ is a "point at infinity" $[0,1,0].$ We first find the slope of the line between the points and then we plug it in to the following equations:

$x^3=m^2-x_1-x_2$

$y^3=-m(x_3-x_1)-y_1$

and the point should be denoted as $[x,y,1]$.

This textbook has confused me beyond belief.

To my understanding, a projective plane essentially is a plane that is parallel to another plane that lies flat on the x,y axis. This plane is perpendicular to the z axis (points satisfy $z=1$), it contains affine points of the original plane and the point at infinity $O$. If one were to construct a 3 dimensional line crossing the origin it would eventually pass through the coordinates $[x_z,y_z,z]$, so the point $(1,2)$ would be found on the projective curve as $[1,2,1]$.

Is there any specific reason why we want to express points of the elliptic curve in projective space? Does it make adding two points or doubling a point easier?How might I explain to someone why I chose to represent it using projective space if they were to ask me why not just use the algorithm shown in the picture?

$\endgroup$
  • 1
    $\begingroup$ I would like to mention in passing that projective coordinates are quite natural: They can be interpreted as simply storing the fractions arising from divisions as a pair of numerator and denominator instead of performing the division. The arithmetic rules of fractions then imply that one can convert any formula comprised of field operations into an equivalent formula without divisions (except for one at the end), and this is precisely the process of projectivizing affine formulas. In ECC's $[x:y:z]$ coordinates, $z$ is the common denominator for both $x/z$ and $y/z$, saving space. $\endgroup$ – yyyyyyy Mar 21 at 3:17
2
$\begingroup$

Is there any specific reason why we want to express points of the elliptic curve in projective space? Does it make adding two points or doubling a point easier?

Because it is a lot more efficient.

If you take a look at the operations involved in performing an elliptic curve operation on a prime curve, they are:

  • Modular addition and subtraction
  • Modular multiplication
  • Modular inversion, that is, given $a$, find $b$ such that $a \cdot b \equiv 1 \pmod p$

It turns out that modular addition and subtraction is fast, modular multiplication is somewhat slower, and modular inverse is dreadfully slow.

And, if we do everything using affine coordinates, it turns out that we need to do a modular inversion for every point addition or doubling.

In contrast, if we do things using projective coordinates, it turns out that we don't need to compute any inverses at all (we do increase the number of modular additions and multiplications we need, however the time involved there is much less than doing a single modular inversion, and so it is a win).

Now, at the end, we'll need to convert back to affine coordinates; that involves a single modular inversion; however when we do a point multiplication, that means that we replaced several hundred modular inversions with just one - a definite win.

$\endgroup$

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.