Montgomery curve

In mathematics the Montgomery curve is a form of elliptic curve introduced by Peter L. Montgomery in 1987, different from the usual Weierstrass form. It is used for certain computations, and in particular in different cryptography applications. 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. 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. The following algorithm represents a doubling of a point on an elliptic curve in the Montgomery form.