Edwards curve

<h2 id="definition">Definition</h2>
The equation of an Edwards curve over a <a href="/facts/Field_(mathematics)/xAjAS4ko">field</a> K which does not
have <a href="/facts/Characteristic_(algebra)/D2VzcQaG">characteristic 2</a> is:

x
          
            2
          
        
        +
        
          y
          
            2
          
        
        =
        1
        +
        d
         
        
          x
          
            2
          
        
        
          y
          
            2
          
        
        
      
    
    {\displaystyle x^{2}+y^{2}=1+d\ x^{2}y^{2}\,}

for some <a href="/facts/Scalar_field/8MtPTGob">scalar</a> 
 
 
 
 d
 ∈
 K
 ∖
 {
 0
 ,
 1
 }
 
 
 {\displaystyle d\in K\setminus \{0,1\}}
 
.
Also the following form with parameters c and d is called an Edwards curve:

x
          
            2
          
        
        +
        
          y
          
            2
          
        
        =
        
          c
          
            2
          
        
        (
        1
        +
        d
         
        
          x
          
            2
          
        
        
          y
          
            2
          
        
        )
        
      
    
    {\displaystyle x^{2}+y^{2}=c^{2}(1+d\ x^{2}y^{2})\,}

where c, d ∈ K with cd(1 − c4·d) ≠ 0.
Every Edwards curve is <a href="/facts/Birationally_equivalent/hsWqRhJ1">birationally equivalent</a> to an elliptic curve in <a href="/facts/Montgomery_curve/YQWgbzVp">Montgomery form</a>, and thus admits an algebraic group law once one chooses a point to serve as a neutral element. If K is finite, then a sizeable fraction of all elliptic curves over K can be written as Edwards curves.
Often elliptic curves in Edwards form are defined having c=1, without loss of generality. In the following sections, it is assumed that c=1.

<h2 id="the-group-law">The group law</h2>
(See also <a href="/facts/Elliptic_curve/60jvaHSA">Weierstrass curve group law</a>)
Every Edwards curve 
 
 
 
 
 x
 
 2
 
 
 +
 
 y
 
 2
 
 
 =
 1
 +
 d
 
 x
 
 2
 
 
 
 y
 
 2
 
 
 
 
 {\displaystyle x^{2}+y^{2}=1+dx^{2}y^{2}}
 
 over field K with characteristic not equal to 2 with 
 
 
 
 d
 ≠
 1
 
 
 {\displaystyle d\neq 1}
 
 is birationally equivalent to an elliptic curve over the same field: 
 
 
 
 (
 1
 
 /
 
 e
 )
 
 v
 
 2
 
 
 =
 
 u
 
 3
 
 
 +
 (
 4
 
 /
 
 e
 −
 2
 )
 
 u
 
 2
 
 
 +
 u
 
 
 {\displaystyle (1/e)v^{2}=u^{3}+(4/e-2)u^{2}+u}
 
, where 
 
 
 
 e
 =
 1
 −
 d
 ,
 u
 =
 
 
 
 1
 +
 y
 
 
 1
 −
 y
 
 
 
 ,
 v
 =
 
 
 
 2
 (
 1
 +
 y
 )
 
 
 x
 (
 1
 −
 y
 )
 
 
 
 
 
 {\displaystyle e=1-d,u={\frac {1+y}{1-y}},v={\frac {2(1+y)}{x(1-y)}}}
 
 and the point 
 
 
 
 P
 =
 (
 0
 ,
 1
 )
 
 
 {\displaystyle P=(0,1)}
 
 is mapped to the infinity O. This birational mapping induces a group on any Edwards curve.

<h3>Edwards addition law</h3>
On any elliptic curve the sum of two points is given by a rational expression of the coordinates of the points, although in general one may need to use several formulas to cover all possible pairs. For the Edwards curve, taking the <a href="/facts/Identity_element/9nss3xHY">neutral element</a> to be the point (0, 1), the sum of the points 
 
 
 
 (
 
 x
 
 1
 
 
 ,
 
 y
 
 1
 
 
 )
 
 
 {\displaystyle (x_{1},y_{1})}
 
 and 
 
 
 
 (
 
 x
 
 2
 
 
 ,
 
 y
 
 2
 
 
 )
 
 
 {\displaystyle (x_{2},y_{2})}
 
 is given by the formula

(
        
          x
          
            1
          
        
        ,
        
          y
          
            1
          
        
        )
        +
        (
        
          x
          
            2
          
        
        ,
        
          y
          
            2
          
        
        )
        =
        
          (
          
            
              
                
                  
                    x
                    
                      1
                    
                  
                  
                    y
                    
                      2
                    
                  
                  +
                  
                    x
                    
                      2
                    
                  
                  
                    y
                    
                      1
                    
                  
                
                
                  1
                  +
                  d
                  
                    x
                    
                      1
                    
                  
                  
                    x
                    
                      2
                    
                  
                  
                    y
                    
                      1
                    
                  
                  
                    y
                    
                      2
                    
                  
                
              
            
            ,
            
              
                
                  
                    y
                    
                      1
                    
                  
                  
                    y
                    
                      2
                    
                  
                  −
                  
                    x
                    
                      1
                    
                  
                  
                    x
                    
                      2
                    
                  
                
                
                  1
                  −
                  d
                  
                    x
                    
                      1
                    
                  
                  
                    x
                    
                      2
                    
                  
                  
                    y
                    
                      1
                    
                  
                  
                    y
                    
                      2
                    
                  
                
              
            
          
          )
        
        
      
    
    {\displaystyle (x_{1},y_{1})+(x_{2},y_{2})=\left({\frac {x_{1}y_{2}+x_{2}y_{1}}{1+dx_{1}x_{2}y_{1}y_{2}}},{\frac {y_{1}y_{2}-x_{1}x_{2}}{1-dx_{1}x_{2}y_{1}y_{2}}}\right)\,}

