24.222.79.230: _\mathrm{w}

2012-10-11T15:02:45Z

_\mathrm{w}

New page

In [[mathematics]] the '''Montgomery curve''' is a form of [[elliptic curve]], different from the usual [[elliptic curve|Weierstrass form]], introduced by [[Peter Montgomery (mathematician)|Peter L. Montgomery]] in 1987.<ref>{{cite journal
| author = [[Peter Montgomery (mathematician)|Peter L. Montgomery]]
| year = 1987
| title = Speeding the Pollard and Elliptic Curve Methods of Factorization
| journal = Mathematics of Computation |volume=48 |issue=177 |pages=243–264
| jstor = 2007888
}}</ref> It is used for certain computations, and in particular in different [[Elliptic curve cryptography|cryptography]] applications.

==Definition==
[[File:Montgomery curve1.svg|300px|right|thumb|A Montgomery curve of equation <math>3y^2=x^3+7x^2+x</math>]]
A '''Montgomery curve''' over a [[field (mathematics)|field]] <math>K</math> is defined by the [[equation]]:

<math>M_{A,B}</math>: <math>By^2 = x^3 + Ax^2 + x</math>

for certain <math>A,B \in K</math> and with <math>B(A^2-4)\neq 0</math>.

Generally this [[curve]] is considered over a [[finite field]] <math>K</math> (for example over a finite field of q [[element (mathematics)|element]]s, <math>K=\mathbb{F}_q</math>) with [[characteristic (algebra)|characteristic]] different from 2 and with <math>A\in K\backslash\{-2,2\}</math>, <math>B \in K\backslash\{0\} </math>; but they are also considered over the [[rational number|rationals]] with the same restrictions for A and B.

