Montgomery curve

From Wikipedia, the free encyclopedia

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 over a field K is defined by the equation

${\displaystyle M_{A,B}:By^{2}=x^{3}+Ax^{2}+x}${\displaystyle M_{A,B}:By^{2}=x^{3}+Ax^{2}+x}

for certain A, B ∈ K and with B(A² − 4) ≠ 0.

Generally this curve is considered over a finite field K (for example, over a finite field of q elements, K = F_q) 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 ${\displaystyle P,Q}${\displaystyle P,Q} consists of finding a third one ${\displaystyle R}${\displaystyle R} such that ${\displaystyle R=P+Q}${\displaystyle R=P+Q}; "doubling" a point consists of computing ${\displaystyle [2]P=P+P}${\displaystyle [2]P=P+P} (For more information about operations see The group law) and below.

A point ${\displaystyle P=(x,y)}${\displaystyle P=(x,y)} on the elliptic curve in the Montgomery form ${\displaystyle By^{2}=x^{3}+Ax^{2}+x}${\displaystyle By^{2}=x^{3}+Ax^{2}+x} can be represented in Montgomery coordinates ${\displaystyle P=(X:Z)}${\displaystyle P=(X:Z)}, where ${\displaystyle P=(X:Z)}${\displaystyle P=(X:Z)} are projective coordinates and ${\displaystyle x=X/Z}${\displaystyle x=X/Z} for ${\displaystyle Z\neq 0}${\displaystyle Z\neq 0}.

Notice that this kind of representation for a point loses information: indeed, in this case, there is no distinction between the affine points ${\displaystyle (x,y)}${\displaystyle (x,y)} and ${\displaystyle (x,-y)}${\displaystyle (x,-y)} because they are both given by the point ${\displaystyle (X:Z)}${\displaystyle (X:Z)}. However, with this representation it is possible to obtain multiples of points, that is, given ${\displaystyle P=(X:Z)}${\displaystyle P=(X:Z)}, to compute ${\displaystyle [n]P=(X_{n}:Z_{n})}${\displaystyle [n]P=(X_{n}:Z_{n})}.

Now, considering the two points ${\displaystyle P_{n}=[n]P=(X_{n}:Z_{n})}${\displaystyle P_{n}=[n]P=(X_{n}:Z_{n})} and ${\displaystyle P_{m}=[m]P=(X_{m}:Z_{m})}${\displaystyle P_{m}=[m]P=(X_{m}:Z_{m})}: their sum is given by the point ${\displaystyle P_{m+n}=P_{m}+P_{n}=(X_{m+n}:Z_{m+n})}${\displaystyle P_{m+n}=P_{m}+P_{n}=(X_{m+n}:Z_{m+n})} whose coordinates are:

${\displaystyle X_{m+n}=Z_{m-n}((X_{m}-Z_{m})(X_{n}+Z_{n})+(X_{m}+Z_{m})(X_{n}-Z_{n}))^{2}}${\displaystyle X_{m+n}=Z_{m-n}((X_{m}-Z_{m})(X_{n}+Z_{n})+(X_{m}+Z_{m})(X_{n}-Z_{n}))^{2}}

${\displaystyle Z_{m+n}=X_{m-n}((X_{m}-Z_{m})(X_{n}+Z_{n})-(X_{m}+Z_{m})(X_{n}-Z_{n}))^{2}}${\displaystyle Z_{m+n}=X_{m-n}((X_{m}-Z_{m})(X_{n}+Z_{n})-(X_{m}+Z_{m})(X_{n}-Z_{n}))^{2}}

If ${\displaystyle m=n}${\displaystyle m=n}, then the operation becomes a "doubling"; the coordinates of ${\displaystyle [2]P_{n}=P_{n}+P_{n}=P_{2n}=(X_{2n}:Z_{2n})}${\displaystyle [2]P_{n}=P_{n}+P_{n}=P_{2n}=(X_{2n}:Z_{2n})} are given by the following equations:

${\displaystyle 4X_{n}Z_{n}=(X_{n}+Z_{n})^{2}-(X_{n}-Z_{n})^{2}}${\displaystyle 4X_{n}Z_{n}=(X_{n}+Z_{n})^{2}-(X_{n}-Z_{n})^{2}}

${\displaystyle X_{2n}=(X_{n}+Z_{n})^{2}(X_{n}-Z_{n})^{2}}${\displaystyle X_{2n}=(X_{n}+Z_{n})^{2}(X_{n}-Z_{n})^{2}}

