Tripling-oriented Doche–Icart–Kohel curve

The tripling-oriented Doche–Icart–Kohel curve is a form of an elliptic curve

Elliptic curve

In mathematics, an elliptic curve is a smooth, projective algebraic curve of genus one, on which there is a specified point O. An elliptic curve is in fact an abelian variety — that is, it has a multiplication defined algebraically with respect to which it is a group — and O serves as the identity...

 that has been used lately in cryptography

Cryptography

Cryptography is the practice and study of techniques for secure communication in the presence of third parties...

; it is a particular type of Weierstrass curve

Elliptic curve

In mathematics, an elliptic curve is a smooth, projective algebraic curve of genus one, on which there is a specified point O. An elliptic curve is in fact an abelian variety — that is, it has a multiplication defined algebraically with respect to which it is a group — and O serves as the identity...

. At certain conditions some operations

Operation (mathematics)

The general operation as explained on this page should not be confused with the more specific operators on vector spaces. For a notion in elementary mathematics, see arithmetic operation....

, 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 (mathematics)

In abstract algebra, a field is a commutative ring whose nonzero elements form a group under multiplication. As such it is an algebraic structure with notions of addition, subtraction, multiplication, and division, satisfying certain axioms...

 of characteristic

Characteristic (algebra)

In mathematics, the characteristic of a ring R, often denoted char, is defined to be the smallest number of times one must use the ring's multiplicative identity element in a sum to get the additive identity element ; the ring is said to have characteristic zero if this repeated sum never reaches...

 different form 2 and 3.

An elliptic curve in tripling oriented Doche–Icart–Kohel form is defined by the equation

Equation

An equation is a mathematical statement that asserts the equality of two expressions. In modern notation, this is written by placing the expressions on either side of an equals sign , for examplex + 3 = 5\,asserts that x+3 is equal to 5...

:

with .

A general point

Point (geometry)

In geometry, topology and related branches of mathematics a spatial point is a primitive notion upon which other concepts may be defined. In geometry, points are zero-dimensional; i.e., they do not have volume, area, length, or any other higher-dimensional analogue. In branches of mathematics...

 P on has affine coordinates

Affine space

In mathematics, an affine space is a geometric structure that generalizes the affine properties of Euclidean space. In an affine space, one can subtract points to get vectors, or add a vector to a point to get another point, but one cannot add points. In particular, there is no distinguished point...

 . The "point at infinity" represents the neutral element

Identity element

In mathematics, an identity element is a special type of element of a set with respect to a binary operation on that set. It leaves other elements unchanged when combined with them...

 for the group law and it is written in projective coordinates

Projective space

In mathematics a projective space is a set of elements similar to the set P of lines through the origin of a vector space V. The cases when V=R2 or V=R3 are the projective line and the projective plane, respectively....

 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

Affine space

In mathematics, an affine space is a geometric structure that generalizes the affine properties of Euclidean space. In an affine space, one can subtract points to get vectors, or add a vector to a point to get another point, but one cannot add points. In particular, there is no distinguished point...

:

with .

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

Integer

The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...

, using addition and doubling; computing multiples of points is important in elliptic curve cryptography

Elliptic curve cryptography

Elliptic curve cryptography is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. The use of elliptic curves in cryptography was suggested independently by Neal Koblitz and Victor S...

 and in Lenstra elliptic curve factorization

Lenstra elliptic curve factorization

The Lenstra elliptic curve factorization or the elliptic curve factorization method is a fast, sub-exponential running time algorithm for integer factorization which employs elliptic curves. For general purpose factoring, ECM is the third-fastest known factoring method...

.

Addition

Given and on , the point has coordinates:

Doubling

Given a point on , the point has coordinates:

Negation

Given a point on , its negation

Additive inverse

In mathematics, the additive inverse, or opposite, of a number a is the number that, when added to a, yields zero.The additive inverse of a is denoted −a....

 with respect to the neutral element is .

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 (Jⁿ):

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

Affine space

In mathematics, an affine space is a geometric structure that generalizes the affine properties of Euclidean space. In an affine space, one can subtract points to get vectors, or add a vector to a point to get another point, but one cannot add points. In particular, there is no distinguished 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 (that is the addition between two points in different systems of coordinates

Coordinate system

In geometry, a coordinate system is a system which uses one or more numbers, or coordinates, to uniquely determine the position of a point or other geometric element. The order of the coordinates is significant and they are sometimes identified by their position in an ordered tuple and sometimes by...

) more efficient.

The neutral element

Identity element

In mathematics, an identity element is a special type of element of a set with respect to a binary operation on that set. It leaves other elements unchanged when combined with them...

 in new Jacobian coordinates is .

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₃, 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₂ and a₃ 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

Birational geometry

In mathematics, birational geometry is a part of the subject of algebraic geometry, that deals with the geometry of an algebraic variety that is dependent only on its function field. In the case of dimension two, the birational geometry of algebraic surfaces was largely worked out by the Italian...

 to another written in the Weierstrass form.

The following twisted tripling-oriented Doche-Icart-Kohel curve:

:

can be transformed into the Weierstrass form by the map

Map (mathematics)

In most of mathematics and in some related technical fields, the term mapping, usually shortened to map, is either a synonym for function, or denotes a particular kind of function which is important in that branch, or denotes something conceptually similar to a function.In graph theory, a map is a...

:

.

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

Equation solving

In mathematics, to solve an equation is to find what values fulfill a condition stated in the form of an equation . These expressions contain one or more unknowns, which are free variables for which values are sought that cause the condition to be fulfilled...

 of the polynomial .

Here is the j-invariant

J-invariant

In mathematics, Klein's j-invariant, regarded as a function of a complex variable τ, is a modular function defined on the upper half-plane of complex numbers.We haveThe modular discriminant \Delta is defined as \Delta=g_2^3-27g_3^2...

 of the elliptic curve .

Notice that in this case the map given is not only a birational equivalence, but an isomorphism

Isomorphism

In abstract algebra, an isomorphism is a mapping between objects that shows a relationship between two properties or operations.  If there exists an isomorphism between two structures, the two structures are said to be isomorphic.  In a certain sense, isomorphic structures are...

 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

Table of costs of operations in elliptic curves

This table relates to the computational cost for certain operations used in elliptic curve cryptography, used in practice for strong cryptographic security of a public key system. The columns of the table are labelled by various computational steps...