7
$\begingroup$

How can I get point addition equation for elliptic curves in projective co ordinate system? Can I get it by changing $$ x = X/Z $$ and $$ y =Y/Z $$ in the equation for affine co ordinates' group law?

I have done it using the above narrated step and made the denominator as $ Z $ in equation for binary super-singular curves. Unfortunately I am not able to get the correct output. I have used the equation $$x_3 = (y_1 +y_2/x_1 +x_2)^2 + x_1 + x_2$$ $$y_3 = (y_1 +y_2/x_1 +x_2)(x_1 +x_2) + y_1 + c$$ for the curve $y^2 + cy = x^3 + ax+b$.

$\endgroup$
  • $\begingroup$ I found this, a database of curve equations, with all possible addition formulas. not your curve though. $\endgroup$ – Willem Hengeveld Aug 3 '14 at 20:16
8
$\begingroup$

Your second equation seems a bit off. In the curve of equation: $$ y^2 + cy = x^3 + ax + b $$ in a binary field $\mathbb{F}_{2^m}$, to add point $P_1 = (x_1,y_1)$ to point $P_2 = (x_2,y_2)$, resulting in point $P_3 = (x_3,y_3)$, then the two equations are: \begin{eqnarray*} x_3 &=& \lambda^2 + x_1 + x_2\\ y_3 &=& \lambda (x_1+x_3) + y_1 + c \end{eqnarray*} where $$ \lambda = \frac{y_1+y_2}{x_1+x_2} $$

In projective coordinates, the point $(x,y)$ is represented by the triplet $(X,Y,Z)$ such that $x = X/Z$ and $y = Y/Z$. It is important to realize that the projective coordinates are not unique; $(X,Y,Z)$ and $(\mu X, \mu Y, \mu Z)$ represent the same point, for any non-zero $\mu$. If we have projective coordinates for $P_1$ and $P_2$, then we get: \begin{eqnarray*} \lambda &=& \frac{\frac{Y_1}{Z_1}+\frac{Y_2}{Z_2}}{\frac{X_1}{Z_1}+\frac{X_2}{Z_2}} \\ &=& \frac{\frac{Y_1 Z_2 + Y_2 Z_1}{Z_1 Z_2}}{\frac{X_1 Z_2 + X_2 Z_1}{Z_1 Z_2}} \\ &=& \frac{Y_1 Z_2 + Y_2 Z_1}{X_1 Z_2 + X_2 Z_1} \end{eqnarray*} Then: \begin{eqnarray*} \frac{X_3}{Z_3} &=& \frac{(Y_1 Z_2 + Y_2 Z_1)^2}{(X_1 Z_2 + X_2 Z_1)^2} + \frac{X_1}{Z_1} + \frac{X_2}{Z_2} \\ \frac{Y_3}{Z_3} &=& \frac{Y_1 Z_2 + Y_2 Z_1}{X_1 Z_2 + X_2 Z_1} \cdot \left(\frac{X_1}{Z_1} + \frac{(Y_1 Z_2 + Y_2 Z_1)^2}{(X_1 Z_2 + X_2 Z_1)^2} + \frac{X_1}{Z_1} + \frac{X_2}{Z_2}\right) + \frac{Y_1}{Z_1} + c \end{eqnarray*}

The goal is to compute without making divisions; thus, we need to define $Z_3$ such that all these inconvenient fractions disappear. One possible solution, given the equations above, is to set: $$ Z_3 = Z_1 Z_2 (X_1 Z_2 + X_2 Z_1)^3 $$ from which we deduce: \begin{eqnarray*} X_3 &=& (X_1 Z_2 + X_2 Z_1)(Z_1 Z_2 (Y_1 Z_2 + Y_2 Z_1)^2 + (X_1 Z_2 + X_2 Z_1)^2(X_1 Z_2 + X_2 Z_1)) \\ &=& Z_1 Z_2 (X_1 Z_2 + X_2 Z_1) (Y_1 Z_2 + Y_2 Z_1)^2 + (X_1 Z_2 + X_2 Z_1)^4 \end{eqnarray*} and some even more complex -- but without any division -- expression for $Y_3$ (that I am too lazy to compute).


So you get the two main points:

  • yes, to get projective coordinates, you "just" replace $x$ with $X/Z$ and so on;
  • but ultimately you still get some choice in the expression for $Z_3$, since projective coordinates are not unique. You thus choose an expression which minimizes overall computational cost, which usually means "the simplest expression which avoids divisions".

Since you have a choice in $Z_3$, you do not necessarily end up with the same formulas as other people, and it is not necessarily mean that your formulas are wrong.

$\endgroup$
  • $\begingroup$ Thank you @Thomas Pornin . I got the result with correct output. And one more doubt, the point I am getting in projective is not unique. My doubt is can I get back same point in affine when I map points from different projective representation of a single point to affine? $\endgroup$ – vijita Aug 4 '14 at 6:22
  • $\begingroup$ Yes, you get the same point at the end. That's the idea of non-unique coordinates: you have the choice of representation, but they all stand for the same curve point. $\endgroup$ – Thomas Pornin Aug 4 '14 at 11:02

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.