Tripling-oriented Doche–Icart–Kohel curve

Let K be a field of characteristic different form 2 and 3. An elliptic curve in tripling oriented Doche–Icart–Kohel form is defined by the equation: : T_a\ :\ y^2 = x^3 + 3a(x+1)^2 with a\in K. A general point P on T_{a} has affine coordinates (x,y). The "point at infinity" represents the neutral element for the group law and it is written in projective coordinates as O = (0:1:0). The negation of a point P = (x, y) with respect to this neutral element is −P = (x, −y). ==The group law==

Consider an elliptic curve in the Tripling-oriented Doche-Icart-Kohel form in affine coordinates: : T_a:\quad y^2= x^3 + 3a(x+1)^2, \qquad a\neq 0, \tfrac{9}{4}. As in other forms of elliptic curves, it is possible to define some "operations" between points, such as adding points, or doubling (See also The group law). In the following sections formulas to add, negate and doubling points are given. The addition and doubling formulas are often used for other operations: given a point P on an elliptic curve it is possible to compute [n]P, where n is an integer, using addition and doubling; computing multiples of points is important in elliptic curve cryptography and in Lenstra elliptic curve factorization. Addition Given P_1=(x_1,y_1) and P_2=(x_2,y_2) on T_{a}, the point P_3=(x_3,y_3)=P_1+P_2 has coordinates: :\begin{align} x_3 &= \frac{1}{(x_2 - x_1)^2} \left \{ -x_1^3+(x_2-3a)x_1^2+(x_2^2+6ax_2)x_1+(y_1^2-2y_2y_1+(-x_2^3-3ax_2^2+y_2^2)) \right \} \\ y_3 &= \frac{1}{(x_2 - x_1)^3} \left \{ (-y_1+2y_2)x_1^3+(-3ay_1-3y_2x_2+3ay_2)x_1^2+(3x_2^2y_1+6ax_2y_1-6ay_2x_2)x_1 \right.\\ &\qquad \qquad \qquad \qquad \left.+(y_1^3-3y_2y_1^2+(-2x_2^3-3ax_2^2+3y_2^2)y_1+(y_2x_2^3+3ay_2x_2^2-y_2^3)) \right \} \end{align} Doubling Given a point P_1=(x_1,y_1) on T_{a}, the point P_3=(x_3,y_3)=2P_1 has coordinates: :\begin{align} x_3 &= \frac{9}{4y_1^2 x_1^4}+\frac{9}{y_1^2ax_1^3}+ \left (\frac{9}{y_1^2a^2}+\frac{9}{y_1^2a} \right )x_1^2+ \left (\frac{18}{y_1^2a^2}-2 \right ) x_1+\frac{9}{y_1^2a^2-3a} \\ y_3 &= -\frac{27}{8y_1^3x_1^6}-\frac{81}{4y_1^3ax_1^5}+ \left (-\frac{81}{2y_1^3a^2}-\frac{81}{4y_1^3a} \right )x_1^4+ \left (-\frac{27}{y_1^3a^3}-\frac{81}{y_1^3a^2}+\frac{9}{2y_1} \right )x_1^3+ \left (-\frac{81}{y_1^3a^3}-\frac{81}{2y_1^3}a^2+\frac{27}{2y_1a} \right)x_1^2 \\ & \qquad \qquad \qquad \qquad+ \left (-\frac{81}{y_1^3a^3}+\frac{9}{y_1a^2}+\frac{9}{y_1a} \right )x_1 + \left (-\frac{27}{y_1^3a^3}+\frac{9}{y_1a^2}-y_1 \right ) \end{align} Negation Given a point P_1=(x_1,y_1) on T_{a}, its negation with respect to the neutral element (0:1:0) is -P_1=(x_1,-y_1). There are also other formulas given in for Tripling-oriented Doche–Icart–Kohel curves for fast tripling operation and mixed-addition. ==New Jacobian coordinates==

For computing on these curves points are usually represented in new Jacobian coordinates (Jn): a point in the new Jacobian coordinates is of the form P=(X : Y : Z : Z^2); moreover: : P= (X:Y:Z:Z^{2}) = (\lambda^{2}X:\lambda^{3}Y:\lambda Z:\lambda^{2}Z^{2}), for any \lambda \in K. This means, for example, that the point P=(X:Y:Z:Z^2) and the point Q=(4X:8Y:2Z:4Z^2) (for \lambda=2) are actually the same. So, an affine point P=(x,y) on T_{a} is written in the new Jacobian coordinates as P=(X : Y : Z : Z^2), where x = X/Z^2 and y = Y/Z^3; in this way, the equation for T_{a} becomes: : T_a\ :\ Y^2 = X^3 + 3aZ^2(X+Z^2)^2. The term Z^2 of a point on the curve makes the mixed addition (that is the addition between two points in different systems of coordinates) more efficient. The neutral element in new Jacobian coordinates is (1:1:0:0). ==Algorithms and examples==

