In mathematics

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, the doubling-oriented Doche–Icart–Kohel curve is a form in which 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...

 can be written. It is a special case of Weierstrass form and it is also 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...

 because the doubling speeds up considerably (computing as composition of 2-isogeny

Isogeny

In mathematics, an isogeny is a morphism of varieties between two abelian varieties that is surjective and has a finite kernel....

 and its dual

Dual abelian variety

In mathematics, a dual abelian variety can be defined from an abelian variety A, defined over a field K.-Definition:To an abelian variety A over a field k, one associates a dual abelian variety Av , which is the solution to the following moduli problem...

).
It 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...

 and let . Then, the Doubling-oriented Doche–Icart–Kohel curve with parameter

Parameter

Parameter from Ancient Greek παρά also “para” meaning “beside, subsidiary” and μέτρον also “metron” meaning “measure”, can be interpreted in mathematics, logic, linguistics, environmental science and other disciplines....

 a 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...

 is represented by:



Equivalently, 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....

:



with and .

Notice that, since this curve is an special case of Weierstrass form

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...

, transformations to the most common form of elliptic curve (Weierstrass form) are not needed.

Group law

It is interesting to analyze the group law 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...

, defining the addition and doubling formulas, because these formulas are necessary to compute multiples of points [n]P (see Exponentiation by squaring

Exponentiation by squaring

Exponentiating by squaring is a general method for fast computation of large integer powers of a number. Some variants are commonly referred to as square-and-multiply algorithms or binary exponentiation. In additive notation the appropriate term is double-and-add...

). In general, the group law is defined in the following way: if three points lies in the same line then they sum up to zero. So, by this property, the group laws are different for every curve shape.

In this case, since these curves are special cases of Weierstrass curves, the addition is just the standard addition on Weierstrass curves. On the other hand, to double a point, the standard doubling formula can be used, but it would not be so fast.
In this case, 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...

 is (in projective coordinates), for which . Then, if is a non-trivial element (), then the inverse of this point (by addition) is –P=(x,-y).

Addition

In this case, 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...

 will be used to define the addition formula:

(x₁,y₁)+(x₂,y₂)=(x₃,y₃) where

x₃ = (-x₁³+(x₂-a)x₁²+(x₂²+2ax₂)x₁+(y₁²-2y₂y₁+(-x₂³-ax₂²+y₂²)))/(x₁²-2x₂x₁+x₂²)

y₃ = ((-y₁+2y₂)x₁³+(-ay₁+(-3y₂x₂+ay₂))x₁²+((3x₂²+2ax₂)y₁-2ay₂x₂)x₁+(y₁³-3y₂y₁²+(-2x₂³-ax₂²+3y₂²)y₁+(y₂x₂³+ay₂x₂²-y₂³)))/(-x₁³+3x₂x₁²-3x₂²x₁+x₂³)

Doubling

2(x₁,y₁)=(x₃,y₃)

x₃ = 1/(4y₁²)x₁⁴-8a/y₁²x₁²+64a2/y₁²

y₃ = 1/(8y₁³)x₁⁶+((-a²+40a)/(4y₁³))x₁⁴+((ay₁²+(16a³-640a²))/(4y₁³))x₁²+((-4a²y₁²-512a³)/y₁³)

Addition

The fastest addition is the following one (comparing with the results given in: http://hyperelliptic.org/EFD/g1p/index.html), and the cost that it takes is 4 multiplications, 4 squaring and 10 addition.

A = Y₂-Y₁

AA = A²

B = X₂-X₁

CC = B²

F = X₁CC

Z₃ = 2CC

D = X₂Z₃

ZZ₃ = Z₃²

X₃ = 2(AA-F)-aZ₃-D

Y₃ = ((A+B)²-AA-CC)(D-X₃)-Y₂ZZ₃

Example

Let . Let P=(X₁,Y₁)=(2,1), Q=(X₂,Y₂)=(1,-1) and a=1, then

A=2

AA=4

B=1

CC=1

F=2

Z₃=4

D=4

ZZ₃=16

X₃=-4

Y₃=336

Thus, P+Q=(-4:336:4)

Doubling

The following algorithm is the fastest one (see the following link to compare: http://hyperelliptic.org/EFD/g1p/index.html), and the cost that it takes is 1 multiplication, 5 squaring and 7 additions.

A = X₁²

B = A-a16

C = a₂A

YY = Y₁²

YY₂ = 2YY

Z₃ = 2YY₂

X₃ = B²

V = (Y₁+B)2-YY-X₃

Y₃ = V(X₃+64C+a(YY₂-C))

ZZ₃ = Z₃²

Example

Let and a=1. Let P=(-1,2), then Q=[2]P=(x3,y3) is given by:

A=1

B=-15

C=2

YY=4

YY₂=8

Z₃=16

X₃=225

V=27

Y₃=9693

ZZ₃=256

Thus, Q=(225:9693:16).

Extended coordinates

The addition and doubling computations should be as fast as possible, so it is more convenient to use the following representation of the coordinates:

are represented by satisfying the following equations:







Then, the Doubling-oriented Doche–Icart–Kohel curve is given by the following equation:

.

In this case, is a general point with inverse .
Furthermore, the points over the curve satisfy: for all non zero.

Faster doubling formulas for these curves and mixed-addition formulas were introduced by Doche, Icart and Kohel; but nowadays, these formulas are improved by Daniel J. Bernstein and Tanja Lange (see below the link of EFD).

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...