The <a href="/facts/Additive_inverse/n8gKUmCf">opposite</a> of any point 
 
 
 
 (
 x
 ,
 y
 )
 
 
 {\displaystyle (x,y)}
 
 is 
 
 
 
 (
 −
 x
 ,
 y
 )
 
 
 {\displaystyle (-x,y)}
 
. The point 
 
 
 
 (
 0
 ,
 −
 1
 )
 
 
 {\displaystyle (0,-1)}
 
 has order 2, and the points 
 
 
 
 (
 ±
 1
 ,
 0
 )
 
 
 {\displaystyle (\pm 1,0)}
 
 have order 4. In particular, an Edwards curve always has a point of order 4 with coordinates in K.
If d is not a square in K and 
 
 
 
 {
 (
 
 x
 
 1
 
 
 ,
 
 y
 
 1
 
 
 )
 ,
 (
 
 x
 
 2
 
 
 ,
 
 y
 
 2
 
 
 )
 }
 ∈
 {
 (
 x
 ,
 y
 )
 
 |
 
 
 x
 
 2
 
 
 +
 
 y
 
 2
 
 
 =
 1
 +
 d
 
 x
 
 2
 
 
 
 y
 
 2
 
 
 
 }
 
 2
 
 
 
 
 {\displaystyle \{(x_{1},y_{1}),(x_{2},y_{2})\}\in \{(x,y)|x^{2}+y^{2}=1+dx^{2}y^{2}\}^{2}}
 
, then there are no exceptional points: the denominators 
 
 
 
 1
 +
 d
 
 x
 
 1
 
 
 
 x
 
 2
 
 
 
 y
 
 1
 
 
 
 y
 
 2
 
 
 
 
 {\displaystyle 1+dx_{1}x_{2}y_{1}y_{2}}
 
 and 
 
 
 
 1
 −
 d
 
 x
 
 1
 
 
 
 x
 
 2
 
 
 
 y
 
 1
 
 
 
 y
 
 2
 
 
 
 
 {\displaystyle 1-dx_{1}x_{2}y_{1}y_{2}}
 
 are always nonzero. Therefore, the Edwards addition law is complete when d is not a square in K. This means that the formulas work for all pairs of input points on the Edwards curve with no exceptions for doubling, no exception for the neutral element, no exception for negatives, etc.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> In other words, it is defined for all pairs of input points on the Edwards curve over K and the result gives the sum of the input points.
If d is a square in K, then the same operation can have exceptional points, i.e. there can be pairs of points 
 
 
 
 (
 
 x
 
 1
 
 
 ,
 
 y
 
 1
 
 
 )
 ,
 (
 
 x
 
 2
 
 
 ,
 
 y
 
 2
 
 
 )
 ∈
 {
 (
 x
 ,
 y
 )
 
 |
 
 
 x
 
 2
 
 
 +
 
 y
 
 2
 
 
 =
 1
 +
 d
 
 x
 
 2
 
 
 
 y
 
 2
 
 
 }
 
 
 {\displaystyle (x_{1},y_{1}),(x_{2},y_{2})\in \{(x,y)|x^{2}+y^{2}=1+dx^{2}y^{2}\}}
 
 such that one of the denominators becomes zero: either 
 
 
 
 1
 +
 d
 
 x
 
 1
 
 
 
 x
 
 2
 
 
 
 y
 
 1
 
 
 
 y
 
 2
 
 
 =
 0
 
 
 {\displaystyle 1+dx_{1}x_{2}y_{1}y_{2}=0}
 
 or 
 
 
 
 1
 −
 d
 
 x
 
 1
 
 
 
 x
 
 2
 
 
 
 y
 
 1
 
 
 
 y
 
 2
 
 
 =
 0
 
 
 {\displaystyle 1-dx_{1}x_{2}y_{1}y_{2}=0}
 
.
One of the attractive features of the Edwards Addition law is that it is strongly unified i.e. it can also be used to double a point, simplifying protection against <a href="/facts/Side-channel_attack/2B1dfBty">side-channel attack</a>. The addition formula above is faster than other unified formulas and has the strong property of completeness<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>
Example of addition law :
Consider the elliptic curve in the Edwards form with d=2

x
          
            2
          
        
        +
        
          y
          
            2
          
        
        =
        1
        +
        2
        
          x
          
            2
          
        
        
          y
          
            2
          
        
      
    
    {\displaystyle {\displaystyle }x^{2}+y^{2}=1+2x^{2}y^{2}}

and the point 
 
 
 
 
 P
 
 1
 
 
 =
 (
 1
 ,
 0
 )
 
 
 {\displaystyle P_{1}=(1,0)}
 
 on it. It is possible to prove that the sum of P1 with the neutral element (0,1) gives again P1. Indeed, using the formula given above, the coordinates of the point given by this sum are:

x
          
            3
          
        
        =
        
          
            
              
                x
                
                  1
                
              
              
                y
                
                  2
                
              
              +
              
                y
                
                  1
                
              
              
                x
                
                  2
                
              
            
            
              1
              +
              2
              
                x
                
                  1
                
              
              
                x
                
                  2
                
              
              
                y
                
                  1
                
              
              
                y
                
                  2
                
              
            
          
        
        =
        1
      
    
    {\displaystyle x_{3}={\frac {x_{1}y_{2}+y_{1}x_{2}}{1+2x_{1}x_{2}y_{1}y_{2}}}=1}

