Montgomery curve - AbsoluteAstronomy.com

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

the Montgomery curve is a form of elliptic curve

Elliptic curve

In mathematics, an elliptic curve is a smooth, projective algebraic curve of genus one, on which there is a specified point O. An elliptic curve is in fact an abelian variety — that is, it has a multiplication defined algebraically with respect to which it is a group — and O serves as the identity...

, different from the usual representation (Weierstrass form

Elliptic curve

).
It has been introduced by Peter L.Montgomery

Peter Montgomery

Peter Lawrence Montgomery is an American mathematician who has published widely in the more mathematical end of the field of cryptography. He is currently a researcher in the cryptography group at Microsoft Research....

in, and it has been used since 1987 for certain computations, and in particular in different cryptography

Cryptography

Cryptography is the practice and study of techniques for secure communication in the presence of third parties...

applications.

Definition

A Montgomery curve over a field

Field (mathematics)

In abstract algebra, a field is a commutative ring whose nonzero elements form a group under multiplication. As such it is an algebraic structure with notions of addition, subtraction, multiplication, and division, satisfying certain axioms...

is defined by the equation

Equation

An equation is a mathematical statement that asserts the equality of two expressions. In modern notation, this is written by placing the expressions on either side of an equals sign , for examplex + 3 = 5\,asserts that x+3 is equal to 5...

for certain

and with

.

Generally this curve

Curve

In mathematics, a curve is, generally speaking, an object similar to a line but which is not required to be straight...

is considered over a finite field

Finite field

In abstract algebra, a finite field or Galois field is a field that contains a finite number of elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory...

(for example over a finite field of q elements,

) with characteristic

Characteristic (algebra)

In mathematics, the characteristic of a ring R, often denoted char, is defined to be the smallest number of times one must use the ring's multiplicative identity element in a sum to get the additive identity element ; the ring is said to have characteristic zero if this repeated sum never reaches...

different from 2 and with

; but they are also considered over the rationals

Rational number

In mathematics, a rational number is any number that can be expressed as the quotient or fraction a/b of two integers, with the denominator b not equal to zero. Since b may be equal to 1, every integer is a rational number...

with the same restrictions for A and B.

Montgomery arithmetic

It is possible to do some "operations" between the points

Point (geometry)

In geometry, topology and related branches of mathematics a spatial point is a primitive notion upon which other concepts may be defined. In geometry, points are zero-dimensional; i.e., they do not have volume, area, length, or any other higher-dimensional analogue. In branches of mathematics...

of an elliptic curve: "adding" two points

consists on finding a third one

such that

; "doubling" a point consists on 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

Projective space

In mathematics a projective space is a set of elements similar to the set P of lines through the origin of a vector space V. The cases when V=R2 or V=R3 are the projective line and the projective plane, respectively....

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

Affine space

In mathematics, an affine space is a geometric structure that generalizes the affine properties of Euclidean space. In an affine space, one can subtract points to get vectors, or add a vector to a point to get another point, but one cannot add points. In particular, there is no distinguished point...

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

Summation

Summation is the operation of adding a sequence of numbers; the result is their sum or total. If numbers are added sequentially from left to right, any intermediate result is a partial sum, prefix sum, or running total of the summation. The numbers to be summed may be integers, rational numbers,...

is given by the point

whose coordinates

Coordinate system

In geometry, a coordinate system is a system which uses one or more numbers, or coordinates, to uniquely determine the position of a point or other geometric element. The order of the coordinates is significant and they are sometimes identified by their position in an ordered tuple and sometimes by...

are:

, then the operation becomes a "doubling"; the coordinates of

are given by the following equations:

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

Constant (mathematics)

In mathematics, a constant is a non-varying value, i.e. completely fixed or fixed in the context of use. The term usually occurs in opposition to variable In mathematics, a constant is a non-varying value, i.e. completely fixed or fixed in the context of use. The term usually occurs in opposition...

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

Example

Let

be a point on the curve

.
In coordinates

, with

.

Then:

The result is the point

, such that

Addition

Given two points

on the Montgomery curve

in affine coordinates, the point

represents, geometrically

Geometry

Geometry arose as the field of knowledge dealing with spatial relationships. Geometry was one of the two fields of pre-modern mathematics, the other being the study of numbers ....

the third point of intersection between

and the line passing through

and

. It is possible to find the coordinates

, in the following way:

1) consider a generic line y=lx+m 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 y variable in the curve equation with y=lx+m; the following equation of third degree

Equation

is obtained:

.

As it has been observed before, this equation has three solutions that correspond to the x coordinates of

and

. In particular this equation can be re-written as:

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:

.

4) To find the y coordinate of the point

it is sufficient to substitute the value

in the line y=lx+m. Notice that this will not give the point

directly. Indeed, with this method one find the coordinates of the point R 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 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

in the equation of the line.

Resuming, the coordinates of the point

are:

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

,

then the value of l, which represents the slope

Slope

In mathematics, the slope or gradient of a line describes its steepness, incline, or grade. A higher slope value indicates a steeper incline....

of the line, is given by:

by the implicit function theorem

Implicit function theorem

In multivariable calculus, the implicit function theorem is a tool which allows relations to be converted to functions. It does this by representing the relation as the graph of a function. There may not be a single function whose graph is the entire relation, but there may be such a function on...

.

So

and the coordinates of the point

are:

Equivalence with twisted Edwards curves

Let

be a field with characteristic different from 2.

Let

be an elliptic curve in the Montgomery form:

with

and let

be an elliptic curve in the twisted Edwards form:

with

.

The following theorem proved in, shows the birational equivalence

Birational geometry

In mathematics, birational geometry is a part of the subject of algebraic geometry, that deals with the geometry of an algebraic variety that is dependent only on its function field. In the case of dimension two, the birational geometry of algebraic surfaces was largely worked out by the Italian...

between Montgomery curves and an twisted Edwards curves:

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

Map (mathematics)

In most of mathematics and in some related technical fields, the term mapping, usually shortened to map, is either a synonym for function, or denotes a particular kind of function which is important in that branch, or denotes something conceptually similar to a function.In graph theory, a map is a...