Montgomery curve

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


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 A ≠ ±2 and B ≠ 0, but they are also considered over the rationals with the same restrictions for A and B.

Montgomery arithmeticEdit

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 exampleEdit

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.



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



The result is the point   such that  .


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:



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 curvesEdit

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:



The following theorem shows the birational equivalence between Montgomery curves and twisted Edwards curve:[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 curvesEdit

Any elliptic curve can be written in Weierstrass form. In particular, 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


In contrast, an elliptic curve over base field   in Weierstrass form


can be converted to Montgomery form if and only if   has order divisible by four and satisfies the following conditions:[3]

  1.   has at least one root  ; and
  2.   is a quadratic residue in  .

When these conditions are satisfied, then for   we have the mapping


See alsoEdit


  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". Progress in Cryptology – AFRICACRYPT 2008. Lecture Notes in Computer Science. Vol. 5023. Springer-Verlag Berlin Heidelberg. pp. 389–405. doi:10.1007/978-3-540-68164-9_26. ISBN 978-3-540-68159-5.{{cite book}}: CS1 maint: multiple names: authors list (link)
  3. ^ Katsuyuki Okeya, Hiroyuki Kurumatani, and Kouichi Sakurai (2000). Elliptic Curves with the Montgomery-Form and Their Cryptographic Applications. Public Key Cryptography (PKC2000). doi:10.1007/978-3-540-46588-1_17.{{cite conference}}: CS1 maint: multiple names: authors list (link)


External linksEdit