y
          
            3
          
        
        =
        
          
            
              
                y
                
                  1
                
              
              
                y
                
                  2
                
              
              −
              
                x
                
                  1
                
              
              
                x
                
                  2
                
              
            
            
              1
              −
              2
              
                x
                
                  1
                
              
              
                x
                
                  2
                
              
              
                y
                
                  1
                
              
              
                y
                
                  2
                
              
            
          
        
        =
        0
      
    
    {\displaystyle y_{3}={\frac {y_{1}y_{2}-x_{1}x_{2}}{1-2x_{1}x_{2}y_{1}y_{2}}}=0}

<h3>An analogue on the circle</h3>

To understand better the concept of "addition" of points on a curve, a nice example is given by the classical circle group:
take the circle of radius 1

x
          
            2
          
        
        +
        
          y
          
            2
          
        
        =
        1
      
    
    {\displaystyle {\displaystyle }x^{2}+y^{2}=1}

and consider two points P1=(x1,y1), P2=(x2,y2) on it. Let α1 and α2 be the angles such that:

P
          
            1
          
        
        =
        (
        
          x
          
            1
          
        
        ,
        
          y
          
            1
          
        
        )
        =
        (
        sin
        ⁡
        
          
            α
            
              1
            
          
        
        ,
        cos
        ⁡
        
          
            α
            
              1
            
          
        
        )
      
    
    {\displaystyle {\displaystyle }P_{1}=(x_{1},y_{1})=(\sin {\alpha _{1}},\cos {\alpha _{1}})}

P
          
            2
          
        
        =
        (
        
          x
          
            2
          
        
        ,
        
          y
          
            2
          
        
        )
        =
        (
        sin
        ⁡
        
          
            α
            
              2
            
          
        
        ,
        cos
        ⁡
        
          
            α
            
              2
            
          
        
        )
      
    
    {\displaystyle {\displaystyle }P_{2}=(x_{2},y_{2})=(\sin {\alpha _{2}},\cos {\alpha _{2}})}

The sum of P1 and P2 is, thus, given by the sum of "their angles". That is, the point P3=P1+P2 is a point on the circle with coordinates (x3,y3), where:

x
          
            3
          
        
        =
        sin
        ⁡
        (
        
          
            α
          
          
            1
          
        
        +
        
          
            α
          
          
            2
          
        
        )
        =
        sin
        ⁡
        
          
            α
          
          
            1
          
        
        cos
        ⁡
        
          
            α
          
          
            2
          
        
        +
        sin
        ⁡
        
          
            α
          
          
            2
          
        
        cos
        ⁡
        
          
            α
          
          
            1
          
        
        =
        
          x
          
            1
          
        
        
          y
          
            2
          
        
        +
        
          x
          
            2
          
        
        
          y
          
            1
          
        
      
    
    {\displaystyle {\displaystyle }x_{3}=\sin({\alpha }_{1}+{\alpha }_{2})=\sin {\alpha }_{1}\cos {\alpha }_{2}+\sin {\alpha }_{2}\cos {\alpha }_{1}=x_{1}y_{2}+x_{2}y_{1}}

y
          
            3
          
        
        =
        cos
        ⁡
        (
        
          
            α
          
          
            1
          
        
        +
        
          
            α
          
          
            2
          
        
        )
        =
        cos
        ⁡
        
          
            α
          
          
            1
          
        
        cos
        ⁡
        
          
            α
          
          
            2
          
        
        −
        sin
        ⁡
        
          
            α
          
          
            1
          
        
        sin
        ⁡
        
          
            α
          
          
            2
          
        
        =
        
          y
          
            1
          
        
        
          y
          
            2
          
        
        −
        
          x
          
            1
          
        
        
          x
          
            2
          
        
        .
      
    
    {\displaystyle {\displaystyle }y_{3}=\cos({\alpha }_{1}+{\alpha }_{2})=\cos {\alpha }_{1}\cos {\alpha }_{2}-\sin {\alpha }_{1}\sin {\alpha }_{2}=y_{1}y_{2}-x_{1}x_{2}.}

In this way, the addition formula for points on the circle of radius 1 is:

(
 
 x
 
 1
 
 
 ,
 
 y
 
 1
 
 
 )
 +
 (
 
 x
 
 2
 
 
 ,
 
 y
 
 2
 
 
 )
 =
 (
 
 x
 
 1
 
 
 
 y
 
 2
 
 
 +
 
 x
 
 2
 
 
 
 y
 
 1
 
 
 ,
 
 y
 
 1
 
 
 
 y
 
 2
 
 
 −
 
 x
 
 1
 
 
 
 x
 
 2
 
 
 )
 
 
 {\displaystyle {\displaystyle }(x_{1},y_{1})+(x_{2},y_{2})=(x_{1}y_{2}+x_{2}y_{1},y_{1}y_{2}-x_{1}x_{2})}
 
.
<h3>Addition on Edwards curves</h3>

The points on an elliptic curve form an abelian group: one can add points and take integer multiples of a single point. When an elliptic curve is described by a non-singular cubic equation, then the sum of two points P and Q, denoted P + Q, is directly related to third point of intersection between the curve and the <a href="/facts/Elliptic_curve/60jvaHSA">line that passes through P and Q</a>.
The birational mapping between an Edwards curve and the corresponding cubic elliptic curve maps the straight lines into conic sections<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>

