Montgomery curve

In mathematics the Montgomery curve is a form of elliptic curve, different from the usual representation (Weierstrass form). It has been introduced by Peter L.Montgomery in,^[1] and it has been used since 1987 for certain computations, and in particular in different cryptography applications.

Definition

A Montgomery curve of equation 3y² = x³ + 7x² + x

A Montgomery curve over a field K is defined by the equation:

M_A,B: By² = x³ + Ax² + x

for certain $A,B \in K$ and with $B(A^2-4)\neq 0$.

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

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

Now, considering the two points P_n = [n]P = (X_n:Z_n) and P_m = [m]P(X_m:Z_m): their sum is given by the point P_{m + n} = P_m + P_n = (X_{m + n}:Z_{m + n}) 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))²

Z_{m + n} = X_{m − n}((X_m − Z_m)(X_n + Z_n) − (X_m + Z_m)(X_n − Z_n))²

If m = n, then the operation becomes a "doubling"; the coordinates of [2]P_n = P_n + P_n = P_2n = (X_2n:Z_2n) are given by the following equations:

4X_nZ_n = (X_n + Z_n)² − (X_n − Z_n)²

X_2n = (X_n + Z_n)²(X_n − Z_n)²

Z_2n = (4X_nZ_n)((X_n − Z_n)² + ((A + 2) / 4)(4X_nZ_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 (A + 2) / 4, so A can be chosen in order to have a small D.

Algorithm and example

The following algorithm represents a doubling of a point P₁ = (X₁:Z₁) on an elliptic curve in the Montgomery form.

It is assumed that Z₁ = 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.

$XX_1 = X_1^2 \,$

$X_3 = (XX_1-1)^2 \,$

$Z_3 = 4X_1(XX_1+aX_1+1) \,$

Example

Let $P_1=(2,\sqrt{3})$ be a point on the curve 2y² = x³ − x² + x. In coordinates (X₁:Z₁), with x₁ = X₁ / Z₁, P₁ = (2:1).

Then:

$XX_1 = X_1^2 = 4 \,$

$X_3 = (XX_1-1)^2 = 9 \,$

$Z_3 = 4X_1(XX_1+aX_1+1) = 24 \,$

The result is the point P₃ = (X₃:Z₃) = (9:24), such that P₃ = 2P₁.

Addition

Given two points P₁ = (x₁,y₁), P₂ = (x₂,y₂) on the Montgomery curve M_A,B in affine coordinates, the point P₃ = P₁ + P₂ represents, geometrically the third point of intersection between M_A,B and the line passing through P₁ and P₂. It is possible to find the coordinates (x₃,y₃) of P₃, in the following way:

1) consider a generic line y=lx+m in the affine plane and let it pass through P₁ and P₂ (impose the condition), in this way, one obtains $l=\frac{y_2-y_1}{x_2-x_1}$ and $m=y_1-(\frac{y_2-y_1}{x_2-x_1})x_1$;

2) intersect the line with the curve M_A,B, substituting the y variable in the curve equation with y=lx+m; the following equation of third degree is obtained:

x³ + (A − Bl²)x² + (1 − 2Blm)x − m² = 0.

As it has been observed before, this equation has three solutions that correspond to the x coordinates of P₁, P₂ and P₃. In particular this equation can be re-written as:

(x − x₁)(x − x₂)(x − x₃) = 0

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

− x₁ − x₂ − x₃ = A − Bl².

So, x₃ can be written in terms of x₁, y₁, x₂, y₂, as:

$x_3 = B(\frac{y_2-y_1}{x_2-x_1})^2-A-x_1-x_2$.

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

Resuming, the coordinates of the point P₃ = (x₃,y₃), P₃ = P₁ + P₂ are:

$x_3 = \frac{B(y_2-y_1)^2}{(x_2-x_1)^2}-A-x_1-x_2$

$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 P₁ on the Montgomery curve M_A,B, the point [2]P₁ represents geometrically the third point of intersection between the curve and the line tangent to P₁; so, to find the coordinates of the point P₃ = 2P₁ 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 P₁, so, if M_A,B:f(x,y) = 0 with

f(x,y) = x³ + Ax² + x − By²,

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

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

by the implicit function theorem.

So $l = \frac{3x_1^2 + 2Ax_1 + 1}{2By_1}$ and the coordinates of the point P₃, P₃ = 2P₁ are:

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

Equivalence with twisted Edwards curves

Let K be a field with characteristic different from 2.

Let M_A,B be an elliptic curve in the Montgomery form:

M_A,B: Bv² = u³ + Au² + u

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

and let E_a,d be an elliptic curve in the twisted Edwards form:

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

with $a,d\in K\backslash\{0\}$, $a\neq d$.

The following theorem proved in,^[2] shows the birational equivalence between Montgomery curves and an twisted Edwards curves:

Theorem (i) Every twisted Edwards curve is birationally equivalent to a Montgomery curve over K. In particular, the twisted Edwards curve E_a,d is birationally equivalent to the Montgomery curve M_A,B where $A = \frac{2(a+d)}{a-d}$, and $B = \frac{4}{a-d}$.

The map:

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

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

is a birational equivalence from E_a,d to M_A,B, with inverse:

ψ ^{− 1}: $M_{A,B} \rightarrow E_{a,d}$

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

Notice that this equivalence between the two curves is not valid everywhere: indeed the map ψ is not defined at the points v = 0 or u + 1 = 0 of the M_A,B.

Equivalence with Weierstrass curves

Any elliptic curve can be written in Weierstrass form.

So, the elliptic curve in the Montogmery form

M_A,B: By² = x³ + Ax² + x,

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

$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 $t-\frac{A}{3B}$:

$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:

$v^2 = t^3 + \left(\frac{3-A^2}{3B^2}\right)t + \left(\frac{2A^3-9A}{27B^3}\right)$.

See also

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

Notes

1. ^ Peter L. Montgomery, Speeding the Pollard and Elliptic Curve Methods of Factorization, January 1987
2. ^ Daniel J. Bernstein, Peter Birkner, Marc Joye, Tanja Lange and Christiane Peters, Twisted Edwards Curves

References

• Peter L. Montgomery (1987). Speeding the Pollard and Elliptic Curve Methods of Factorization. American Mathematical Society. JSTOR 2007888. 
• Daniel J. Bernstein, Peter Birkner, Marc Joye, Tanja Lange and Christiane Peters (2008). Twisted Edwards Curves. Springer-Verlag Berlin Heidelberg. ISBN 978-3-540-68159-5. http://www.springerlink.com.proxy.library.uu.nl/content/m37m171510425501/fulltext.pdf. 
• Wouter Castryck, Steven Galbraith, Reza Rezaeian Farashahi. Efficient Arithmetic on Elliptic Curves using a Mixed Edwards-Montgomery Representation. http://wis.kuleuven.be/algebra/castryck/xcoordinate.pdf. 

External links

• Genus-1 curves over large-characteristic fields