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){
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
        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?



1 Answer 1


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.

  • 1
    $\begingroup$ 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. $\endgroup$
    – Donut
    May 26, 2017 at 9:13
  • $\begingroup$ 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? $\endgroup$
    – Donut
    May 26, 2017 at 9:22
  • $\begingroup$ 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. $\endgroup$
    – user47922
    May 26, 2017 at 16:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.