A
 x
 y
 +
 B
 x
 +
 C
 y
 +
 D
 =
 0
 
 
 {\displaystyle Axy+Bx+Cy+D=0}
 
. In other words, for the Edwards curves the three points 
 
 
 
 P
 
 
 {\displaystyle P}
 
, 
 
 
 
 Q
 
 
 {\displaystyle Q}
 
 and 
 
 
 
 −
 (
 P
 +
 Q
 )
 
 
 {\displaystyle -(P+Q)}
 
 lie on a <a href="/facts/Hyperbola/6R6ER0mY">hyperbola</a>.
Given two distinct non-identity points 
 
 
 
 
 P
 
 1
 
 
 =
 (
 
 x
 
 1
 
 
 ,
 
 y
 
 1
 
 
 )
 ,
 
 P
 
 2
 
 
 =
 (
 
 x
 
 2
 
 
 ,
 
 y
 
 2
 
 
 )
 ,
 
 P
 
 1
 
 
 ≠
 
 P
 
 2
 
 
 
 
 {\displaystyle P_{1}=(x_{1},y_{1}),P_{2}=(x_{2},y_{2}),P_{1}\neq P_{2}}
 
, the coefficients of the quadratic form are (up to scalars):

 
 
 
 A
 =
 (
 
 x
 
 1
 
 
 −
 
 x
 
 2
 
 
 )
 +
 (
 
 x
 
 1
 
 
 
 y
 
 2
 
 
 −
 
 x
 
 2
 
 
 
 y
 
 1
 
 
 )
 
 
 {\displaystyle A=(x_{1}-x_{2})+(x_{1}y_{2}-x_{2}y_{1})}
 
,

 
 
 
 B
 =
 (
 
 x
 
 2
 
 
 
 y
 
 2
 
 
 −
 
 x
 
 1
 
 
 
 y
 
 1
 
 
 )
 +
 
 y
 
 1
 
 
 
 y
 
 2
 
 
 (
 
 x
 
 2
 
 
 −
 
 x
 
 1
 
 
 )
 
 
 {\displaystyle B=(x_{2}y_{2}-x_{1}y_{1})+y_{1}y_{2}(x_{2}-x_{1})}
 
,

 
 
 
 C
 =
 
 x
 
 1
 
 
 
 x
 
 2
 
 
 (
 
 y
 
 1
 
 
 −
 
 y
 
 2
 
 
 )
 ,
 D
 =
 C
 
 
 {\displaystyle C=x_{1}x_{2}(y_{1}-y_{2}),D=C}

In the case of doubling a point 
 
 
 
 P
 =
 (
 x
 ,
 y
 )
 
 
 {\displaystyle P=(x,y)}
 
 the inverse point 
 
 
 
 −
 2
 P
 
 
 {\displaystyle -2P}
 
 lies on the conic that touches the curve at the point 
 
 
 
 P
 
 
 {\displaystyle P}
 
. The coefficients of the quadratic form that defines the conic are (up to scalars):

 
 
 
 A
 =
 d
 
 x
 
 2
 
 
 y
 −
 1
 
 
 {\displaystyle A=dx^{2}y-1}
 
,

 
 
 
 B
 =
 y
 −
 
 x
 
 2
 
 
 
 
 {\displaystyle B=y-x^{2}}
 
,

 
 
 
 C
 =
 x
 (
 1
 −
 y
 )
 ,
 D
 =
 C
 
 
 {\displaystyle C=x(1-y),D=C}

<h2 id="projective-homogeneous-coordinates">Projective homogeneous coordinates</h2>
In the context of cryptography, <a href="/facts/Homogeneous_coordinates/TG9ebKN4">homogeneous coordinates</a> are used to prevent <a href="/facts/Elliptic_curve_cryptography/YbjcXIWk">field inversions</a> that appear in the affine formula. To avoid inversions in the original Edwards addition formulas, the curve equation can be written in <a href="/facts/Projective_space/7MSpA9cM">projective coordinates</a> as:

 
 
 
 (
 
 X
 
 2
 
 
 +
 
 Y
 
 2
 
 
 )
 
 Z
 
 2
 
 
 =
 
 Z
 
 4
 
 
 +
 d
 
 X
 
 2
 
 
 
 Y
 
 2
 
 
 
 
 {\displaystyle (X^{2}+Y^{2})Z^{2}=Z^{4}+dX^{2}Y^{2}}
 
.
A projective point 
 
 
 
 (
 X
 :
 Y
 :
 Z
 )
 
 
 {\displaystyle (X:Y:Z)}
 
 corresponds to the <a href="/facts/Affine_space/tlvI3oX1">affine point</a> 
 
 
 
 (
 X
 
 /
 
 Z
 :
 Y
 
 /
 
 Z
 )
 
 
 {\displaystyle (X/Z:Y/Z)}
 
 on the Edwards curve.
The identity element is represented by 
 
 
 
 (
 0
 :
 1
 :
 1
 )
 
 
 {\displaystyle (0:1:1)}
 
. The inverse of 
 
 
 
 (
 X
 :
 Y
 :
 Z
 )
 
 
 {\displaystyle (X:Y:Z)}
 
 is 
 
 
 
 (
 −
 X
 :
 Y
 :
 Z
 )
 
 
 {\displaystyle (-X:Y:Z)}
 