${\displaystyle Z_{2n}=(4X_{n}Z_{n})((X_{n}-Z_{n})^{2}+((A+2)/4)(4X_{n}Z_{n}))}${\displaystyle Z_{2n}=(4X_{n}Z_{n})((X_{n}-Z_{n})^{2}+((A+2)/4)(4X_{n}Z_{n}))}

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 ${\displaystyle (A+2)/4}${\displaystyle (A+2)/4}, so ${\displaystyle A}${\displaystyle A} can be chosen in order to have a small D.

The following algorithm represents a doubling of a point ${\displaystyle P_{1}=(X_{1}:Z_{1})}${\displaystyle P_{1}=(X_{1}:Z_{1})} on an elliptic curve in the Montgomery form.

It is assumed that ${\displaystyle Z_{1}=1}${\displaystyle Z_{1}=1}. 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.

${\displaystyle XX_{1}=X_{1}^{2},円}${\displaystyle XX_{1}=X_{1}^{2},円}

${\displaystyle X_{2}=(XX_{1}-1)^{2},円}${\displaystyle X_{2}=(XX_{1}-1)^{2},円}

${\displaystyle Z_{2}=4X_{1}(XX_{1}+aX_{1}+1),円}${\displaystyle Z_{2}=4X_{1}(XX_{1}+aX_{1}+1),円}

Let ${\displaystyle P_{1}=(2,{\sqrt {3}})}${\displaystyle P_{1}=(2,{\sqrt {3}})} be a point on the curve ${\displaystyle 2y^{2}=x^{3}-x^{2}+x}${\displaystyle 2y^{2}=x^{3}-x^{2}+x}. In coordinates ${\displaystyle (X_{1}:Z_{1})}${\displaystyle (X_{1}:Z_{1})}, with ${\displaystyle x_{1}=X_{1}/Z_{1}}${\displaystyle x_{1}=X_{1}/Z_{1}}, ${\displaystyle P_{1}=(2:1)}${\displaystyle P_{1}=(2:1)}.

Then:

${\displaystyle XX_{1}=X_{1}^{2}=4,円}${\displaystyle XX_{1}=X_{1}^{2}=4,円}

${\displaystyle X_{2}=(XX_{1}-1)^{2}=9,円}${\displaystyle X_{2}=(XX_{1}-1)^{2}=9,円}

${\displaystyle Z_{2}=4X_{1}(XX_{1}+AX_{1}+1)=24,円}${\displaystyle Z_{2}=4X_{1}(XX_{1}+AX_{1}+1)=24,円}

The result is the point ${\displaystyle P_{2}=(X_{2}:Z_{2})=(9:24)}${\displaystyle P_{2}=(X_{2}:Z_{2})=(9:24)} such that ${\displaystyle P_{2}=2P_{1}}${\displaystyle P_{2}=2P_{1}}.

Given two points ${\displaystyle P_{1}=(x_{1},y_{1})}${\displaystyle P_{1}=(x_{1},y_{1})}, ${\displaystyle P_{2}=(x_{2},y_{2})}${\displaystyle P_{2}=(x_{2},y_{2})} on the Montgomery curve ${\displaystyle M_{A,B}}${\displaystyle M_{A,B}} in affine coordinates, the point ${\displaystyle P_{3}=P_{1}+P_{2}}${\displaystyle P_{3}=P_{1}+P_{2}} represents, geometrically the third point of intersection between ${\displaystyle M_{A,B}}${\displaystyle M_{A,B}} and the line passing through ${\displaystyle P_{1}}${\displaystyle P_{1}} and ${\displaystyle P_{2}}${\displaystyle P_{2}}. It is possible to find the coordinates ${\displaystyle (x_{3},y_{3})}${\displaystyle (x_{3},y_{3})} of ${\displaystyle P_{3}}${\displaystyle P_{3}}, in the following way:

1) consider a generic line ${\displaystyle ~y=lx+m}${\displaystyle ~y=lx+m} in the affine plane and let it pass through ${\displaystyle P_{1}}${\displaystyle P_{1}} and ${\displaystyle P_{2}}${\displaystyle P_{2}} (impose the condition), in this way, one obtains ${\displaystyle l={\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}}${\displaystyle l={\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}} and ${\displaystyle m=y_{1}-\left({\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}\right)x_{1}}${\displaystyle m=y_{1}-\left({\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}\right)x_{1}};

2) intersect the line with the curve ${\displaystyle M_{A,B}}${\displaystyle M_{A,B}}, substituting the ${\displaystyle ~y}${\displaystyle ~y} variable in the curve equation with ${\displaystyle ~y=lx+m}${\displaystyle ~y=lx+m}; the following equation of third degree is obtained:

