Projective coordinates for binary Edwards curves

  d1*(x+y)+d2*(x^2+y^2)=(x+x^2)*(y+y^2)

Projective coordinates [database entry] represent x y as X Y Z satisfying the following equations:

  x=X/Z
  y=Y/Z

Best operation counts

• 18M for addition: 18M+2S. 18M+3S.
• 13M for addition with Z2=1: 13M+3S.
• 18M for readdition: 18M+2S after 18M+2S. 18M+3S after 18M+3S.
• 13M for readdition with Z2=1: 13M+1S after 13M+3S.
• 2M for doubling: 2M+6S.
• 12M for scaling: 1I+2M.

• 18.4M for addition: 18M+2S.
• 13.6M for addition with Z2=1: 13M+3S.
• 18.4M for readdition: 18M+2S after 18M+2S.
• 13.2M for readdition with Z2=1: 13M+1S after 13M+3S.
• 3.2M for doubling: 2M+6S.
• 12M for scaling: 1I+2M.

Summary of all explicit formulas

Explicit formulas for addition

• Assumptions: Z2=1.
• Cost: 13M + 3S + 2*d1 + 1*d2 + 15add.
• Cost: 13M + 1S + 2*d1 + 1*d2 + 12add dependent upon the first point.
• Source: 2008 Bernstein–Lange–Rezaeian Farashahi.
• Strongly unified.
• Explicit formulas:

        W1 = X1+Y1
        w2 = X2+Y2
        A = X2^2+X2
        B = Y2^2+Y2
        D = W1*Z1
        E = d1*Z1^2
        H = (E+d2*D)*w2
        I = d1*Z1
        U = E+A*D
        V = E+B*D
        Z3 = U*V
        X3 = Z3*Y2+(H+X1*(I+A*(Y1+Z1)))*V
        Y3 = Z3*X2+(H+Y1*(I+B*(X1+Z1)))*U
  

• Assumptions: d2plusd1=d2+d1 and d1d1=d1^².
• Cost: 18M + 2S + 1*d1d1 + 3*d1 + 1*d2 + 2*d2plusd1 + 24add.
• Cost: 18M + 2S + 1*d1d1 + 3*d1 + 1*d2 + 2*d2plusd1 + 21add dependent upon the first point.
• Source: 2008 Bernstein-–Lange-–Rezaeian Farashahi.
• Strongly unified.
• Explicit formulas:

        A = X1*X2
        B = Y1*Y2
        C = Z1*Z2
        D = d1*C
        E = C^2
        F = d1d1*E
        G = (X1+Z1)*(X2+Z2)
        H = (Y1+Z1)*(Y2+Z2)
        I = A+G
        J = B+H
        K = (X1+Y1)*(X2+Y2)
        U = C*(F+d1*K*(K+I+J+C))
        V = U+D*F+K*(d2*(d1*E+G*H+A*B)+d2plusd1*I*J)
        X3 = V+D*(A+D)*(G+D)
        Y3 = V+D*(B+D)*(H+D)
        Z3 = U+d2plusd1*C*K^2
  

• Assumptions: d2plusd1=d2+d1 and d1d1=d1^².
• Cost: 18M + 3S + 3*d1 + 1*d2 + 2*d2plusd1 + 24add.
• Cost: 18M + 3S + 3*d1 + 1*d2 + 2*d2plusd1 + 21add dependent upon the first point.
• Source: 2008 Bernstein-–Lange-–Rezaeian Farashahi.
• Strongly unified.
• Explicit formulas:

        A = X1*X2
        B = Y1*Y2
        C = Z1*Z2
        D = d1*C
        E = C^2
        F = D^2
        G = (X1+Z1)*(X2+Z2)
        H = (Y1+Z1)*(Y2+Z2)
        I = A+G
        J = B+H
        K = (X1+Y1)*(X2+Y2)
        U = C*(F+d1*K*(K+I+J+C))
        V = U+D*F+K*(d2*(d1*E+G*H+A*B)+d2plusd1*I*J)
        X3 = V+D*(A+D)*(G+D)
        Y3 = V+D*(B+D)*(H+D)
        Z3 = U+d2plusd1*C*K^2
  

• Cost: 21M + 1S + 3*d1 + 1*d2 + 15add.
• Cost: 20M + 1S + 2*d1 + 11add dependent upon the first point.
• Source: 2008 Bernstein-–Lange-–Rezaeian Farashahi.
• Strongly unified.
• Explicit formulas:

        W1 = X1+Y1
        W2 = X2+Y2
        A = X1*(X1+Z1)
        B = Y1*(Y1+Z1)
        C = Z1*Z2
        D = W2*Z2
        E = d1*C^2
        H = (d1*Z2+d2*W2)*W1*C
        I = d1*C*Z1
        U = E+A*D
        V = E+B*D
        S = U*V
        X3 = S*Y1+(H+X2*(I+A*(Y2+Z2)))*V*Z1
        Y3 = S*X1+(H+Y2*(I+B*(X2+Z2)))*U*Z1
        Z3 = S*Z1
  

Explicit formulas for doubling

• Assumptions: d2d1=d2/d1.
• Cost: 2M + 6S + 1*d1 + 1*d2 + 1*d2d1 + 9add.
• Source: 2008 Bernstein-–Lange-–Rezaeian Farashahi.
• Explicit formulas:

        A = X1^2
        B = A^2
        C = Y1^2
        D = C^2
        E = Z1^2
        F = d1*E^2
        G = d2d1*(B+D)
        H = A*E
        I = C*E
        J = H+I
        K = G+d2*J
        Z3 = F+J+G
        X3 = K+H+D
        Y3 = K+I+B
  

Explicit formulas for tripling

Explicit formulas for differential addition

Explicit formulas for differential addition and doubling

Explicit formulas for scaling

• Cost: 1I + 2M + 0add.
• Explicit formulas:

        A = 1/Z1
        X3 = A*X1
        Y3 = A*Y1
        Z3 = 1