.
The addition formula in homogeneous coordinates is given by: 
 
 
 
 (
 
 X
 
 1
 
 
 :
 
 Y
 
 1
 
 
 :
 
 Z
 
 1
 
 
 )
 +
 (
 
 X
 
 2
 
 
 :
 
 Y
 
 2
 
 
 :
 
 Z
 
 2
 
 
 )
 =
 (
 
 X
 
 3
 
 
 :
 
 Y
 
 3
 
 
 :
 
 Z
 
 3
 
 
 )
 
 
 {\displaystyle (X_{1}:Y_{1}:Z_{1})+(X_{2}:Y_{2}:Z_{2})=(X_{3}:Y_{3}:Z_{3})}

where

 
 
 
 
 X
 
 3
 
 
 =
 
 Z
 
 1
 
 
 
 Z
 
 2
 
 
 (
 
 X
 
 1
 
 
 
 Y
 
 2
 
 
 +
 
 X
 
 2
 
 
 
 Y
 
 1
 
 
 )
 (
 
 Z
 
 1
 
 
 2
 
 
 
 Z
 
 2
 
 
 2
 
 
 −
 d
 
 X
 
 1
 
 
 
 X
 
 2
 
 
 
 Y
 
 1
 
 
 
 Y
 
 2
 
 
 )
 
 
 {\displaystyle X_{3}=Z_{1}Z_{2}(X_{1}Y_{2}+X_{2}Y_{1})(Z_{1}^{2}Z_{2}^{2}-dX_{1}X_{2}Y_{1}Y_{2})}

Y
 
 3
 
 
 =
 
 Z
 
 1
 
 
 
 Z
 
 2
 
 
 (
 
 Y
 
 1
 
 
 
 Y
 
 2
 
 
 −
 
 X
 
 1
 
 
 
 X
 
 2
 
 
 )
 (
 
 Z
 
 1
 
 
 2
 
 
 
 Z
 
 2
 
 
 2
 
 
 +
 d
 
 X
 
 1
 
 
 
 X
 
 2
 
 
 
 Y
 
 1
 
 
 
 Y
 
 2
 
 
 )
 
 
 {\displaystyle Y_{3}=Z_{1}Z_{2}(Y_{1}Y_{2}-X_{1}X_{2})(Z_{1}^{2}Z_{2}^{2}+dX_{1}X_{2}Y_{1}Y_{2})}

Z
 
 3
 
 
 =
 (
 
 Z
 
 1
 
 
 2
 
 
 
 Z
 
 2
 
 
 2
 
 
 −
 d
 
 X
 
 1
 
 
 
 X
 
 2
 
 
 
 Y
 
 1
 
 
 
 Y
 
 2
 
 
 )
 (
 
 Z
 
 1
 
 
 2
 
 
 
 Z
 
 2
 
 
 2
 
 
 +
 d
 
 X
 
 1
 
 
 
 X
 
 2
 
 
 
 Y
 
 1
 
 
 
 Y
 
 2
 
 
 )
 
 
 {\displaystyle Z_{3}=(Z_{1}^{2}Z_{2}^{2}-dX_{1}X_{2}Y_{1}Y_{2})(Z_{1}^{2}Z_{2}^{2}+dX_{1}X_{2}Y_{1}Y_{2})}

<h3>Algorithm</h3>
Addition of two points on the Edwards curve could be computed more efficiently<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> in the extended Edwards form 
 
 
 
 (
 X
 :
 Y
 :
 Z
 :
 T
 )
 
 
 {\displaystyle (X:Y:Z:T)}
 
, where 
 
 
 
 T
 =
 X
 Y
 
 /
 
 Z
 
 
 {\displaystyle T=XY/Z}
 
: 
 
 
 
 (
 
 X
 
 3
 
 
 :
 
 Y
 
 3
 
 
 :
 
 Z
 
 3
 
 
 :
 
 T
 
 3
 
 
 )
 =
 (
 
 X
 
 1
 
 
 :
 
 Y
 
 1
 
 
 :
 
 Z
 
 1
 
 
 :
 
 T
 
 1
 
 
 )
 +
 (
 
 X
 
 2
 
 
 :
 
 Y
 
 2
 
 
 :
 
 Z
 
 2
 
 
 :
 
 T
 
 2
 
 
 )
 
 
 {\displaystyle (X_{3}:Y_{3}:Z_{3}:T_{3})=(X_{1}:Y_{1}:Z_{1}:T_{1})+(X_{2}:Y_{2}:Z_{2}:T_{2})}

A
 =
 
 X
 
 1
 
 
 
 X
 
 2
 
 
 ;
 B
 =
 
 Y
 
 1
 
 
 
 Y
 
 2
 
 
 ;
 C
 =
 d
 
 T
 
 1
 
 
 
 T
 
 2
 
 
 ;
 D
 =
 
 Z
 
 1
 
 
 
 Z
 
 2
 
 
 ;
 
 
 {\displaystyle A=X_{1}X_{2};B=Y_{1}Y_{2};C=dT_{1}T_{2};D=Z_{1}Z_{2};}

E
 =
 (
 
 X
 
 1
 
 
 +
 
 Y
 
 1
 
 
 )
 (
 
 X
 
 2
 
 
 +
 
 Y
 
 2
 
 
 )
 −
 A
 −
 B
 ;
 F
 =
 D
 −
 C
 ;
 G
 =
 D
 +
 C
 ;
 H
 =
 B
 −
 A
 ;
 
 
 {\displaystyle E=(X_{1}+Y_{1})(X_{2}+Y_{2})-A-B;F=D-C;G=D+C;H=B-A;}

