SECP256K1 Jacobian algorithms

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')


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

Looks like you found those algorithms here?

I found out the point at infinity is (0, 1, 0), even I am not sure if this is correct.

Yes, you are incorrect about the point at infinity in Jacobian coordinates, which is $\infty = (1:1:0)$. See the answer here for more about that. If $P_1 = -P_2$, you have $P_1 + P_2 = \infty$.

I would highly recommend getting your formulas from the Explicit-Formulas Database in the future, or at least using it as a cross-check. They do a great job sourcing where their algorithms come from.

• Yes, you are right about the location where I found it. Thank you, I did not know that there is such a website :) I will have a look. May 26, 2017 at 9:13
• When I want to double a point, how do I check if it is the point at infinity? Would I check if X and Y are 1 and Z equals 0? May 26, 2017 at 9:22
• Yes, but just keep in mind that you are choosing a particular representation of $\infty$. From the link I posted, you can represent $\infty = (t^2:t^3:0),t \neq 0$. I don't have experience with Bitcoin calculations, but that's what I would do to start.
– user47922
May 26, 2017 at 16:00