${\displaystyle x^{3}+(A-Bl^{2})x^{2}+(1-2Blm)x-Bm^{2}=0.}${\displaystyle x^{3}+(A-Bl^{2})x^{2}+(1-2Blm)x-Bm^{2}=0.}

As it has been observed before, this equation has three solutions that correspond to the ${\displaystyle ~x}${\displaystyle ~x} coordinates of ${\displaystyle P_{1}}${\displaystyle P_{1}}, ${\displaystyle P_{2}}${\displaystyle P_{2}} and ${\displaystyle P_{3}}${\displaystyle P_{3}}. In particular this equation can be re-written as:

${\displaystyle (x-x_{1})(x-x_{2})(x-x_{3})=0}${\displaystyle (x-x_{1})(x-x_{2})(x-x_{3})=0}

3) Comparing the coefficients of the two identical equations given above, in particular the coefficients of the terms of second degree, one gets:

${\displaystyle -x_{1}-x_{2}-x_{3}=A-Bl^{2}}${\displaystyle -x_{1}-x_{2}-x_{3}=A-Bl^{2}}.

So, ${\displaystyle x_{3}}${\displaystyle x_{3}} can be written in terms of ${\displaystyle x_{1}}${\displaystyle x_{1}}, ${\displaystyle y_{1}}${\displaystyle y_{1}}, ${\displaystyle x_{2}}${\displaystyle x_{2}}, ${\displaystyle y_{2}}${\displaystyle y_{2}}, as:

${\displaystyle x_{3}=B\left({\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}\right)^{2}-A-x_{1}-x_{2}.}${\displaystyle x_{3}=B\left({\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}\right)^{2}-A-x_{1}-x_{2}.}

4) To find the ${\displaystyle ~y}${\displaystyle ~y} coordinate of the point ${\displaystyle P_{3}}${\displaystyle P_{3}} it is sufficient to substitute the value ${\displaystyle x_{3}}${\displaystyle x_{3}} in the line ${\displaystyle ~y=lx+m}${\displaystyle ~y=lx+m}. Notice that this will not give the point ${\displaystyle P_{3}}${\displaystyle P_{3}} directly. Indeed, with this method one find the coordinates of the point ${\displaystyle ~R}${\displaystyle ~R} such that ${\displaystyle R+P_{1}+P_{2}=P_{\infty }}${\displaystyle R+P_{1}+P_{2}=P_{\infty }}, but if one needs the resulting point of the sum between ${\displaystyle P_{1}}${\displaystyle P_{1}} and ${\displaystyle P_{2}}${\displaystyle P_{2}}, then it is necessary to observe that: ${\displaystyle R+P_{1}+P_{2}=P_{\infty }}${\displaystyle R+P_{1}+P_{2}=P_{\infty }} if and only if ${\displaystyle -R=P_{1}+P_{2}}${\displaystyle -R=P_{1}+P_{2}}. So, given the point ${\displaystyle ~R}${\displaystyle ~R}, it is necessary to find ${\displaystyle ~-R}${\displaystyle ~-R}, but this can be done easily by changing the sign to the ${\displaystyle ~y}${\displaystyle ~y} coordinate of ${\displaystyle ~R}${\displaystyle ~R}. In other words, it will be necessary to change the sign of the ${\displaystyle ~y}${\displaystyle ~y} coordinate obtained by substituting the value ${\displaystyle x_{3}}${\displaystyle x_{3}} in the equation of the line.

Resuming, the coordinates of the point ${\displaystyle P_{3}=(x_{3},y_{3})}${\displaystyle P_{3}=(x_{3},y_{3})}, ${\displaystyle P_{3}=P_{1}+P_{2}}${\displaystyle P_{3}=P_{1}+P_{2}} are:

${\displaystyle x_{3}={\frac {B(y_{2}-y_{1})^{2}}{(x_{2}-x_{1})^{2}}}-A-x_{1}-x_{2}}${\displaystyle x_{3}={\frac {B(y_{2}-y_{1})^{2}}{(x_{2}-x_{1})^{2}}}-A-x_{1}-x_{2}}

${\displaystyle 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}}${\displaystyle 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}}