X
 
 3
 
 
 =
 E
 ⋅
 F
 ;
 
 Y
 
 3
 
 
 =
 G
 ⋅
 H
 ;
 
 Z
 
 3
 
 
 =
 F
 ⋅
 G
 ;
 
 T
 
 3
 
 
 =
 E
 ⋅
 H
 ;
 
 
 {\displaystyle X_{3}=E\cdot F;Y_{3}=G\cdot H;Z_{3}=F\cdot G;T_{3}=E\cdot H;}

<h2 id="doubling">Doubling</h2>
Doubling can be performed with exactly the same formula as addition. Doubling refers to the case in which the inputs (x1, y1) and (x2, y2) are equal.
Doubling a point 
 
 
 
 P
 =
 (
 x
 ,
 y
 )
 
 
 {\displaystyle P=(x,y)}
 
: 

 
 
 
 
 
 
 
 (
 x
 ,
 y
 )
 +
 (
 x
 ,
 y
 )
 
 
 
 =
 
 (
 
 
 
 
 2
 x
 y
 
 
 1
 +
 d
 
 x
 
 2
 
 
 
 y
 
 2
 
 
 
 
 
 ,
 
 
 
 
 y
 
 2
 
 
 −
 
 x
 
 2
 
 
 
 
 1
 −
 d
 
 x
 
 2
 
 
 
 y
 
 2
 
 
 
 
 
 
 )
 
 
 
 
 
 
 
 =
 
 (
 
 
 
 
 2
 x
 y
 
 
 
 x
 
 2
 
 
 +
 
 y
 
 2
 
 
 
 
 
 ,
 
 
 
 
 y
 
 2
 
 
 −
 
 x
 
 2
 
 
 
 
 2
 −
 
 x
 
 2
 
 
 −
 
 y
 
 2
 
 
 
 
 
 
 )
 
 
 
 
 
 
 
 {\displaystyle {\begin{aligned}(x,y)+(x,y)&=\left({\frac {2xy}{1+dx^{2}y^{2}}},{\frac {y^{2}-x^{2}}{1-dx^{2}y^{2}}}\right)\\[6pt]&=\left({\frac {2xy}{x^{2}+y^{2}}},{\frac {y^{2}-x^{2}}{2-x^{2}-y^{2}}}\right)\end{aligned}}}

The denominators were simplified based on the curve equation 
 
 
 
 
 x
 
 2
 
 
 +
 
 y
 
 2
 
 
 =
 1
 +
 d
 
 x
 
 2
 
 
 
 y
 
 2
 
 
 
 
 {\displaystyle x^{2}+y^{2}=1+dx^{2}y^{2}}
 
. Further speedup is achieved by computing 
 
 
 
 2
 x
 y
 
 
 {\displaystyle 2xy}
 
 as 
 
 
 
 (
 x
 +
 y
 
 )
 
 2
 
 
 −
 
 x
 
 2
 
 
 −
 
 y
 
 2
 
 
 
 
 {\displaystyle (x+y)^{2}-x^{2}-y^{2}}
 
. This reduces the cost of doubling in homomorphic coordinates to 3M + 4S + 3C + 6a, while general addition costs 10M + 1S + 1C + 1D + 7a. Here M is field multiplications, S is field squarings, D is the cost of multiplying by the curve parameter d, and a is field addition.

Example of doubling
As in the previous example for the addition law, consider the Edwards curve with d=2:

 
 
 
 
 x
 
 2
 
 
 +
 
 y
 
 2
 
 
 =
 1
 +
 2
 
 x
 
 2
 
 
 
 y
 
 2
 
 
 
 
 {\displaystyle x^{2}+y^{2}=1+2x^{2}y^{2}}

and the point 
 
 
 
 P
 =
 (
 1
 ,
 0
 )
 
 
 {\displaystyle P=(1,0)}
 
. The coordinates of the point 
 
 
 
 
 P
 
 2
 
 
 =
 2
 
 P
 
 1
 
 
 
 
 {\displaystyle P_{2}=2P_{1}}
 
 are:

 
 
 
 
 x
 
 2
 
 
 =
 
 
 
 2
 x
 y
 
 
 
 x
 
 2
 
 
 +
 
 y
 
 2
 
 
 
 
 
 =
 0
 
 
 {\displaystyle x_{2}={\frac {2xy}{x^{2}+y^{2}}}=0}

y
 
 2
 
 
 =
 
 
 
 
 y
 
 2
 
 
 −
 
 x
 
 2
 
 
 
 
 2
 −
 (
 
 x
 
 2
 
 
 +
 
 y
 
 2
 
 
 )
 
 
 
 =
 −
 1
 
 
 {\displaystyle y_{2}={\frac {y^{2}-x^{2}}{2-(x^{2}+y^{2})}}=-1}

The point obtained from doubling P is thus 
 
 
 
 
 P
 
 2
 
 
 =
 (
 0
 ,
 −
 1
 )
 
 
 {\displaystyle P_{2}=(0,-1)}
 
.

<h2 id="mixed-addition">Mixed addition</h2>
Mixed addition is the case when Z2 is known to be 1. In such a case A=Z1.Z2 can be eliminated and the total cost reduces to 9M+1S+1C+1D+7a

<h3>Algorithm</h3>
A= Z1.Z2 // in other words, A= Z1
B= Z12
C=X1.X2
D=Y1.Y2
E=d.C.D
F=B-E
G=B+E
X3= A.F((XI+Y1).(X2+Y2)-C-D)
Y3= A.G.(D-C)
Z3=C.F.G

