Elliptic Curve: Montgomery Curve

Montgomery Curve

Table of Content:

• Definition
• Montgomery Arithmetic
• Addition
• Doubling
• Examples
• Conclusion
  
  

Definition

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

Generally this type of curve is considered over a finite field K. Eg: Over a field of q elements, . 

Next blog am going to touch on Finite Field in Montgomery Curve.

Montgomery Arithmetic

There are two type of Arithmetic in this type of Curve:

• Adding: It consist of adding 2 points to find the third point. 
  
  
  
  
  
• Doubling: It consist of 1 point to find the other.
  
  

Addition

Assume:

From P1 and P2, derive Point P3 from the Montgomery Curve

1. Lets Consider a straight line, L: 

So:

Using P1 and P2, we can find the equation of the line, L.

2. To find the third point, we can take both the equation and find the third intersection point. 

The result is an equation with third degree. Since it is a third degree equation, it should have 3 solution. It can be rewritten as:

Lets expand the brackets:

Lets analyze:

Lets look at the second degree (x^2). it show that:

We get an equation which we have only 1 unknown(x3).  SO:

We get the value of x3. We can then replace this value in either the Curve or the straight line to get the y3 (y-coordinate of P3).

Doubling

In doubling, the line only touches 2 points, P1 and P3. Given point P1, [2]P1 represent geometrically the third point of intersection between the line and curve. So to find the coordinate of P3, we use the equation P3 = [2]P1. We can use the same approach as addition with the exception that the line touches at 2 points only. So to get the gradient at point P1, we must differentiate the curve.

Assuming:

We need to get the differentiation of the Montgomery Curve.

Now we replace the x and y value by the coordinate of P1 to get the gradient of the line.

Using the second degree derived equation:

Thus getting the third point. We basically assumed that the second point P2 is P1 (P2 = P1).

After getting the x-coordinate of P3, we can find the coordinate by replacing it on the Montgomery Curve.

Examples

Addition

Lets find the equation of line:

Using the derived formula:

Taking only the second degree:

Here is the proof:

Doubling

Lets Differentiate the curve to get the gradient at P1.

Using the second degree derived equation:

Proof:

Conclusion

Montgomery is an elliptic curve which is being used in the field of cryptography. The simple arithmetic produces the keys need for communication. 

One thing that I did not touched on Montgomery is the Field of the curve. As the definition above states that a Montgomery curve has a field K. This will be on my next blog.