Concept

Montgomery curve

In mathematics the Montgomery curve is a form of elliptic curve introduced by Peter L. Montgomery in 1987, 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 for certain A, B ∈ K and with B(A2 − 4) ≠ 0. Generally this curve is considered over a finite field K (for example, over a finite field of q elements, K = Fq) 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 consists of finding a third one such that ; "doubling" a point consists of 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 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 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 is given by the point whose coordinates are: If , 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; notice that the constant is , so can be chosen in order to have a small D. The following algorithm represents a doubling of a point on an elliptic curve in the Montgomery form.

About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.