Projective coordinates for short Weierstrass curves

  y^2=x^3+a*x+b

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

  x=X/Z
  y=Y/Z

Best operation counts

• 12M for addition: 12M.
• 11M for addition with Z2=1: 9M+2S. 11M.
• 7M for addition with Z1=1 and Z2=1: 5M+2S.
• 12M for readdition: 12M after 12M.
• 11M for readdition with Z2=1: 9M+2S after 9M+2S. 11M after 11M.
• 7M for readdition with Z1=1 and Z2=1: 5M+2S after 5M+2S.
• 11M for doubling: 5M+6S. 6M+5S. 8M+3S.
• 8M for doubling with Z1=1: 3M+5S.
• 102M for scaling: 1I+2M.

• 12M for addition: 12M.
• 10.6M for addition with Z2=1: 9M+2S.
• 6.6M for addition with Z1=1 and Z2=1: 5M+2S.
• 12M for readdition: 12M after 12M.
• 10.6M for readdition with Z2=1: 9M+2S after 9M+2S.
• 6.6M for readdition with Z1=1 and Z2=1: 5M+2S after 5M+2S.
• 9.8M for doubling: 5M+6S.
• 7M for doubling with Z1=1: 3M+5S.
• 102M for scaling: 1I+2M.

• 12M for addition: 12M.
• 10.34M for addition with Z2=1: 9M+2S.
• 6.34M for addition with Z1=1 and Z2=1: 5M+2S.
• 12M for readdition: 12M after 12M.
• 10.34M for readdition with Z2=1: 9M+2S after 9M+2S.
• 6.34M for readdition with Z1=1 and Z2=1: 5M+2S after 5M+2S.
• 9.02M for doubling: 5M+6S.
• 6.35M for doubling with Z1=1: 3M+5S.
• 102M for scaling: 1I+2M.

Summary of all explicit formulas

Explicit formulas for addition

• Assumptions: Z1=1 and Z2=1.
• Cost: 5M + 2S + 6add + 1*2.
• Source: 1998 Cohen–Miyaji–Ono "Efficient elliptic curve exponentiation using mixed coordinates", plus Z1=1, plus Z2=1, plus common-subexpression elimination.
• Explicit formulas:

        u = Y2-Y1
        uu = u^2
        v = X2-X1
        vv = v^2
        vvv = v*vv
        R = vv*X1
        A = uu-vvv-2*R
        X3 = v*A
        Y3 = u*(R-A)-vvv*Y1
        Z3 = vvv
  

• Assumptions: Z2=1.
• Cost: 9M + 2S + 6add + 1*2.
• Source: 1998 Cohen–Miyaji–Ono "Efficient elliptic curve exponentiation using mixed coordinates", formula (3), plus common-subexpression elimination, plus Z2=1.
• Explicit formulas:

        u = Y2*Z1-Y1
        uu = u^2
        v = X2*Z1-X1
        vv = v^2
        vvv = v*vv
        R = vv*X1
        A = uu*Z1-vvv-2*R
        X3 = v*A
        Y3 = u*(R-A)-vvv*Y1
        Z3 = vvv*Z1
  

• Assumptions: Z2=1 and b3=3*b.
• Cost: 11M + 2*b3 + 3*a + 17add.
• Cost: 11M + 2*b3 + 3*a + 16add dependent upon the first point.
• Source: 2015 Renes–Costello–Batina "Complete addition formulas for prime order elliptic curves", Algorithm 2.
• Strongly unified.
• Explicit formulas:

        t0 = X1*X2
        t1 = Y1*Y2
        t3 = X2+Y2
        t4 = X1+Y1
        t3 = t3*t4
        t4 = t0+t1
        t3 = t3-t4
        t4 = X2*Z1
        t4 = t4+X1
        t5 = Y2*Z1
        t5 = t5+Y1
        Z3 = a*t4
        X3 = b3*Z1
        Z3 = X3+Z3
        X3 = t1-Z3
        Z3 = t1+Z3
        Y3 = X3*Z3
        t1 = t0+t0
        t1 = t1+t0
        t2 = a*Z1
        t4 = b3*t4
        t1 = t1+t2
        t2 = t0-t2
        t2 = a*t2
        t4 = t4+t2
        t0 = t1*t4
        Y3 = Y3+t0
        t0 = t5*t4
        X3 = t3*X3
        X3 = X3-t0
        t0 = t3*t1
        Z3 = t5*Z3
        Z3 = Z3+t0
  

