Montgomery curve

Montgomery arithmetic

It is possible to do some "operations" between the points of an elliptic curve: "adding" two points ${\displaystyle P,Q}$ consists of finding a third one ${\displaystyle R}$ such that ${\displaystyle R=P+Q}$; "doubling" a point consists of computing ${\displaystyle [2]P=P+P}$ (For more information about operations see The group law) and below.

A point ${\displaystyle P=(x,y)}$ on the elliptic curve in the Montgomery form ${\displaystyle B{y}^2=x^3+A{x}^2+x}$ can be represented in Montgomery coordinates ${\displaystyle P=(X:Z)}$, where ${\displaystyle P=(X:Z)}$ are projective coordinates and ${\displaystyle x=X/Z}$ for ${\displaystyle Z\ne 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)}$ and ${\displaystyle (x,-y)}$ because they are both given by the point ${\displaystyle (X:Z)}$. However, with this representation it is possible to obtain multiples of points, that is, given ${\displaystyle P=(X:Z)}$, to compute ${\displaystyle [n]P=(X_n:Z_n)}$.

Now, considering the two points ${\displaystyle P_n=[n]P=(X_n:Z_n)}$ and ${\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})}$ 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 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}$, then the operation becomes a "doubling"; the coordinates of ${\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 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))}$

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

Algorithm and example

The following algorithm represents a doubling of a point ${\displaystyle P_1=(X_1:Z_1)}$ on an elliptic curve in the Montgomery form.

It is assumed that ${\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 X{X}_1=X_1^2}$

${\displaystyle X_2=(X{X}_1-1{)}^2}$

${\displaystyle Z_2=4X_1(X{X}_1+a{X}_1+1)}$

Example

Let ${\displaystyle P_1=(2,\sqrt{3})}$ be a point on the curve ${\displaystyle 2y^2=x^3-x^2+x}$. In coordinates ${\displaystyle (X_1:Z_1)}$, with ${\displaystyle x_1=X_1/Z_1}$, ${\displaystyle P_1=(2:1)}$.

Then:

${\displaystyle X{X}_1=X_1^2=4}$

${\displaystyle X_2=(X{X}_1-1{)}^2=9}$

${\displaystyle Z_2=4X_1(X{X}_1+A{X}_1+1)=24}$

The result is the point ${\displaystyle P_2=(X_2:Z_2)=(9:24)}$ such that ${\displaystyle P_2=2P_1}$.

Addition

Given two points ${\displaystyle P_1=(x_1,y_1)}$, ${\displaystyle P_2=(x_2,y_2)}$ on the Montgomery curve ${\displaystyle M_{A,B}}$ in affine coordinates, the point ${\displaystyle P_3=P_1+P_2}$ represents, geometrically the third point of intersection between ${\displaystyle M_{A,B}}$ and the line passing through ${\displaystyle P_1}$ and ${\displaystyle P_2}$. It is possible to find the coordinates ${\displaystyle (x_3,y_3)}$ of ${\displaystyle P_3}$, in the following way:

1) consider a generic line ${\displaystyle y=lx+m}$ in the affine plane and let it pass through ${\displaystyle P_1}$ and ${\displaystyle P_2}$ (impose the condition), in this way, one obtains ${\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}$;

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

${\displaystyle x^3+(A-B{l}^2)x^2+(1-2Blm)x-B{m}^2=0.}$

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

${\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-B{l}^2}$.

So, ${\displaystyle x_3}$ can be written in terms of ${\displaystyle x_1}$, ${\displaystyle y_1}$, ${\displaystyle x_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.}$

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

Doubling

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

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

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

${\displaystyle l=-\frac{\mathrm{\partial }f}{\mathrm{\partial }x}/\frac{\mathrm{\partial }f}{\mathrm{\partial }y}}$

by the implicit function theorem.

So ${\displaystyle l=\frac{3x_1^2+2A{x}_1+1}{2B{y}_1}}$ and the coordinates of the point ${\displaystyle P_3}$, ${\displaystyle P_3=2P_1}$ are:

${\displaystyle \begin{array}{cc}{x}_3& =B{l}^2-A-x_1-x_1=\frac{B(3x_1^2+2A{x}_1+1{)}^2}{(2B{y}_1{)}^2}-A-x_1-x_1\\ y_3& =(2x_1+x_1+A)l-B{l}^3-y_1\\ & =\frac{(2x_1+x_1+A)(3{x_1}^2+2A{x}_1+1)}{2B{y}_1}-\frac{B(3{x_1}^2+2A{x}_1+1{)}^3}{(2B{y}_1{)}^3}-y_1.\end{array}}$

Equivalence with twisted Edwards curves

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

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

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

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

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

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

with ${\displaystyle a,d\in K\setminus \{0\},a\ne d.}$

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

The map:

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

${\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}}$ to ${\displaystyle M_{A,B}}$, with inverse:

${\displaystyle {\psi }^{-1}}$: ${\displaystyle M_{A,B}\to 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}}$

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

Equivalence with Weierstrass curves

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

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

can be transformed in the following way: divide each term of the equation for ${\displaystyle M_{A,B}}$ by ${\displaystyle B^3}$, and substitute the variables x and y, with ${\displaystyle u=\frac{x}{B}}$ and ${\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.}$

To obtain a short Weierstrass form from here, it is sufficient to replace u with the variable ${\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);}$

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).}$

Hence the mapping is given as

${\displaystyle \psi }$: ${\displaystyle M_{A,B}\to 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}}$

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

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

can be converted to Montgomery form if and only if ${\displaystyle E_{a,b}}$ satisfies the following conditions:

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

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

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

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