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[]
A Montgomery curve of equation
![{\textstyle {\frac {1}{4}}y^{2}=x^{3}+{\frac {5}{2}}x^{2}+x}](https://wikimedia.org/api/rest_v1/media/math/render/svg/90441f11d233c0173b69eda000d6ed0192d6874f)
A Montgomery curve over a field K is defined by the equation
![{\displaystyle M_{A,B}:By^{2}=x^{3}+Ax^{2}+x}](https://wikimedia.org/api/rest_v1/media/math/render/svg/442cda26be6a0633cb59f817e5933625b67aa493)
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.
Montgomery arithmetic[]
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:
![X_{m+n} = Z_{m-n}((X_m-Z_m)(X_n+Z_n)+(X_m+Z_m)(X_n-Z_n))^2](https://wikimedia.org/api/rest_v1/media/math/render/svg/4b0f17b85bf890fca81b007b7303143cdc40268b)
![Z_{m+n} = X_{m-n}((X_m-Z_m)(X_n+Z_n)-(X_m+Z_m)(X_n-Z_n))^2](https://wikimedia.org/api/rest_v1/media/math/render/svg/476f6b678ae046e7934f8e9ad89193cfb94ce3db)
If
, then the operation becomes a "doubling"; the coordinates of
are given by the following equations:
![4X_nZ_n = (X_n+Z_n)^2 - (X_n-Z_n)^2](https://wikimedia.org/api/rest_v1/media/math/render/svg/ea40cfd9be313ac46148acc1e2ce697d3fbc7bcd)
![X_{2n} = (X_n+Z_n)^2(X_n-Z_n)^2](https://wikimedia.org/api/rest_v1/media/math/render/svg/cbbc201c9240078b452987ad02c03595e7f589df)
![Z_{2n} = (4X_nZ_n)((X_n-Z_n)^2+((A+2)/4)(4X_nZ_n))](https://wikimedia.org/api/rest_v1/media/math/render/svg/f7695802b7b703643e17156916de0f0291ef4d8d)
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[]
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.
![XX_1 = X_1^2 \,](https://wikimedia.org/api/rest_v1/media/math/render/svg/2f0e5ed7bd82f5726d6b657ecd39c55cd5a41f7c)
![{\displaystyle X_{2}=(XX_{1}-1)^{2}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c665c68c35462f435d62a9ff594aa069b7c04e4d)
![{\displaystyle Z_{2}=4X_{1}(XX_{1}+aX_{1}+1)\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f967097dc4a57471ad069e8ea2d34ee747ac62a8)
Example[]
Let
be a point on the curve
.
In coordinates
, with
,
.
Then:
![XX_1 = X_1^2 = 4 \,](https://wikimedia.org/api/rest_v1/media/math/render/svg/f3e16e1acc2cfdb75c18deb8c77bfd178bc83fa5)
![{\displaystyle X_{2}=(XX_{1}-1)^{2}=9\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d3dd9da175d6c96974b427ced3b090c53561b3e2)
![{\displaystyle Z_{2}=4X_{1}(XX_{1}+AX_{1}+1)=24\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/faf3ebfa98ba06b4e7cddcf6f0e391d82802eb3f)
The result is the point
such that
.
Addition[]
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:
![{\displaystyle x^{3}+(A-Bl^{2})x^{2}+(1-2Blm)x-Bm^{2}=0.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2830c3fab88b12e0bd66074d7bf441d3644ccea3)
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:
![(x-x_1)(x-x_2)(x-x_3)=0](https://wikimedia.org/api/rest_v1/media/math/render/svg/b49e885cdcfc022717f4aa9e5e8e367f4fdb7aca)
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:
![{\displaystyle x_{3}=B\left({\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}\right)^{2}-A-x_{1}-x_{2}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/91a22ee8c2db6cf8ad2a2bda6c506420140b0f72)
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:
![x_3 = \frac{B(y_2-y_1)^2}{(x_2-x_1)^2}-A-x_1-x_2=\frac{B(x_2y_1-x_1y_2)^2}{x_1x_2(x_2-x_1)^2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ac1b977d44f6a84a92d52ab2c55fc651669478c4)
![y_3 = \frac{(2x_1+x_2+A)(y_2-y_1)}{x_2-x_1}-\frac{B(y_2-y_1)^3}{(x_2-x_1)^3}-y_1](https://wikimedia.org/api/rest_v1/media/math/render/svg/96251d347f7e12e04f7cc684b6c8eebbf729bf6b)
Doubling[]
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
![{\displaystyle f(x,y)=x^{3}+Ax^{2}+x-By^{2},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0a24124d8a79b42c164b7b8ba9d34763130323d8)
then the value of l, which represents the slope of the line, is given by:
![l=-\left.\frac{\partial f}{\partial x}\right/\frac{\partial f}{\partial y }](https://wikimedia.org/api/rest_v1/media/math/render/svg/27e5343df6367c6f9613178892d909eeaecb44ab)
by the implicit function theorem.
So
and the coordinates of the point
,
are:
![{\displaystyle {\begin{aligned}x_{3}&=Bl^{2}-A-x_{1}-x_{1}={\frac {B(3x_{1}^{2}+2Ax_{1}+1)^{2}}{(2By_{1})^{2}}}-A-x_{1}-x_{1}\\&={\frac {(x_{1}^{2}-1)^{2}}{4By_{1}^{2}}}={\frac {(x_{1}^{2}-1)^{2}}{4x_{1}(x_{1}^{2}+Ax_{1}+1)}}\\[8pt]y_{3}&=(2x_{1}+x_{1}+A)l-Bl^{3}-y_{1}\\&={\frac {(2x_{1}+x_{1}+A)(3{x_{1}}^{2}+2Ax_{1}+1)}{2By_{1}}}-{\frac {B(3{x_{1}}^{2}+2Ax_{1}+1)^{3}}{(2By_{1})^{3}}}-y_{1}.\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2ce2a17af104efe86d0db8f1b044f868fde9e710)
Equivalence with twisted Edwards curves[]
Let
be a field with characteristic different from 2.
Let
be an elliptic curve in the Montgomery form:
![{\displaystyle M_{A,B}:Bv^{2}=u^{3}+Au^{2}+u}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1c15f710abd67a4be758200e375100477d89d2f8)
with
,
and let
be an elliptic curve in the twisted Edwards form:
![E_{a,d}\ :\ ax^2 + y^2 = 1 + dx^2y^2, \,](https://wikimedia.org/api/rest_v1/media/math/render/svg/c13c6ef64b22c9116e8a2e80e4a94cf6e23aba74)
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
.
In particular, the twisted Edwards curve
is birationally equivalent to the Montgomery curve
where
, and
.
The map:
![\psi\,:\,E_{a,d} \rightarrow M_{A,B}](https://wikimedia.org/api/rest_v1/media/math/render/svg/808bdb74992b80edd8afea13e163b29c0f91ce86)
![(x,y) \mapsto (u,v) = \left(\frac{1+y}{1-y},\frac{1+y}{(1-y)x}\right)](https://wikimedia.org/api/rest_v1/media/math/render/svg/5ebeeafaa685bec69282ed1b55e2a721d01ca6cf)
is a birational equivalence from
to
, with inverse:
: ![M_{A,B} \rightarrow E_{a,d}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8f7936dcc404b51bd5fd02050b3c1714e888e9ae)
![(u,v) \mapsto (x,y) = \left(\frac{u}{v},\frac{u-1}{u+1}\right),
a=\frac{A+2}{B}, d=\frac{A-2}{B}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4837ad2123e2a1571860d66d010dd394a50b8528)
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[]
Any elliptic curve can be written in Weierstrass form. In particular, the elliptic curve in the Montgomery form
: ![{\displaystyle By^{2}=x^{3}+Ax^{2}+x,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a8ccc51b12e1092c3cbdf1ae5c5d0513fdac261e)
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
![{\displaystyle v^{2}=u^{3}+{\frac {A}{B}}u^{2}+{\frac {1}{B^{2}}}u.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/82a91d980907ee82eef33f9c2d53f78d8e31399d)
To obtain a short Weierstrass form from here, it is sufficient to replace u with the variable
:
![{\displaystyle v^{2}=\left(t-{\frac {A}{3B}}\right)^{3}+{\frac {A}{B}}\left(t-{\frac {A}{3B}}\right)^{2}+{\frac {1}{B^{2}}}\left(t-{\frac {A}{3B}}\right);}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d3a5adc9c1ccce5c9a5c5dcdc6ae21967e9b8a89)
finally, this gives the equation:
![{\displaystyle v^{2}=t^{3}+\left({\frac {3-A^{2}}{3B^{2}}}\right)t+\left({\frac {2A^{3}-9A}{27B^{3}}}\right).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/644d1c775800dce1327795b07315427219ca4821)
Hence the mapping is given as
: ![{\displaystyle M_{A,B}\rightarrow E_{a,b}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/03fd874706e684ee0699114b9dca8410f5bebf7e)
![{\displaystyle (x,y)\mapsto (t,v)=\left({\frac {x}{B}}+{\frac {A}{3B}},{\frac {y}{B}}\right),a={\frac {3-A^{2}}{3B^{2}}},b={\frac {2A^{3}-9A}{27B^{3}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cb6d429b73e8f9f0f3b7c3d40dd631a62c84b2b3)
In contrast, an elliptic curve over base field
in Weierstrass form
: ![{\displaystyle v^{2}=t^{3}+at+b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6c71f66d30677e762b5c31d45604a0a8dae92853)
can be converted to Montgomery form if and only if
has order divisible by four and satisfies the following conditions:[3]
has at least one root
; and
is a quadratic residue in
.
When these conditions are satisfied, then for
we have the mapping
: ![{\displaystyle E_{a,b}\rightarrow M_{A,B}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dbfe66cc8364d3b9192af8f9fc7fdc2e3d8e0f5c)
.
See also[]
Notes[]
References[]
External links[]