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
Operation | Assumptions | Cost | Readdition cost |
---|---|---|---|
addition | Z1=1 and Z2=1 | 5M + 2S | 5M + 2S |
addition | Z2=1 | 9M + 2S | 9M + 2S |
addition | Z2=1 and b3=3*b | 11M + 2*b3 + 3*a | 11M + 2*b3 + 3*a |
addition | b3=3*b | 12M + 2*b3 + 3*a | 12M + 2*b3 + 3*a |
addition | 12M + 2S | 12M + 2S | |
addition | 11M + 6S + 1*a | 11M + 6S + 1*a | |
addition | 12M + 5S + 1*a | 12M + 5S + 1*a | |
addition | 10M + 4S + 1^3 | 10M + 4S + 1^3 | |
addition | 16M + 3S + 3^3 | 16M + 3S + 3^3 | |
doubling | Z1=1 | 3M + 5S | |
doubling | 5M + 6S + 1*a | ||
doubling | 6M + 5S + 1*a | ||
doubling | b3=3*b | 8M + 3S + 2*b3 + 3*a | |
doubling | 6M + 5S + 1^3 + 1*a | ||
scaling | 1I + 2M |
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
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
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
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
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
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
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
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
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
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
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
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
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
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
A = 1/Z1 X3 = A*X1 Y3 = A*Y1 Z3 = 1