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. Definition. A Montgomery curve over a field is defined by the equation for certain and with . Generally this curve is considered over a finite field "K" (for example, over a finite field of elements, ) with characteristic different from 2 and with and , but they are also considered over the rationals with the same restrictions for and . Montgomery arithmetic. It is possible  to do some "operations" between the points of an elliptic curve: "adding" two points formula_2 consists of finding a third one formula_3 such that formula_4; "doubling" a point consists of computing formula_5 (For more information about operations see The group law) and below. A point formula_6 on the elliptic curve in the Montgomery form formula_7 can be represented in Montgomery coordinates formula_8, where formula_8 are projective coordinates and formula_10 for formula_11. Notice that this kind of representation for a point loses information: indeed, in this case, there is no distinction between the affine points formula_12 and formula_13 because they are  both given by the point formula_14. However, with this representation it is possible to obtain multiples of points, that is, given formula_8, to compute formula_16. Now, considering the two points formula_17 and formula_18: their sum is given by the point formula_19 whose coordinates are: If formula_22, then the operation becomes a "doubling"; the coordinates of formula_23 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 formula_27, so formula_28 can be chosen in order to have a small D. Algorithm and example. The following algorithm represents a doubling of a point formula_29 on an elliptic curve in the Montgomery form. It is assumed that formula_30. 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. Let formula_34 be a point on the curve formula_35. In coordinates formula_36, with formula_37, formula_38. Then: The result is the point formula_42 such that formula_43. Addition. Given two points formula_44, formula_45 on the Montgomery curve formula_46 in affine coordinates, the point formula_47 represents, geometrically the third point of intersection between formula_46 and the line passing through formula_49 and formula_50. It is possible to find the coordinates formula_51 of formula_52, in the following way: 1) consider a generic line formula_53 in the affine plane and let it pass through formula_49  and formula_50 (impose the condition), in this way, one obtains formula_56 and formula_57; 2) intersect the line with the curve formula_46, substituting the formula_59 variable in the curve equation with formula_53; the following equation of third degree is obtained: As it has been observed before, this equation has three solutions that correspond to the formula_62 coordinates of formula_49, formula_50 and formula_52. 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, formula_68 can be written in terms  of formula_69, formula_70, formula_71, formula_72, as: 4) To find the formula_59 coordinate of the point formula_52 it is sufficient to substitute the value formula_68 in the line formula_53. Notice that this will not give the point formula_52 directly. Indeed, with this method one find the coordinates of the point formula_79 such that formula_80, but if one needs the resulting point of the sum between formula_49 and formula_50, then it is necessary to observe that: formula_80 if and only if formula_84. So, given the point formula_79, it is necessary to find formula_86, but this can be done easily by changing the  sign to the formula_59 coordinate of formula_79. In other words, it will be necessary to change the sign of the formula_59 coordinate obtained by substituting the value formula_68 in the equation of the line. Resuming, the coordinates of the point formula_91, formula_47 are: Doubling. Given a point formula_49 on the Montgomery curve formula_46, the point formula_97 represents geometrically the third point of intersection between the curve and the line tangent to formula_49; so, to find the coordinates of the point formula_99 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 formula_49, so, if formula_101 with then the value of "l", which represents the slope of the line, is given by: by the implicit function theorem. So formula_104 and the coordinates of the point formula_52, formula_99 are: Equivalence with twisted Edwards curves. Let formula_108 be a field with characteristic different from 2. Let formula_46 be an elliptic curve in the Montgomery form: with formula_111, formula_112 and let formula_113 be an elliptic curve in the twisted Edwards form: with formula_115 The following theorem shows the birational equivalence between Montgomery  curves and twisted Edwards curve: Theorem (i) Every twisted Edwards curve is birationally equivalent to a Montgomery curve over formula_108. In particular, the twisted Edwards curve formula_113 is birationally equivalent to the Montgomery curve formula_46 where formula_119, and formula_120. The map: is a birational equivalence from formula_113 to formula_46, with inverse: Notice that this equivalence between the two curves is not valid everywhere: indeed the map formula_128 is not defined at the points formula_129 or formula_130 of the formula_46. Equivalence with Weierstrass curves. 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 formula_46 by formula_135, and substitute the variables "x" and "y", with formula_136 and formula_137 respectively, to get the equation To obtain a short Weierstrass form from here, it is sufficient to replace "u" with the variable formula_139: finally, this gives the equation: Hence the mapping is given as In contrast, an elliptic curve over base field formula_145 in Weierstrass form can be converted to Montgomery form if and only if formula_146 has order divisible by four and satisfies the following conditions: When these conditions are  satisfied, then for formula_153 we have the mapping