The tripling-oriented Doche–Icart–Kohel curve is a form of an
elliptic curve
In mathematics, an elliptic curve is a smooth, projective, algebraic curve of genus one, on which there is a specified point . An elliptic curve is defined over a field and describes points in , the Cartesian product of with itself. If ...
that has been used lately in
cryptography
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adve ...
; it is a particular type of
Weierstrass curve. At certain conditions some
operations
Operation or Operations may refer to:
Arts, entertainment and media
* ''Operation'' (game), a battery-operated board game that challenges dexterity
* Operation (music), a term used in musical set theory
* ''Operations'' (magazine), Multi-Man ...
, 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 has been introduced by Christophe Doche, Thomas Icart, and David R. Kohel in
Definition
Let
be a
field
Field may refer to:
Expanses of open ground
* Field (agriculture), an area of land used for agricultural purposes
* Airfield, an aerodrome that lacks the infrastructure of an airport
* Battlefield
* Lawn, an area of mowed grass
* Meadow, a grass ...
of
characteristic different form 2 and 3.
An elliptic curve in tripling oriented Doche–Icart–Kohel form is defined by the
equation:
:
with
.
A general
point ''P'' on
has
affine coordinates
In mathematics, an affine space is a geometric structure that generalizes some of the properties of Euclidean spaces in such a way that these are independent of the concepts of distance and measure of angles, keeping only the properties relate ...
. The "point at infinity" represents the
neutral element
In mathematics, an identity element, or neutral element, of a binary operation operating on a set is an element of the set that leaves unchanged every element of the set when the operation is applied. This concept is used in algebraic structures ...
for the group law and it is written in
projective coordinates
In mathematics, homogeneous coordinates or projective coordinates, introduced by August Ferdinand Möbius in his 1827 work , are a system of coordinates used in projective geometry, just as Cartesian coordinates are used in Euclidean geometry. Th ...
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
In mathematics, an affine space is a geometric structure that generalizes some of the properties of Euclidean spaces in such a way that these are independent of the concepts of distance and measure of angles, keeping only the properties relate ...
:
:
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 ''
'', where ''n'' is an
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
, using addition and doubling; computing multiples of points is important in
elliptic curve cryptography
Elliptic-curve cryptography (ECC) is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. ECC allows smaller keys compared to non-EC cryptography (based on plain Galois fields) to provide e ...
and in
Lenstra elliptic curve factorization
The Lenstra elliptic-curve factorization or the elliptic-curve factorization method (ECM) is a fast, sub- exponential running time, algorithm for integer factorization, which employs elliptic curves. For general-purpose factoring, ECM is the t ...
.
Addition
Given
and
on
, the point
has coordinates:
:
Doubling
Given a point
on
, the point
has coordinates:
:
Negation
Given a point
on
, its
negation
In logic, negation, also called the logical complement, is an operation that takes a proposition P to another proposition "not P", written \neg P, \mathord P or \overline. It is interpreted intuitively as being true when P is false, and fals ...
with respect to the neutral element
is
.
There are also other formulas given in
[Christophe Doche, Thomas Icart, and David R. Kohel, ''Efficient Scalar Multiplication by Isogeny Decompositions'', page 198-199] 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 (J
n):
a point in the new Jacobian coordinates is of the form
; moreover:
:
for any
.
This means, for example, that the point
and the point
(for
) are actually the same.
So, an
affine point on
is written in the new Jacobian coordinates as
, where
and
; in this way, the equation for
becomes:
:
The term
of a point on the curve makes the mixed
addition
Addition (usually signified by the plus symbol ) is one of the four basic operations of arithmetic, the other three being subtraction, multiplication and division. The addition of two whole numbers results in the total amount or ''sum'' of ...
(that is the addition between two points in different
systems of coordinates) more efficient.
The
neutral element
In mathematics, an identity element, or neutral element, of a binary operation operating on a set is an element of the set that leaves unchanged every element of the set when the operation is applied. This concept is used in algebraic structures ...
in new Jacobian coordinates is
.
Algorithms and examples
Addition
The following algorithm represents the sum of two points
and
on an elliptic curve in the Tripling-oriented Doche-Icart-Kohel form. The result is a point
.
It is assumed that
and that
.
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 a
3, add represents the number of additions required.
Example
Let
and
affine points on the elliptic curve over
:
.
Then:
Notice that in this case
.
The resulting point is
, that in affine coordinates is
.
Doubling
The following algorithm represents the doubling of a point
on an elliptic curve in the Tripling-oriented Doche-Icart-Kohel form.
It is assumed that
,
.
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 a
2 and a
3 respectively, and add indicates the additions.
Example
Let
be a point on
.
Then:
Notice that here the point is in affine coordinates, so
.
The resulting point is
, that in affine coordinates is
.
Equivalence with Weierstrass form
Any elliptic curve is
birationally equivalent
In mathematics, birational geometry is a field of algebraic geometry in which the goal is to determine when two algebraic varieties are isomorphic outside lower-dimensional subsets. This amounts to studying mappings that are given by rational ...
to another written in the Weierstrass form.
The following
twisted Twisted may refer to:
Film and television
* ''Twisted'' (1986 film), a horror film by Adam Holender starring Christian Slater
* ''Twisted'' (1996 film), a modern retelling of ''Oliver Twist''
* ''Twisted'', a 2011 Singapore Chinese film directed ...
tripling-oriented Doche-Icart-Kohel curve:
:
can be transformed into the Weierstrass form by the
map:
:
In this way
becomes:
:
.
Conversely, given an elliptic curve in the Weierstrass form:
:
,
it is possible to find the "corresponding" Tripling-oriented Doche–Icart–Kohel curve, using the following relation:
:
where is a
root
In vascular plants, the roots are the organs of a plant that are modified to provide anchorage for the plant and take in water and nutrients into the plant body, which allows plants to grow taller and faster. They are most often below the sur ...
of the polynomial
:
where
:
is the
j-invariant
In mathematics, Felix Klein's -invariant or function, regarded as a function of a complex variable , is a modular function of weight zero for defined on the upper half-plane of complex numbers. It is the unique such function which is holom ...
of the elliptic curve
.
Notice that in this case the map given is not only a birational equivalence, but an
isomorphism
In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word i ...
between curves.
Internal link
For more informations about the running-time required in a specific case, see
Table of costs of operations in elliptic curves
Elliptic curve cryptography is a popular form of public key encryption that is based on the mathematical theory of elliptic curves. Points on an elliptic curve can be added and form a group under this addition operation. This article describe ...
Notes
External links
* http://hyperelliptic.org/EFD/g1p/index.html
References
*
*
*
*http://hyperelliptic.org/EFD/g1p/auto-3dik-standard.html
{{DEFAULTSORT:Tripling-oriented Doche-Icart-Kohel curve
Elliptic curves
Elliptic curve cryptography