• Assumptions: b3=3*b.
• Cost: 12M + 2*b3 + 3*a + 23add.
• Cost: 12M + 2*b3 + 3*a + 20add dependent upon the first point.
• Source: 2015 Renes–Costello–Batina "Complete addition formulas for prime order elliptic curves", Appendix A.1.
• Strongly unified.
• Explicit formulas:

        t0 = X1*X2
        t1 = Y1*Y2
        t2 = Z1*Z2
        t3 = X1+Y1
        t4 = X2+Y2
        t3 = t3*t4
        t4 = t0+t1
        t3 = t3-t4
        t4 = X1+Z1
        t5 = X2+Z2
        t4 = t4*t5
        t5 = t0+t2
        t4 = t4-t5
        t5 = Y1+Z1
        X3 = Y2+Z2
        t5 = t5*X3
        X3 = t1+t2
        t5 = t5-X3
        Z3 = a*t4
        X3 = b3*t2
        Z3 = X3+Z3
        X3 = t1-Z3
        Z3 = t1+Z3
        Y3 = X3*Z3
        t1 = t0+t0
        t1 = t1+t0
        t2 = a*t2
        t4 = b3*t4
        t1 = t1+t2
        t2 = t0-t2
        t2 = a*t2
        t4 = t4+t2
        t0 = t1*t4
        Y3 = Y3+t0
        t0 = t5*t4
        X3 = t3*X3
        X3 = X3-t0
        t0 = t3*t1
        Z3 = t5*Z3
        Z3 = Z3+t0
  

• Cost: 12M + 2S + 6add + 1*2.
• Source: 1998 Cohen–Miyaji–Ono "Efficient elliptic curve exponentiation using mixed coordinates", formula (3), plus common-subexpression elimination.
• Explicit formulas:

        Y1Z2 = Y1*Z2
        X1Z2 = X1*Z2
        Z1Z2 = Z1*Z2
        u = Y2*Z1-Y1Z2
        uu = u^2
        v = X2*Z1-X1Z2
        vv = v^2
        vvv = v*vv
        R = vv*X1Z2
        A = uu*Z1Z2-vvv-2*R
        X3 = v*A
        Y3 = u*(R-A)-vvv*Y1Z2
        Z3 = vvv*Z1Z2
  

• Cost: 11M + 6S + 1*a + 10add + 4*2 + 1*4.
• Source: 2007 Bernstein–Lange.
• Strongly unified.
• Explicit formulas:

        U1 = X1*Z2
        U2 = X2*Z1
        S1 = Y1*Z2
        S2 = Y2*Z1
        ZZ = Z1*Z2
        T = U1+U2
        TT = T^2
        M = S1+S2
        R = TT-U1*U2+a*ZZ^2
        F = ZZ*M
        L = M*F
        LL = L^2
        G = (T+L)^2-TT-LL
        W = 2*R^2-G
        X3 = 2*F*W
        Y3 = R*(G-2*W)-2*LL
        Z3 = 4*F*F^2
  

• Cost: 12M + 5S + 1*a + 7add + 3*2.
• Source: 2002 Brier–Joye "Weierstrass elliptic curves and side-channel attacks", page 339.
• Strongly unified.
• Explicit formulas:

        U1 = X1*Z2
        U2 = X2*Z1
        S1 = Y1*Z2
        S2 = Y2*Z1
        ZZ = Z1*Z2
        T = U1+U2
        M = S1+S2
        R = T^2-U1*U2+a*ZZ^2
        F = ZZ*M
        L = M*F
        G = T*L
        W = R^2-G
        X3 = 2*F*W
        Y3 = R*(G-2*W)-L^2
        Z3 = 2*F*F^2
  

• Cost: 10M + 4S + 1^³ + 7add + 1*2 + 1*3.
• Source: 1986 Chudnovsky–Chudnovsky "Sequences of numbers generated by addition in formal groups and new primality and factorization tests", page 415, formula (4.4i).
• Explicit formulas:

        U1 = X1*Z2
        U2 = X2*Z1
        S1 = Y1*Z2
        S2 = Y2*Z1
        W = Z1*Z2
        P = U2-U1
        R = S2-S1
        X3 = P*(-(U1+U2)*P^2+W*R^2)
        Y3 = (R*(-2*W*R^2+3*(U1+U2)*P^2)-P^3*(S1+S2))/2
        Z3 = W*P^3
  

