4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • 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 '17 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 '17 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 '17 at 16:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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