Given a point ${\displaystyle P_{1}}${\displaystyle P_{1}} on the Montgomery curve ${\displaystyle M_{A,B}}${\displaystyle M_{A,B}}, the point ${\displaystyle [2]P_{1}}${\displaystyle [2]P_{1}} represents geometrically the third point of intersection between the curve and the line tangent to ${\displaystyle P_{1}}${\displaystyle P_{1}}; so, to find the coordinates of the point ${\displaystyle P_{3}=2P_{1}}${\displaystyle P_{3}=2P_{1}} 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 ${\displaystyle P_{1}}${\displaystyle P_{1}}, so, if ${\displaystyle M_{A,B}:f(x,y)=0}${\displaystyle M_{A,B}:f(x,y)=0} with

${\displaystyle f(x,y)=x^{3}+Ax^{2}+x-By^{2},}${\displaystyle f(x,y)=x^{3}+Ax^{2}+x-By^{2},}

then the value of l, which represents the slope of the line, is given by:

${\displaystyle l=-\left.{\frac {\partial f}{\partial x}}\right/{\frac {\partial f}{\partial y}}}${\displaystyle l=-\left.{\frac {\partial f}{\partial x}}\right/{\frac {\partial f}{\partial y}}}

by the implicit function theorem.

So ${\displaystyle l={\frac {3x_{1}^{2}+2Ax_{1}+1}{2By_{1}}}}${\displaystyle l={\frac {3x_{1}^{2}+2Ax_{1}+1}{2By_{1}}}} and the coordinates of the point ${\displaystyle P_{3}}${\displaystyle P_{3}}, ${\displaystyle P_{3}=2P_{1}}${\displaystyle P_{3}=2P_{1}} 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}\\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}}}${\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}\\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}}}

Let ${\displaystyle K}${\displaystyle K} be a field with characteristic different from 2.

Let ${\displaystyle M_{A,B}}${\displaystyle M_{A,B}} be an elliptic curve in the Montgomery form:

${\displaystyle M_{A,B}:Bv^{2}=u^{3}+Au^{2}+u}${\displaystyle M_{A,B}:Bv^{2}=u^{3}+Au^{2}+u}

with ${\displaystyle A\in K\smallsetminus \{-2,2\}}${\displaystyle A\in K\smallsetminus \{-2,2\}}, ${\displaystyle B\in K\smallsetminus \{0\}}${\displaystyle B\in K\smallsetminus \{0\}}

and let ${\displaystyle E_{a,d}}${\displaystyle E_{a,d}} be an elliptic curve in the twisted Edwards form:

${\displaystyle E_{a,d}\ :\ ax^{2}+y^{2}=1+dx^{2}y^{2},,円}${\displaystyle E_{a,d}\ :\ ax^{2}+y^{2}=1+dx^{2}y^{2},,円}

with ${\displaystyle a,d\in K\smallsetminus \{0\},\quad a\neq d.}${\displaystyle a,d\in K\smallsetminus \{0\},\quad a\neq d.}

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 ${\displaystyle K}${\displaystyle K}. In particular, the twisted Edwards curve ${\displaystyle E_{a,d}}${\displaystyle E_{a,d}} is birationally equivalent to the Montgomery curve ${\displaystyle M_{A,B}}${\displaystyle M_{A,B}} where ${\displaystyle A={\frac {2(a+d)}{a-d}}}${\displaystyle A={\frac {2(a+d)}{a-d}}}, and ${\displaystyle B={\frac {4}{a-d}}}${\displaystyle B={\frac {4}{a-d}}}.

The map:

${\displaystyle \psi ,円:,円E_{a,d}\rightarrow M_{A,B}}${\displaystyle \psi ,円:,円E_{a,d}\rightarrow M_{A,B}}

${\displaystyle (x,y)\mapsto (u,v)=\left({\frac {1+y}{1-y}},{\frac {1+y}{(1-y)x}}\right)}${\displaystyle (x,y)\mapsto (u,v)=\left({\frac {1+y}{1-y}},{\frac {1+y}{(1-y)x}}\right)}

is a birational equivalence from ${\displaystyle E_{a,d}}${\displaystyle E_{a,d}} to ${\displaystyle M_{A,B}}${\displaystyle M_{A,B}}, with inverse:

${\displaystyle \psi ^{-1}}${\displaystyle \psi ^{-1}}: ${\displaystyle M_{A,B}\rightarrow E_{a,d}}${\displaystyle M_{A,B}\rightarrow E_{a,d}}

${\displaystyle (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}}}${\displaystyle (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}}}