• Cost: 16M + 3S + 3^³ + 6add + 1*2.
• Source: 1998 Cohen–Miyaji–Ono "Efficient elliptic curve exponentiation using mixed coordinates", formula (3).
• Explicit formulas:

        u = Y2*Z1-Y1*Z2
        v = X2*Z1-X1*Z2
        A = u^2*Z1*Z2-v^3-2*v^2*X1*Z2
        X3 = v*A
        Y3 = u*(v^2*X1*Z2-A)-v^3*Y1*Z2
        Z3 = v^3*Z1*Z2
  

Explicit formulas for doubling

• Assumptions: Z1=1.
• Cost: 3M + 5S + 7add + 4*2 + 1*3 + 1*4.
• Source: 2007 Bernstein–Lange.
• Explicit formulas:

        XX = X1^2
        w = a+3*XX
        Y1Y1 = Y1^2
        R = 2*Y1Y1
        sss = 4*Y1*R
        RR = R^2
        B = (X1+R)^2-XX-RR
        h = w^2-2*B
        X3 = 2*h*Y1
        Y3 = w*(B-h)-2*RR
        Z3 = sss
  

• Cost: 5M + 6S + 1*a + 7add + 3*2 + 1*3.
• Source: 2007 Bernstein–Lange.
• Explicit formulas:

        XX = X1^2
        ZZ = Z1^2
        w = a*ZZ+3*XX
        s = 2*Y1*Z1
        ss = s^2
        sss = s*ss
        R = Y1*s
        RR = R^2
        B = (X1+R)^2-XX-RR
        h = w^2-2*B
        X3 = h*s
        Y3 = w*(B-h)-2*RR
        Z3 = sss
  

• Cost: 6M + 5S + 1*a + 4add + 1*2 + 1*3 + 1*4 + 3*8.
• Source: 1998 Cohen–Miyaji–Ono "Efficient elliptic curve exponentiation using mixed coordinates", formula (4), plus common-subexpression elimination.
• Explicit formulas:

        w = a*Z1^2+3*X1^2
        s = Y1*Z1
        ss = s^2
        sss = s*ss
        R = Y1*s
        B = X1*R
        h = w^2-8*B
        X3 = 2*h*s
        Y3 = w*(4*B-h)-8*R^2
        Z3 = 8*sss
  

• Assumptions: b3=3*b.
• Cost: 8M + 3S + 2*b3 + 3*a + 15add.
• Source: 2015 Renes–Costello–Batina "Complete addition formulas for prime order elliptic curves", Appendix A.1.
• Explicit formulas:

        t0 = X1^2
        t1 = Y1^2
        t2 = Z1^2
        t3 = X1*Y1
        t3 = t3+t3
        Z3 = X1*Z1
        Z3 = Z3+Z3
        X3 = a*Z3
        Y3 = b3*t2
        Y3 = X3+Y3
        X3 = t1-Y3
        Y3 = t1+Y3
        Y3 = X3*Y3
        X3 = t3*X3
        Z3 = b3*Z3
        t2 = a*t2
        t3 = t0-t2
        t3 = a*t3
        t3 = t3+Z3
        Z3 = t0+t0
        t0 = Z3+t0
        t0 = t0+t2
        t0 = t0*t3
        Y3 = Y3+t0
        t2 = Y1*Z1
        t2 = t2+t2
        t0 = t2*t3
        X3 = X3-t0
        Z3 = t2*t1
        Z3 = Z3+Z3
        Z3 = Z3+Z3
  

• Cost: 6M + 5S + 1^³ + 1*a + 4add + 1*2 + 1*3 + 1*4 + 3*8.
• Source: 1998 Cohen–Miyaji–Ono "Efficient elliptic curve exponentiation using mixed coordinates", formula (4).
• Explicit formulas:

        w = a*Z1^2+3*X1^2
        s = Y1*Z1
        B = X1*Y1*s
        h = w^2-8*B
        X3 = 2*h*s
        Y3 = w*(4*B-h)-8*Y1^2*s^2
        Z3 = 8*s^3
  

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