==Montgomery arithmetic==
It is possible to do some "operations" between the [[point (geometry)|points]] of an elliptic curve: "adding" two points <math>P, Q</math> consists on finding a third one <math>R</math> such that <math>R=P+Q</math>; "doubling" a point consists on computing <math>[2]P=P+P</math> (For more information about operations see [[Elliptic curve#The group law|The group law]]) and below.

A point <math>P=(x,y)</math> on the elliptic curve in the Montgomery form <math>By^2 = x^3 + Ax^2 + x</math> can be represented in Montgomery coordinates <math>P=(X:Z)</math>, where <math>P=(X:Z)</math> are [[projective space|projective coordinates]] and <math>x=X/Z</math> for <math>Z\ne 0</math>.

Notice that this kind of representation for a point loses information: indeed, in this case, there is no distinction between the [[affine space|affine points]] <math>(x,y)</math> and <math>(x,-y)</math> because they are both given by the point <math>(X:Z)</math>. However, with this representation it is possible to obtain multiples of points, that is, given <math>P=(X:Z)</math>, to compute <math>[n]P=(X_n:Z_n)</math>.

Now, considering the two points <math>P_n=[n]P=(X_n:Z_n)</math> and <math>P_m=[m]P(X_m:Z_m)</math>: their [[summation|sum]] is given by the point <math>P_{m+n}=P_m+P_n = (X_{m+n}:Z_{m+n})</math> whose [[coordinate system|coordinates]] are:

<math>
X_{m+n} = Z_{m-n}((X_m-Z_m)(X_n+Z_n)+(X_m+Z_m)(X_n-Z_n))^2
</math>

<math>
Z_{m+n} = X_{m-n}((X_m-Z_m)(X_n+Z_n)-(X_m+Z_m)(X_n-Z_n))^2
</math>

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

<math>
4X_nZ_n = (X_n+Z_n)^2 - (X_n-Z_n)^2
</math>

<math>
X_{2n} = (X_n+Z_n)^2(X_n-Z_n)^2
</math>

<math>
Z_{2n} = (4X_nZ_n)((X_n-Z_n)^2+((A+2)/4)(4X_nZ_n))
</math>

The first operation considered above ([[elliptic curve#The group law|addition]]) has a time-cost of 3'''M'''+2'''S''', where '''M''' denotes the multiplication between two general [[element (mathematics)|elements]] of the field on which the elliptic curve is defined, while '''S''' denotes [[square (algebra)|squaring]] of a general element of the field.

The second operation (doubling) has a time-cost of 2'''M'''+2'''S'''+1'''D''', where '''D''' denotes the multiplication of a general element by a [[constant (mathematics)|constant]]; notice that the constant is <math>(A+2)/4</math>, so <math>A</math> can be chosen in order to have a small '''D'''.

==Algorithm and example==
The following algorithm represents a doubling of a point <math>P_1=(X_1:Z_1)</math> on an elliptic curve in the Montgomery form.

It is assumed that <math>Z_1=1</math>. 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.

: <math>XX_1 = X_1^2 \, </math>

: <math>X_3 = (XX_1-1)^2 \, </math>

: <math>Z_3 = 4X_1(XX_1+aX_1+1) \, </math>

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

Then:

: <math>XX_1 = X_1^2 = 4 \, </math>

: <math>X_3 = (XX_1-1)^2 = 9 \, </math>

: <math>Z_3 = 4X_1(XX_1+aX_1+1) = 24 \, </math>

The result is the point <math>P_3=(X_3:Z_3)=(9:24)</math> such that <math>P_3=2P_1</math>.

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

1) consider a generic line <math>~y=lx+m</math> in the affine plane and let it pass through <math>P_1</math> and <math>P_2</math> (impose the condition), in this way, one obtains <math>l=\frac{y_2-y_1}{x_2-x_1}</math> and <math>m=y_1-(\frac{y_2-y_1}{x_2-x_1})x_1</math>;

2) intersect the line with the curve <math>M_{A,B}</math>, substituting the <math>~y</math> variable in the curve equation with <math>~y=lx+m</math>; the following [[equation| equation of third degree]] is obtained:

<math>x^3+(A-Bl^2)x^2+(1-2Blm)x-Bm^2=0</math>.

As it has been observed before, this equation has three solutions that correspond to the <math>~x</math> coordinates of <math>P_1</math>, <math>P_2</math> and <math>P_3</math>. In particular this equation can be re-written as:

<math>(x-x_1)(x-x_2)(x-x_3)=0</math>

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

<math>-x_1-x_2-x_3=A-Bl^2</math>.

So, <math>x_3</math> can be written in terms of <math>x_1</math>, <math>y_1</math>, <math>x_2</math>, <math>y_2</math>, as:

<math>x_3 = B(\frac{y_2-y_1}{x_2-x_1})^2-A-x_1-x_2</math>.

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

Resuming, the coordinates of the point <math>P_3=(x_3,y_3)</math>, <math>P_3=P_1+P_2</math> are:

<math>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}</math>

<math>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</math>

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

<math>f(x,y)=x^3+Ax^2+x-By^2</math>,

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

<math> l=-\frac{\frac{\partial f}{\partial x}}{\frac{\partial f}{\partial y }}</math>

by the [[implicit function theorem]].

So <math>l = \frac{3x_1^2 + 2Ax_1 + 1}{2By_1}</math> and the coordinates of the point <math>P_3</math>, <math>P_3=2P_1</math> are:

<math>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)}</math>

<math>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</math>.

==Equivalence with twisted Edwards curves==
Let <math>K</math> be a field with characteristic different from 2.

Let <math>M_{A,B}</math> be an elliptic curve in the Montgomery form:

<math>M_{A,B}</math>: <math>Bv^2 = u^3 + Au^2 + u</math>

with <math>A\in K\backslash\{-2,2\}</math>, <math>B \in K\backslash\{0\}</math>

and let <math>E_{a,d}</math> be an elliptic curve in the twisted Edwards form:

: <math>E_{a,d}\ :\ ax^2 + y^2 = 1 + dx^2y^2, \,</math>

with <math>a,d\in K\backslash\{0\}</math>, <math>a\neq d</math>.

The following theorem shows the [[Birational geometry|birational equivalence]] between Montgomery curves and twisted Edwards curves:<ref>{{cite book
| author = [[Daniel J. Bernstein]], Peter Birkner, Marc Joye, Tanja Lange and Christiane Peters
| year = 2008
| title = Twisted Edwards Curves
| publisher = Springer-Verlag Berlin Heidelberg
| url = http://www.springerlink.com/content/m37m171510425501/fulltext.pdf
| isbn = 978-3-540-68159-5
}}</ref>

'''Theorem''' (i) Every twisted Edwards curve is birationally equivalent to a Montgomery curve over <math>K</math>.
In particular, the twisted Edwards curve <math>E_{a,d}</math> is birationally equivalent to the Montgomery curve <math>M_{A,B}</math> where <math>A = \frac{2(a+d)}{a-d}</math>, and <math>B = \frac{4}{a-d}</math>.

The [[map (mathematics)|map]]:

: <math>\psi\,:\,E_{a,d} \rightarrow M_{A,B}</math>

: <math>
(x,y) \mapsto (u,v) = \left(\frac{1+y}{1-y},\frac{1+y}{(1-y)x}\right)
</math>

is a birational equivalence from <math>E_{a,d}</math> to <math>M_{A,B}</math>, with inverse:

: <math>\psi^{-1}</math>: <math>M_{A,B} \rightarrow E_{a,d}</math>

: <math>
(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}
</math>

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

==Equivalence with Weierstrass curves==
Any elliptic curve can be written in Weierstrass form.

So, the elliptic curve in the Montogmery form

<math>M_{A,B}</math>: <math>By^2 = x^3 + Ax^2 + x</math>,

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

<math>v^2 = u^3 + \frac{A}{B}u^2 + \frac{1}{B^2}u</math>.

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

<math>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)</math>;

finally, this gives the equation:

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

==See also==

* [[Curve25519]]
* [[Table of costs of operations in elliptic curves]], information about the running-time required in a specific case

==Notes==
{{reflist}}

==References==
* {{cite journal
| author = [[Peter Montgomery (mathematician)|Peter L. Montgomery]]
| year = 1987
| title = Speeding the Pollard and Elliptic Curve Methods of Factorization
| journal = Mathematics of Computation |volume=48 |issue=177 |pages=243–264
| jstor = 2007888
}}
* {{cite book
| author = [[Daniel J. Bernstein]], Peter Birkner, Marc Joye, Tanja Lange and Christiane Peters
| year = 2008
| title = Twisted Edwards Curves
| publisher = Springer-Verlag Berlin Heidelberg
| url = http://www.springerlink.com/content/m37m171510425501/fulltext.pdf
| isbn = 978-3-540-68159-5
}}
* {{cite paper
| author = Wouter Castryck, Steven Galbraith, Reza Rezaeian Farashahi |year=2008
| title = Efficient Arithmetic on Elliptic Curves using a Mixed Edwards-Montgomery Representation
| url = http://wis.kuleuven.be/algebra/castryck/xcoordinate.pdf
}}

==External links==
*[http://hyperelliptic.org/EFD/g1p/index.html Genus-1 curves over large-characteristic fields]

[[Category:Elliptic curves]]
[[Category:Elliptic curve cryptography]]

Searle's bar method - Revision history

24.222.79.230: _\mathrm{w}