I am working on a bitcoin related project and I am trying to speedup the ecc calculation. I started with double-and-add and sliding window.
I would like to go move over to the jacobian coordinates. This is what I found out so far:
Point Doubling
if(Y == 0){
return POINT_AT_INFINITY
}
S = 4 * X *Y^2
M = 3 * X^2 + a * Z^4
X'= M^2 - 2 * S
y'= M(S - X') - 8 * Y^4
Z'= 2 * Y * Z
return (X', Y', Z')
Point Addition
U1 = X1 * Z2^2
U2 = X2 * Z1^2
S1 = Y1 * Z2^3
S2 = Y2 * Z1^3
if U1 == U2:
if S1 != S2:
return POINT_AT_INFINITY
else:
return POINT_DOUBLE(X1, Y1, Z1)
H = U2 - U1
R = S2 - S1
X3= R^2 - H^3 - 2 * U1 * H^3
Y3= R * (U1 * H^2 - X3) - S1 * H^3
Z3= H * Z1 * Z2
return (X3, Y3, Z3)
I found out the point at infinity is (0, 1, 0), even I am not sure if this is correct. Since I am not sure about this point, I started to think about the point doubling algorithm. There it checks if Y is 0 and returns the point at infinity. What if the point double algorithm returns the point at infinity and I have to run it again? Y would be 1 in that case and the point doubling algorithm would not detect it.
I know that in affine coordinates this would be a problem but how does it look in Jacobian?
Thanks