<h2 id="tripling">Tripling</h2>
Tripling can be done by first doubling the point and then adding the result to itself. By applying the curve equation as in doubling, we obtain

3
        (
        
          x
          
            1
          
        
        ,
        
          y
          
            1
          
        
        )
        =
        
          (
          
            
              
                
                  (
                  
                    x
                    
                      1
                    
                    
                      2
                    
                  
                  +
                  
                    y
                    
                      1
                    
                    
                      2
                    
                  
                  
                    )
                    
                      2
                    
                  
                  −
                  (
                  2
                  
                    y
                    
                      1
                    
                  
                  
                    )
                    
                      2
                    
                  
                
                
                  4
                  (
                  
                    x
                    
                      1
                    
                    
                      2
                    
                  
                  −
                  1
                  )
                  
                    x
                    
                      1
                    
                    
                      2
                    
                  
                  −
                  (
                  
                    x
                    
                      1
                    
                    
                      2
                    
                  
                  −
                  
                    y
                    
                      1
                    
                    
                      2
                    
                  
                  
                    )
                    
                      2
                    
                  
                
              
            
            
              x
              
                1
              
            
            ,
            
              
                
                  (
                  
                    x
                    
                      1
                    
                    
                      2
                    
                  
                  +
                  
                    y
                    
                      1
                    
                    
                      2
                    
                  
                  
                    )
                    
                      2
                    
                  
                  −
                  (
                  2
                  
                    x
                    
                      1
                    
                  
                  
                    )
                    
                      2
                    
                  
                
                
                  −
                  4
                  (
                  
                    y
                    
                      1
                    
                    
                      2
                    
                  
                  −
                  1
                  )
                  
                    y
                    
                      1
                    
                    
                      2
                    
                  
                  +
                  (
                  
                    x
                    
                      1
                    
                    
                      2
                    
                  
                  −
                  
                    y
                    
                      1
                    
                    
                      2
                    
                  
                  
                    )
                    
                      2
                    
                  
                
              
            
            
              y
              
                1
              
            
          
          )
        
        .
        
      
    
    {\displaystyle 3(x_{1},y_{1})=\left({\frac {(x_{1}^{2}+y_{1}^{2})^{2}-(2y_{1})^{2}}{4(x_{1}^{2}-1)x_{1}^{2}-(x_{1}^{2}-y_{1}^{2})^{2}}}x_{1},{\frac {(x_{1}^{2}+y_{1}^{2})^{2}-(2x_{1})^{2}}{-4(y_{1}^{2}-1)y_{1}^{2}+(x_{1}^{2}-y_{1}^{2})^{2}}}y_{1}\right).\,}

There are two sets of formulas for this operation in standard Edwards coordinates. The first one costs 9M + 4S while the second needs 7M + 7S. If the S/M ratio is very small, specifically below 2/3, then the second set is better while for larger ratios the first one is to be preferred.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>
Using the addition and doubling formulas (as mentioned above) the point (X1 : Y1 : Z1) is symbolically computed as 3(X1 : Y1 : Z1) and compared with (X3 : Y3 : Z3)

Example of tripling
Giving the Edwards curve with d=2, and the point P1=(1,0), the point 3P1 has coordinates:

 
 
 
 
 x
 
 3
 
 
 =
 
 
 
 (
 
 x
 
 1
 
 
 2
 
 
 +
 
 y
 
 1
 
 
 2
 
 
 
 )
 
 2
 
 
 −
 (
 2
 
 y
 
 1
 
 
 
 )
 
 2
 
 
 
 
 4
 (
 
 x
 
 1
 
 
 2
 
 
 −
 1
 )
 
 x
 
 1
 
 
 2
 
 
 −
 (
 
 x
 
 1
 
 
 2
 
 
 −
 
 y
 
 1
 
 
 2
 
 
 
 )
 
 2
 
 
 
 
 
 
 x
 
 1
 
 
 =
 −
 1
 
 
 {\displaystyle x_{3}={\frac {(x_{1}^{2}+y_{1}^{2})^{2}-(2y_{1})^{2}}{4(x_{1}^{2}-1)x_{1}^{2}-(x_{1}^{2}-y_{1}^{2})^{2}}}x_{1}=-1}

y
 
 3
 
 
 =
 
 
 
 (
 
 x
 
 1
 
 
 2
 
 
 +
 
 y
 
 1
 
 
 2
 
 
 
 )
 
 2
 
 
 −
 2
 (
 
 x
 
 1
 
 
 
 )
 
 2
 
 
 
 
 −
 4
 (
 
 y
 
 1
 
 
 2
 
 
 −
 1
 )
 
 y
 
 1
 
 
 2
 
 
 +
 (
 
 x
 
 1
 
 
 2
 
 
 −
 
 y
 
 1
 
 
 2
 
 
 
 )
 
 2
 
 
 
 
 
 
 y
 
 1
 
 
 =
 0
 
 
 {\displaystyle y_{3}={\frac {(x_{1}^{2}+y_{1}^{2})^{2}-2(x_{1})^{2}}{-4(y_{1}^{2}-1)y_{1}^{2}+(x_{1}^{2}-y_{1}^{2})^{2}}}y_{1}=0}

So, 3P1=(-1,0)=P-1. This result can also be found considering the doubling example: 2P1=(0,1), so 3P1 = 2P1 + P1 = (0,-1) + P1 = -P1.

Algorithm
A=X12
B=Y12
C=(2Z1)2
D=A+B
E=D2
F=2D.(A-B)
G=E-B.C
H=E-A.C
I=F+H
J=F-G
X3=G.J.X1
Y3=H.I.Y1
Z3=I.J.Z1
This formula costs 9M + 4S