Addition The following algorithm represents the sum of two points P_1 and P_2 on an elliptic curve in the Tripling-oriented Doche-Icart-Kohel form. The result is a point P_3=(X_3,Y_3,Z_3,ZZ_3). It is assumed that Z_2=1 and that a_3=3a. The cost of this implementation is 7M + 4S + 1*a3 + 10add + 3*2 + 1*4, where M indicates the multiplications, S the squarings, a3 indicates the multiplication by the constant a3, add represents the number of additions required. A = X_2ZZ_1 B = Y_2ZZ_1Z_1 C = X_1-A D = 2(Y_1-B) F = C^2 F_4 = 4F Z_3 = (Z_1+C)^2-ZZ_1-F E = {Z_3}^2 G = CF_4 H = AF_4 X_3 = D^2-G-2H-a_3E Y_3 = D(H-X_3)-2BG ZZ_3 = E Example Let P_1=(1,\sqrt{13}) and P_2=(0,\sqrt{3}) affine points on the elliptic curve over \mathbb{R}: y^2 = x^3 +3(x+1)^2. Then: A = X_2ZZ_1 = 0 B = Y_2ZZ_1Z_1 = \sqrt{3} C = X_1-A = 1 D = 2(Y_1-B) = 2(\sqrt{13}-\sqrt{3}) F = C^2 = 1 F_4 = 4F = 4 Z_3 = (Z_1+C)^2-ZZ_1-F = 2 E = {Z_3}^2 = 4 G = CF_4 = 4 H = AF_4 = 0 X_3 = D^2-G-2H-a_3E = 48-8\sqrt{39} Y_3 = D(H-X_3)-2BG = 296\sqrt{3}-144\sqrt{13} ZZ_3 = E = 4 Notice that in this case Z_1=Z_2=1. The resulting point is P_3 = (X_3,Y_3,Z_3,ZZ_3) = (48-8\sqrt{39},296\sqrt{3}-144\sqrt{13},2,4), that in affine coordinates is P_3=(12-2\sqrt{39},37\sqrt{3}-18\sqrt{13}). Doubling The following algorithm represents the doubling of a point P_1 on an elliptic curve in the Tripling-oriented Doche-Icart-Kohel form. It is assumed that a_3=3a, a_2=2a. The cost of this implementation is 2M + 7S + 1*a2 + 1*a3 + 12add + 2*2 + 1*3 + 1*8; here M represents the multiplications, S the squarings, a2 and a3 indicates the multiplications by the constants a2 and a3 respectively, and add indicates the additions. A = {X_1}^2 B = a_2ZZ_1(X_1+ZZ_1) C = 3(A+B) D = {Y_1}^2 E = D^2 Z_3 = (Y_1+Z_1)^2-D-ZZ_1 ZZ_3 = Z_3^2 F = 2((X_1+D)^2-A-E) X_3 = C^2-a_3ZZ_3-2F Y_3 = C(F-X_3)-8E Example Let P_1=(0,\sqrt{3}) be a point on y^2 = x^3 + 3(x+1)^2. Then: A = {X_1}^2 = 0 B = a_2ZZ_1(X_1+ZZ_1) = 2 C = 3(A+B) = 6 D = {Y_1}^2 = 3 E = D^2 = 9 Z_3 = (Y_1+Z_1)^2-D-ZZ_1 = 2\sqrt{3} ZZ_3 = Z_3^2 = 12 F = 2((X_1+D)^2-A-E) = 0 X_3 = C^2-a_3ZZ_3-2F = 0 Y_3 = C(F-X_3)-8E = -72 Notice that here the point is in affine coordinates, so Z_1=1. The resulting point is P_3=(0,-72,2\sqrt{3},12), that in affine coordinates is P_3 = (0,-\sqrt{3}). ==Equivalence with Weierstrass form==

Any elliptic curve is birationally equivalent to another written in the Weierstrass form. The following twisted tripling-oriented Doche-Icart-Kohel curve: :T_{a,\lambda}: \quad y^2 = x^3 + 3\lambda a(x+\lambda)^2 can be transformed into the Weierstrass form by the map: :(x,y)\mapsto (x-\lambda a, y). In this way T_{a,\lambda} becomes: :y^2 = x^3 - 3{\lambda}^2a(a-2)x + {\lambda}^3a(2a^2-6a+3). Conversely, given an elliptic curve in the Weierstrass form: :E_{c,d}: \quad y^2 = x^3 +cx^2 +d, it is possible to find the "corresponding" Tripling-oriented Doche–Icart–Kohel curve, using the following relation: :\lambda = \frac{-3d(a-2)}{a(2a^2-6a+3)} where is a root of the polynomial :6912a(a-2)^3-j(4a-9), where :j=\frac{6912c^3}{4c^3+27d^2} is the j-invariant of the elliptic curve E_{c,d}. Notice that in this case the map given is not only a birational equivalence, but an isomorphism between curves. ==See also==