Type of elliptic curve
The tripling-oriented Doche–Icart–Kohel curve is a form of an elliptic curve that has been used lately in cryptography [when? ; it is a particular type of Weierstrass curve . At certain conditions some operations , as adding, doubling or tripling points, are faster to compute using this form.
The tripling-oriented Doche–Icart–Kohel curve, often called with the abbreviation 3DIK was introduced by Christophe Doche, Thomas Icart, and David R. Kohel in.[ 1]
A tripling-oriented Doche–Icart–Kohel curve of equation
y
2
=
x
3
−
3
x
2
−
6
x
−
3
{\displaystyle y^{2}=x^{3}-3x^{2}-6x-3}
Let
K
{\displaystyle K}
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
+
3
a
(
x
+
1
)
2
{\displaystyle T_{a}\ :\ y^{2}=x^{3}+3a(x+1)^{2}}
with
a
∈
K
{\displaystyle a\in K}
A general point P on
T
a
{\displaystyle T_{a}}
affine coordinates
(
x
,
y
)
{\displaystyle (x,y)}
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 ).
Consider an elliptic curve in the Tripling-oriented Doche-Icart-Kohel form in affine coordinates :
T
a
:
y
2
=
x
3
+
3
a
(
x
+
1
)
2
,
a
≠
0
,
9
4
.
{\displaystyle 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 .
Given
P
1
=
(
x
1
,
y
1
)
{\displaystyle P_{1}=(x_{1},y_{1})}
P
2
=
(
x
2
,
y
2
)
{\displaystyle P_{2}=(x_{2},y_{2})}
T
a
{\displaystyle T_{a}}
P
3
=
(
x
3
,
y
3
)
=
P
1
+
P
2
{\displaystyle P_{3}=(x_{3},y_{3})=P_{1}+P_{2}}
x
3
=
1
(
x
2
−
x
1
)
2
{
−
x
1
3
+
(
x
2
−
3
a
)
x
1
2
+
(
x
2
2
+
6
a
x
2
)
x
1
+
(
y
1
2
−
2
y
2
y
1
+
(
−
x
2
3
−
3
a
x
2
2
+
y
2
2
)
)
}
y
3
=
1
(
x
2
−
x
1
)
3
{
(
−
y
1
+
2
y
2
)
x
1
3
+
(
−
3
a
y
1
−
3
y
2
x
2
+
3
a
y
2
)
x
1
2
+
(
3
x
2
2
y
1
+
6
a
x
2
y
1
−
6
a
y
2
x
2
)
x
1
+
(
y
1
3
−
3
y
2
y
1
2
+
(
−
2
x
2
3
−
3
a
x
2
2
+
3
y
2
2
)
y
1
+
(
y
2
x
2
3
+
3
a
y
2
x
2
2
−
y
2
3
)
)
}
{\displaystyle {\begin{aligned}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_{2}y_{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_{2}x_{2}+3ay_{2})x_{1}^{2}+(3x_{2}^{2}y_{1}+6ax_{2}y_{1}-6ay_{2}x_{2})x_{1}\right.\\&\qquad \qquad \qquad \qquad \left.+(y_{1}^{3}-3y_{2}y_{1}^{2}+(-2x_{2}^{3}-3ax_{2}^{2}+3y_{2}^{2})y_{1}+(y_{2}x_{2}^{3}+3ay_{2}x_{2}^{2}-y_{2}^{3}))\right\}\end{aligned}}}
Given a point
P
1
=
(
x
1
,
y
1
)
{\displaystyle P_{1}=(x_{1},y_{1})}
T
a
{\displaystyle T_{a}}
P
3
=
(
x
3
,
y
3
)
=
2
P
1
{\displaystyle P_{3}=(x_{3},y_{3})=2P_{1}}
x
3
=
9
4
y
1
2
x
1
4
+
9
y
1
2
a
x
1
3
+
(
9
y
1
2
a
2
+
9
y
1
2
a
)
x
1
2
+
(
18
y
1
2
a
2
−
2
)
x
1
+
9
y
1
2
a
2
−
3
a
y
3
=
−
27
8
y
1
3
x
1
6
−
81
4
y
1
3
a
x
1
5
+
(
−
81
2
y
1
3
a
2
−
81
4
y
1
3
a
)
x
1
4
+
(
−
27
y
1
3
a
3
−
81
y
1
3
a
2
+
9
2
y
1
)
x
1
3
+
(
−
81
y
1
3
a
3
−
81
2
y
1
3
a
2
+
27
2
y
1
a
)
x
1
2
+
(
−
81
y
1
3
a
3
+
9
y
1
a
2
+
9
y
1
a
)
x
1
+
(
−
27
y
1
3
a
3
+
9
y
1
a
2
−
y
1
)
{\displaystyle {\begin{aligned}x_{3}&={\frac {9}{4y_{1}^{2}x_{1}^{4}}}+{\frac {9}{y_{1}^{2}ax_{1}^{3}}}+\left({\frac {9}{y_{1}^{2}a^{2}}}+{\frac {9}{y_{1}^{2}a}}\right)x_{1}^{2}+\left({\frac {18}{y_{1}^{2}a^{2}}}-2\right)x_{1}+{\frac {9}{y_{1}^{2}a^{2}-3a}}\\y_{3}&=-{\frac {27}{8y_{1}^{3}x_{1}^{6}}}-{\frac {81}{4y_{1}^{3}ax_{1}^{5}}}+\left(-{\frac {81}{2y_{1}^{3}a^{2}}}-{\frac {81}{4y_{1}^{3}a}}\right)x_{1}^{4}+\left(-{\frac {27}{y_{1}^{3}a^{3}}}-{\frac {81}{y_{1}^{3}a^{2}}}+{\frac {9}{2y_{1}}}\right)x_{1}^{3}+\left(-{\frac {81}{y_{1}^{3}a^{3}}}-{\frac {81}{2y_{1}^{3}}}a^{2}+{\frac {27}{2y_{1}a}}\right)x_{1}^{2}\\&\qquad \qquad \qquad \qquad +\left(-{\frac {81}{y_{1}^{3}a^{3}}}+{\frac {9}{y_{1}a^{2}}}+{\frac {9}{y_{1}a}}\right)x_{1}+\left(-{\frac {27}{y_{1}^{3}a^{3}}}+{\frac {9}{y_{1}a^{2}}}-y_{1}\right)\end{aligned}}}
Given a point
P
1
=
(
x
1
,
y
1
)
{\displaystyle P_{1}=(x_{1},y_{1})}
T
a
{\displaystyle T_{a}}
negation with respect to the neutral element
(
0
:
1
:
0
)
{\displaystyle (0:1:0)}
−
P
1
=
(
x
1
,
−
y
1
)
{\displaystyle -P_{1}=(x_{1},-y_{1})}
There are also other formulas given in [ 2]
New Jacobian coordinates [ edit ] 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
)
{\displaystyle P=(X:Y:Z:Z^{2})}
P
=
(
X
:
Y
:
Z
:
Z
2
)
=
(
λ
2
X
:
λ
3
Y
:
λ
Z
:
λ
2
Z
2
)
,
{\displaystyle P=(X:Y:Z:Z^{2})=(\lambda ^{2}X:\lambda ^{3}Y:\lambda Z:\lambda ^{2}Z^{2}),}
for any
λ
∈
K
{\displaystyle \lambda \in K}
This means, for example, that the point
P
=
(
X
:
Y
:
Z
:
Z
2
)
{\displaystyle P=(X:Y:Z:Z^{2})}
Q
=
(
4
X
:
8
Y
:
2
Z
:
4
Z
2
)
{\displaystyle Q=(4X:8Y:2Z:4Z^{2})}
λ
=
2
{\displaystyle \lambda =2}
So, an affine point
P
=
(
x
,
y
)
{\displaystyle P=(x,y)}
T
a
{\displaystyle T_{a}}
P
=
(
X
:
Y
:
Z
:
Z
2
)
{\displaystyle P=(X:Y:Z:Z^{2})}
x
=
X
/
Z
2
{\displaystyle x=X/Z^{2}}
y
=
Y
/
Z
3
{\displaystyle y=Y/Z^{3}}
T
a
{\displaystyle T_{a}}
T
a
:
Y
2
=
X
3
+
3
a
Z
2
(
X
+
Z
2
)
2
.
{\displaystyle T_{a}\ :\ Y^{2}=X^{3}+3aZ^{2}(X+Z^{2})^{2}.}
The term
Z
2
{\displaystyle Z^{2}}
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
)
{\displaystyle (1:1:0:0)}
Algorithms and examples [ edit ] The following algorithm represents the sum of two points
P
1
{\displaystyle P_{1}}
P
2
{\displaystyle P_{2}}
P
3
=
(
X
3
,
Y
3
,
Z
3
,
Z
Z
3
)
{\displaystyle P_{3}=(X_{3},Y_{3},Z_{3},ZZ_{3})}
Z
2
=
1
{\displaystyle Z_{2}=1}
a
3
=
3
a
{\displaystyle a_{3}=3a}
3 , add represents the number of additions required.
A
=
X
2
Z
Z
1
{\displaystyle A=X_{2}ZZ_{1}}
B
=
Y
2
Z
Z
1
Z
1
{\displaystyle B=Y_{2}ZZ_{1}Z_{1}}
C
=
X
1
−
A
{\displaystyle C=X_{1}-A}
D
=
2
(
Y
1
−
B
)
{\displaystyle D=2(Y_{1}-B)}
F
=
C
2
{\displaystyle F=C^{2}}
F
4
=
4
F
{\displaystyle F_{4}=4F}
Z
3
=
(
Z
1
+
C
)
2
−
Z
Z
1
−
F
{\displaystyle Z_{3}=(Z_{1}+C)^{2}-ZZ_{1}-F}
E
=
Z
3
2
{\displaystyle E={Z_{3}}^{2}}
G
=
C
F
4
{\displaystyle G=CF_{4}}
H
=
A
F
4
{\displaystyle H=AF_{4}}
X
3
=
D
2
−
G
−
2
H
−
a
3
E
{\displaystyle X_{3}=D^{2}-G-2H-a_{3}E}
Y
3
=
D
(
H
−
X
3
)
−
2
B
G
{\displaystyle Y_{3}=D(H-X_{3})-2BG}
Z
Z
3
=
E
{\displaystyle ZZ_{3}=E}
Let
P
1
=
(
1
,
13
)
{\displaystyle P_{1}=(1,{\sqrt {13}})}
P
2
=
(
0
,
3
)
{\displaystyle P_{2}=(0,{\sqrt {3}})}
R
{\displaystyle \mathbb {R} }
y
2
=
x
3
+
3
(
x
+
1
)
2
{\displaystyle y^{2}=x^{3}+3(x+1)^{2}}
Then:
A
=
X
2
Z
Z
1
=
0
{\displaystyle A=X_{2}ZZ_{1}=0}
B
=
Y
2
Z
Z
1
Z
1
=
3
{\displaystyle B=Y_{2}ZZ_{1}Z_{1}={\sqrt {3}}}
C
=
X
1
−
A
=
1
{\displaystyle C=X_{1}-A=1}
D
=
2
(
Y
1
−
B
)
=
2
(
13
−
3
)
{\displaystyle D=2(Y_{1}-B)=2({\sqrt {13}}-{\sqrt {3}})}
F
=
C
2
=
1
{\displaystyle F=C^{2}=1}
F
4
=
4
F
=
4
{\displaystyle F_{4}=4F=4}
Z
3
=
(
Z
1
+
C
)
2
−
Z
Z
1
−
F
=
2
{\displaystyle Z_{3}=(Z_{1}+C)^{2}-ZZ_{1}-F=2}
E
=
Z
3
2
=
4
{\displaystyle E={Z_{3}}^{2}=4}
G
=
C
F
4
=
4
{\displaystyle G=CF_{4}=4}
H
=
A
F
4
=
0
{\displaystyle H=AF_{4}=0}
X
3
=
D
2
−
G
−
2
H
−
a
3
E
=
48
−
8
39
{\displaystyle X_{3}=D^{2}-G-2H-a_{3}E=48-8{\sqrt {39}}}
Y
3
=
D
(
H
−
X
3
)
−
2
B
G
=
296
3
−
144
13
{\displaystyle Y_{3}=D(H-X_{3})-2BG=296{\sqrt {3}}-144{\sqrt {13}}}
Z
Z
3
=
E
=
4
{\displaystyle ZZ_{3}=E=4}
Notice that in this case
Z
1
=
Z
2
=
1
{\displaystyle Z_{1}=Z_{2}=1}
P
3
=
(
X
3
,
Y
3
,
Z
3
,
Z
Z
3
)
=
(
48
−
8
39
,
296
3
−
144
13
,
2
,
4
)
{\displaystyle P_{3}=(X_{3},Y_{3},Z_{3},ZZ_{3})=(48-8{\sqrt {39}},296{\sqrt {3}}-144{\sqrt {13}},2,4)}
P
3
=
(
12
−
2
39
,
37
3
−
18
13
)
{\displaystyle P_{3}=(12-2{\sqrt {39}},37{\sqrt {3}}-18{\sqrt {13}})}
The following algorithm represents the doubling of a point
P
1
{\displaystyle P_{1}}
a
3
=
3
a
{\displaystyle a_{3}=3a}
a
2
=
2
a
{\displaystyle a_{2}=2a}
2 and a3 respectively, and add indicates the additions.
A
=
X
1
2
{\displaystyle A={X_{1}}^{2}}
B
=
a
2
Z
Z
1
(
X
1
+
Z
Z
1
)
{\displaystyle B=a_{2}ZZ_{1}(X_{1}+ZZ_{1})}
C
=
3
(
A
+
B
)
{\displaystyle C=3(A+B)}
D
=
Y
1
2
{\displaystyle D={Y_{1}}^{2}}
E
=
D
2
{\displaystyle E=D^{2}}
Z
3
=
(
Y
1
+
Z
1
)
2
−
D
−
Z
Z
1
{\displaystyle Z_{3}=(Y_{1}+Z_{1})^{2}-D-ZZ_{1}}
Z
Z
3
=
Z
3
2
{\displaystyle ZZ_{3}=Z_{3}^{2}}
F
=
2
(
(
X
1
+
D
)
2
−
A
−
E
)
{\displaystyle F=2((X_{1}+D)^{2}-A-E)}
X
3
=
C
2
−
a
3
Z
Z
3
−
2
F
{\displaystyle X_{3}=C^{2}-a_{3}ZZ_{3}-2F}
Y
3
=
C
(
F
−
X
3
)
−
8
E
{\displaystyle Y_{3}=C(F-X_{3})-8E}
Let
P
1
=
(
0
,
3
)
{\displaystyle P_{1}=(0,{\sqrt {3}})}
y
2
=
x
3
+
3
(
x
+
1
)
2
{\displaystyle y^{2}=x^{3}+3(x+1)^{2}}
Then:
A
=
X
1
2
=
0
{\displaystyle A={X_{1}}^{2}=0}
B
=
a
2
Z
Z
1
(
X
1
+
Z
Z
1
)
=
2
{\displaystyle B=a_{2}ZZ_{1}(X_{1}+ZZ_{1})=2}
C
=
3
(
A
+
B
)
=
6
{\displaystyle C=3(A+B)=6}
D
=
Y
1
2
=
3
{\displaystyle D={Y_{1}}^{2}=3}
E
=
D
2
=
9
{\displaystyle E=D^{2}=9}
Z
3
=
(
Y
1
+
Z
1
)
2
−
D
−
Z
Z
1
=
2
3
{\displaystyle Z_{3}=(Y_{1}+Z_{1})^{2}-D-ZZ_{1}=2{\sqrt {3}}}
Z
Z
3
=
Z
3
2
=
12
{\displaystyle ZZ_{3}=Z_{3}^{2}=12}
F
=
2
(
(
X
1
+
D
)
2
−
A
−
E
)
=
0
{\displaystyle F=2((X_{1}+D)^{2}-A-E)=0}
X
3
=
C
2
−
a
3
Z
Z
3
−
2
F
=
0
{\displaystyle X_{3}=C^{2}-a_{3}ZZ_{3}-2F=0}
Y
3
=
C
(
F
−
X
3
)
−
8
E
=
−
72
{\displaystyle Y_{3}=C(F-X_{3})-8E=-72}
Notice that here the point is in affine coordinates, so
Z
1
=
1
{\displaystyle Z_{1}=1}
P
3
=
(
0
,
−
72
,
2
3
,
12
)
{\displaystyle P_{3}=(0,-72,2{\sqrt {3}},12)}
P
3
=
(
0
,
−
3
)
{\displaystyle P_{3}=(0,-{\sqrt {3}})}
Any elliptic curve is birationally equivalent to another written in the Weierstrass form.
The following twisted tripling-oriented Doche-Icart-Kohel curve
T
a
,
λ
:
y
2
=
x
3
+
3
λ
a
(
x
+
λ
)
2
{\displaystyle 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
)
↦
(
x
−
λ
a
,
y
)
.
{\displaystyle (x,y)\mapsto (x-\lambda a,y).}
In this way
T
a
,
λ
{\displaystyle T_{a,\lambda }}
y
2
=
x
3
−
3
λ
2
a
(
a
−
2
)
x
+
λ
3
a
(
2
a
2
−
6
a
+
3
)
{\displaystyle y^{2}=x^{3}-3{\lambda }^{2}a(a-2)x+{\lambda }^{3}a(2a^{2}-6a+3)}
Conversely, given an elliptic curve in the Weierstrass form:
E
c
,
d
:
y
2
=
x
3
+
c
x
2
+
d
{\displaystyle 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:
λ
=
−
3
d
(
a
−
2
)
a
(
2
a
2
−
6
a
+
3
)
{\displaystyle \lambda ={\frac {-3d(a-2)}{a(2a^{2}-6a+3)}}}
where a is a root of the polynomial
6912
a
(
a
−
2
)
3
−
j
(
4
a
−
9
)
,
{\displaystyle 6912a(a-2)^{3}-j(4a-9),}
where
j
=
6912
c
3
4
c
3
+
27
d
2
{\displaystyle j={\frac {6912c^{3}}{4c^{3}+27d^{2}}}}
is the j-invariant of the elliptic curve
E
c
,
d
{\displaystyle E_{c,d}}
Notice that in this case the map given is not only a birational equivalence, but an isomorphism between curves.
^ Christophe Doche, Thomas Icart, and David R. Kohel, Efficient Scalar Multiplication by Isogeny Decompositions
^ Christophe Doche, Thomas Icart, and David R. Kohel, Efficient Scalar Multiplication by Isogeny Decompositions , page 198-199
Christophe Doche; Thomas Icart & David R. Kohel (2006). Efficient Scalar Multiplication by Isogeny Decompositions (PDF) . appeared at PKC 2006, part of LNCS (Lecture Series in Computer Science) volume number 3958. Springer Verlag. pp. 285– 352. Daniel J. Bernstein , Tanja Lange (2007). Analysis and optimization of elliptic-curve single-scalar multiplication (PDF) . appeared in G.L. Mullen, D. Panario, I.E. Shparlinski (eds.), Finite Fields and Applications (Proceedings 8th International Conference, Fq8, Melbourne, Australia, July 9–13, 2007). Mathematics Subject Classification.D.J.Bernstein , P.Birkner, T.Lange, and C.Peters (2007). Optimizing Double-Base Elliptic-Curve Single-Scalar Multiplication (PDF) . appeared in K. Srinathan, C. Pandu Rangan , M. Yung (Eds.), Proceedings of the 8th International Conference on Cryptology in India: Progress in Cryptology (Indocrypt 2007) 9–13 December 2007, Chennai, India. Springer.{{cite book }}: CS1 maint: multiple names: authors list (link )http://hyperelliptic.org/EFD/g1p/auto-3dik-standard.html 
