Montgomery curve

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In mathematics the Montgomery curve is a form of elliptic curve, different from the usual Weierstrass form, introduced by Peter L. Montgomery in 1987.[1] It is used for certain computations, and in particular in different cryptography applications.

Definition[edit]

A Montgomery curve of equation

A Montgomery curve over a field K is defined by the equation

for certain A, BK and with B(A2 − 4) ≠ 0.

Generally this curve is considered over a finite field K (for example, over a finite field of q elements, K = Fq) with characteristic different from 2 and with AK ∖ {−2, 2}, BK ∖ {0}, but they are also considered over the rationals with the same restrictions for A and B.

Montgomery arithmetic[edit]

It is possible to do some "operations" between the points of an elliptic curve: "adding" two points consists of finding a third one such that ; "doubling" a point consists of computing (For more information about operations see The group law) and below.

A point on the elliptic curve in the Montgomery form can be represented in Montgomery coordinates , where are projective coordinates and for .

Notice that this kind of representation for a point loses information: indeed, in this case, there is no distinction between the affine points and because they are both given by the point . However, with this representation it is possible to obtain multiples of points, that is, given , to compute .

Now, considering the two points and : their sum is given by the point whose coordinates are:

If , then the operation becomes a "doubling"; the coordinates of are given by the following equations:

The first operation considered above (addition) has a time-cost of 3M+2S, where M denotes the multiplication between two general elements of the field on which the elliptic curve is defined, while S denotes squaring of a general element of the field.

The second operation (doubling) has a time-cost of 2M+2S+1D, where D denotes the multiplication of a general element by a constant; notice that the constant is , so can be chosen in order to have a small D.

Algorithm and example[edit]

The following algorithm represents a doubling of a point on an elliptic curve in the Montgomery form.

It is assumed that . The cost of this implementation is 1M + 2S + 1*A + 3add + 1*4. Here M denotes the multiplications required, S indicates the squarings, and a refers to the multiplication by A.

Example[edit]

Let be a point on the curve . In coordinates , with , .

Then:

The result is the point such that .

Addition[edit]

Given two points , on the Montgomery curve in affine coordinates, the point represents, geometrically the third point of intersection between and the line passing through and . It is possible to find the coordinates of , in the following way:

1) consider a generic line in the affine plane and let it pass through and (impose the condition), in this way, one obtains and ;

2) intersect the line with the curve , substituting the variable in the curve equation with ; the following equation of third degree is obtained:

.

As it has been observed before, this equation has three solutions that correspond to the coordinates of , and . In particular this equation can be re-written as:

3) Comparing the coefficients of the two identical equations given above, in particular the coefficients of the terms of second degree, one gets:

.

So, can be written in terms of , , , , as:

.

4) To find the coordinate of the point it is sufficient to substitute the value in the line . Notice that this will not give the point directly. Indeed, with this method one find the coordinates of the point such that , but if one needs the resulting point of the sum between and , then it is necessary to observe that: if and only if . So, given the point , it is necessary to find , but this can be done easily by changing the sign to the coordinate of . In other words, it will be necessary to change the sign of the coordinate obtained by substituting the value in the equation of the line.

Resuming, the coordinates of the point , are:

Doubling[edit]

Given a point on the Montgomery curve , the point represents geometrically the third point of intersection between the curve and the line tangent to ; so, to find the coordinates of the point it is sufficient to follow the same method given in the addition formula; however, in this case, the line y=lx+m has to be tangent to the curve at , so, if with

,

then the value of l, which represents the slope of the line, is given by:

by the implicit function theorem.

So and the coordinates of the point , are:

.

Equivalence with twisted Edwards curves[edit]

Let be a field with characteristic different from 2.

Let be an elliptic curve in the Montgomery form:

:

with ,

and let be an elliptic curve in the twisted Edwards form:

with , .

The following theorem shows the birational equivalence between Montgomery curves and twisted Edwards curves:[2]

Theorem (i) Every twisted Edwards curve is birationally equivalent to a Montgomery curve over . In particular, the twisted Edwards curve is birationally equivalent to the Montgomery curve where , and .

The map:

is a birational equivalence from to , with inverse:

:

Notice that this equivalence between the two curves is not valid everywhere: indeed the map is not defined at the points or of the .

Equivalence with Weierstrass curves[edit]

Any elliptic curve can be written in Weierstrass form.

So, the elliptic curve in the Montgomery form

: ,

can be transformed in the following way: divide each term of the equation for by , and substitute the variables x and y, with and respectively, to get the equation

.

To obtain a short Weierstrass form from here, it is sufficient to replace u with the variable :

;

finally, this gives the equation:

.

Hence the mapping is given as

:

See also[edit]

Notes[edit]

  1. ^ Peter L. Montgomery (1987). "Speeding the Pollard and Elliptic Curve Methods of Factorization". Mathematics of Computation. 48 (177): 243–264. doi:10.2307/2007888. JSTOR 2007888. 
  2. ^ Daniel J. Bernstein, Peter Birkner, Marc Joye, Tanja Lange and Christiane Peters (2008). Twisted Edwards Curves (PDF). Springer-Verlag Berlin Heidelberg. ISBN 978-3-540-68159-5. 

References[edit]

External links[edit]