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.

A Montgomery curve over a field K is defined by the equation for certain A, B ∈ K 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.

; "doubling" a point consists of computing

(For more information about operations see The group law) and below.

on the elliptic curve in the Montgomery form

Notice that this kind of representation for a point loses information: indeed, in this case, there is no distinction between the affine points

However, with this representation it is possible to obtain multiples of points, that is, given

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

can be chosen in order to have a small D. The following algorithm represents a doubling of a point

on an elliptic curve in the Montgomery form.

represents, geometrically the third point of intersection between

, in the following way: 1) consider a generic line

; the following equation of third degree is obtained: As it has been observed before, this equation has three solutions that correspond to the

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,

Indeed, with this method one find the coordinates of the point

represents geometrically the third point of intersection between the curve and the line tangent to

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

with then the value of l, which represents the slope of the line, is given by: by the implicit function theorem.

be an elliptic curve in the Montgomery form: with

be an elliptic curve in the twisted Edwards form: with

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

is birationally equivalent to the Montgomery curve

, with inverse: Notice that this equivalence between the two curves is not valid everywhere: indeed the map

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

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

has order divisible by four and satisfies the following conditions:[3] When these conditions are satisfied, then for