Notice that this equivalence between the two curves is not valid everywhere: indeed the map ${\displaystyle \psi }${\displaystyle \psi } is not defined at the points ${\displaystyle v=0}${\displaystyle v=0} or ${\displaystyle u+1=0}${\displaystyle u+1=0} of the ${\displaystyle M_{A,B}}${\displaystyle M_{A,B}}.

Any elliptic curve can be written in Weierstrass form. In particular, the elliptic curve in the Montgomery form

${\displaystyle M_{A,B}}${\displaystyle M_{A,B}}: ${\displaystyle By^{2}=x^{3}+Ax^{2}+x,}${\displaystyle By^{2}=x^{3}+Ax^{2}+x,}

can be transformed in the following way: divide each term of the equation for ${\displaystyle M_{A,B}}${\displaystyle M_{A,B}} by ${\displaystyle B^{3}}${\displaystyle B^{3}}, and substitute the variables x and y, with ${\displaystyle u={\frac {x}{B}}}${\displaystyle u={\frac {x}{B}}} and ${\displaystyle v={\frac {y}{B}}}${\displaystyle v={\frac {y}{B}}} respectively, to get the equation

${\displaystyle v^{2}=u^{3}+{\frac {A}{B}}u^{2}+{\frac {1}{B^{2}}}u.}${\displaystyle v^{2}=u^{3}+{\frac {A}{B}}u^{2}+{\frac {1}{B^{2}}}u.}

To obtain a short Weierstrass form from here, it is sufficient to replace u with the variable ${\displaystyle t-{\frac {A}{3B}}}${\displaystyle t-{\frac {A}{3B}}}:

${\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);}${\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);}

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).}${\displaystyle v^{2}=t^{3}+\left({\frac {3-A^{2}}{3B^{2}}}\right)t+\left({\frac {2A^{3}-9A}{27B^{3}}}\right).}

Hence the mapping is given as

${\displaystyle \psi }${\displaystyle \psi }: ${\displaystyle M_{A,B}\rightarrow E_{a,b}}${\displaystyle M_{A,B}\rightarrow E_{a,b}}

${\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}}}}${\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}}}}

In contrast, an elliptic curve over base field ${\displaystyle \mathbb {F} }${\displaystyle \mathbb {F} } in Weierstrass form

${\displaystyle E_{a,b}}${\displaystyle E_{a,b}}: ${\displaystyle v^{2}=t^{3}+at+b}${\displaystyle v^{2}=t^{3}+at+b}

can be converted to Montgomery form if and only if ${\displaystyle E_{a,b}}${\displaystyle E_{a,b}} has order divisible by four and satisfies the following conditions:^[3]

1. ${\displaystyle z^{3}+az+b=0}${\displaystyle z^{3}+az+b=0} has at least one root ${\displaystyle \alpha \in \mathbb {F} }${\displaystyle \alpha \in \mathbb {F} }; and
2. ${\displaystyle 3\alpha ^{2}+a}${\displaystyle 3\alpha ^{2}+a} is a quadratic residue in ${\displaystyle \mathbb {F} }${\displaystyle \mathbb {F} }.

When these conditions are satisfied, then for ${\displaystyle s=({\sqrt {3\alpha ^{2}+a}})^{-1}}${\displaystyle s=({\sqrt {3\alpha ^{2}+a}})^{-1}} we have the mapping

${\displaystyle \psi ^{-1}}${\displaystyle \psi ^{-1}}: ${\displaystyle E_{a,b}\rightarrow M_{A,B}}${\displaystyle E_{a,b}\rightarrow M_{A,B}}

${\displaystyle (t,v)\mapsto (x,y)=\left(s(t-\alpha ),sv\right),A=3\alpha s,B=s}${\displaystyle (t,v)\mapsto (x,y)=\left(s(t-\alpha ),sv\right),A=3\alpha s,B=s}.

• Curve25519
• Table of costs of operations in elliptic curves – information about the running-time required in a specific case

• 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.
• 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)
• Wouter Castryck; Steven Galbraith; Reza Rezaeian Farashahi (2008). "Efficient Arithmetic on Elliptic Curves using a Mixed Edwards-Montgomery Representation" (PDF). {{cite journal}}: Cite journal requires |journal= (help)

• Genus-1 curves over large-characteristic fields

Retrieved from "https://en.wikipedia.org/w/index.php?title=Montgomery_curve&oldid=1275957163"

Categories:

• Elliptic curves
• Elliptic curve cryptography

Hidden categories:

• CS1 maint: multiple names: authors list
• Wikipedia articles that are too technical from February 2025
• All articles that are too technical
• Articles with short description
• Short description is different from Wikidata
• CS1 errors: missing periodical