<h2 id="inverted-edwards-coordinates">Inverted Edwards coordinates</h2>
Bernstein and Lange introduced an even faster coordinate system for elliptic curves called the Inverted Edward coordinates<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a> in which the coordinates (X : Y : Z) satisfy the curve (X2 + Y2)Z2 = (dZ4 + X2Y2) and corresponds
to the affine point (Z/X, Z/Y) on the Edwards curve x2 + y2 = 1 + dx2y2 with XYZ ≠ 0.
Inverted Edwards coordinates, unlike standard Edwards coordinates, do not have complete addition formulas: some points, such as the neutral element, must be handled separately. But the addition formulas still have the advantage of strong unification: they can be used without change to double a point.
For more information about operations with these coordinates see <a href="http://hyperelliptic.org/EFD/g1p/auto-edwards-inverted.html">http://hyperelliptic.org/EFD/g1p/auto-edwards-inverted.html</a>

<h2 id="extended-coordinates-for-edward-curves">Extended Coordinates for Edward Curves</h2>
There is another coordinates system with which an Edwards curve can be represented. These new coordinates are called extended coordinates<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a> and are even faster than inverted coordinates. For more information about the time-cost required in the operations with these coordinates see:
<a href="http://hyperelliptic.org/EFD/g1p/auto-edwards.html">http://hyperelliptic.org/EFD/g1p/auto-edwards.html</a>

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Twisted_Edwards_curve/mz1EMMNL">Twisted Edwards curve</a></li></ul>
For more information about the running-time required in a specific case, see <a href="/facts/Table_of_costs_of_operations_in_elliptic_curves/dwCyhAKr">Table of costs of operations in elliptic curves</a>.

<h2 id="notes">Notes</h2>

<ul><li><a href="/facts/Daniel_J._Bernstein/KQLuMRTx">Bernstein, Daniel</a>; <a href="/facts/Tanja_Lange/8bYpR72r">Lange, Tanja</a> (2007), <a href="http://cr.yp.to/newelliptic/newelliptic-20070906.pdf">Faster Addition and Doubling on Elliptic curves</a> (PDF)</li>
<li>Edwards, Harold M. (9 April 2007), "A normal form for elliptic curves", <a href="/facts/Bulletin_of_the_American_Mathematical_Society/8ER5KY5z">Bulletin of the American Mathematical Society</a>, 44 (3): 393–422, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1090%2Fs0273-0979-07-01153-6">10.1090/s0273-0979-07-01153-6</a>, <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/0002-9904">0002-9904</a></li>
<li>Faster Group Operations on Elliptic curves, H. Hisil, K. K. Wong, G. Carter, E. Dawson</li>
<li>D.J.Bernstein, P.Birkner. T. Lange, C.Peters, <a href="http://cr.yp.to/antiforgery/doublebase-20071028.pdf">Optimizing Double-Base Elliptic-Curve Single-Scalar Multiplication</a> (PDF){{citation}}: CS1 maint: multiple names: authors list (link)</li>
<li><a href="/facts/Lawrence_C._Washington/SHyW0o8j">Washington, Lawrence C.</a> (2008), Elliptic Curves: Number Theory and Cryptography, Discrete Mathematics and its Applications (2nd ed.), Chapman & Hall/CRC, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-1-4200-7146-7</li>
<li><a href="/facts/Daniel_J._Bernstein/KQLuMRTx">Bernstein, Daniel</a>; <a href="/facts/Tanja_Lange/8bYpR72r">Lange, Tanja</a>, <a href="http://cr.yp.to/newelliptic/inverted-20071009.pdf">Inverted Edwards coordinates</a> (PDF)</li></ul>
<h2 id="external-links">External links</h2>
<ul><li><a href="http://hyperelliptic.org/EFD/g1p/index.html">http://hyperelliptic.org/EFD/g1p/index.html</a></li>
<li><a href="http://hyperelliptic.org/EFD/g1p/auto-edwards.html">http://hyperelliptic.org/EFD/g1p/auto-edwards.html</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Bernstein, Daniel; Lange, Tanja (3 March 2014), How to design an elliptic-curve signature system <a href="https://blog.cr.yp.to/20140323-ecdsa.html" target="_blank">https://blog.cr.yp.to/20140323-ecdsa.html</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Daniel. J. Bernstein , Tanja Lange, pag. 3, Faster addition and doubling on elliptic curves <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Daniel. J. Bernstein , Tanja Lange, pag. 3, Faster addition and doubling on elliptic curves <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Christophe Arene; Tanja Lange; Michael Naehrig; Christophe Ritzenthaler (2009). "Faster Computation of the Tate Pairing". arXiv:0904.0854. Bibcode:2009arXiv0904.0854A. Retrieved 28 February 2010. <a href="http://eprint.iacr.org/2009/155" target="_blank">http://eprint.iacr.org/2009/155</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Huseyin Hisil, Kenneth Koon-Ho Wong, Gary Carter, and Ed Dawson. Twisted Edwards curves revisited. In ASIACRYPT
2008, pages 326–343, 2008 <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Bernstein et al., Optimizing Double-Base Elliptic curve single-scalar Multiplication <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Daniel J.Bernstein. Tanja Lange, pag.2, Inverted Edward coordinates <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">H. Hisil, K. K. Wong, G. Carter, E. Dawson Faster group operations on elliptic curves <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
</ol>

Edwards curve open-in-new

Edwards curve