2
$\begingroup$

When exchanging a public key I usually receive some compressed form of X,Y coordinates. To use some speed ups I'd need to represent that in the Jacobean x,y,z form.

Z=1 satisfies everything and looking at the speed ups (https://en.wikibooks.org/wiki/Cryptography/Prime_Curve/Jacobian_Coordinates, http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html) I don't see an obvious reason why Z=1 would be slower (or faster?) than any other Z, is this a legitimate question? Can you point me in some direction about "does it even make sense to look for Z other than 1?".

$\endgroup$
3
  • 1
    $\begingroup$ Isn't it clear? $Z^4$ that is 1 when $Z=1$ and for the other cases one need 3 doublings. $\endgroup$
    – kelalaka
    Feb 8, 2022 at 17:18
  • $\begingroup$ thanks for the quick answer, when I do a multiplication of a point for a large number I'll do a bunch of additions, doubling, tripling, etc, and I was wondering if choosing a different z would have an impact. I'm not sure it makes sense as a question thought thanks again for the patience. $\endgroup$
    – T. Rossi
    Feb 8, 2022 at 17:40
  • 1
    $\begingroup$ In scalar multiplication, a point is added, again and again (double-and-add), there is no fixed point there. $\endgroup$
    – kelalaka
    Feb 8, 2022 at 17:43

1 Answer 1

2
$\begingroup$

The point doubling (Wiki link) requires Z^4 and when used with the double-and-add algorithm (needed for public point calculation, ECDH, and EC-based signatures) using $Z=1$ simplifies the calculation of Z^4 otherwise one may need 3 doublings. The double-and-add method where the res is not fixed to save time. Double-and-add Wikipedia version;

let bits = bit_representation(s) # the vector of bits (from MSB to LSB) representing s
let res = O # point at infinity
for bit in bits:
    res = res + res # double
    if bit == 1:            
        res = res + P # add
    i = i - 1
return res

This is the beginning of the long story. The "m-fold double" (repeated doubling) calculates $[2^m]P$ and only calculates Z^4 once. When you need $[k]P$, you may need to represent $k$ in the binary form then use m-fold doubling when necessary. To have benefited from this, one has to calculate the cost before deciding to use m-fold double or not.

The answer is not easy and complete, since this one requires Z1=Z2 with 5M + 2S for addition Wiki version has 12M + 4S cost. The 5M + 2S has still Z1 multiplication and if Z1=1 that has zero cost.

In a short sentence, in general, Z1=1 simplifies the equations.

Since $(X_1:Y_1:Z_1)$ represents $(Z/Z^2,Y/Z^3)$ and $(X_1:Y_1:Z_1)$ is an equivalance relation that is $$(X_1:Y_1:Z_1) \sim (\lambda X_1:\lambda Y_1:\lambda Z_1)$$ one can simple convert the $Z_1 =1$ with $$(X_1/Z_1:Y_1/Z_1:1)$$

Keep in mind that 1/Z1 is not division, rather the inverse of Z1 on the defining field.

The Z1 on the other hand, is not staying there with Z1=1 under the operations. To benefit from this, one has to find the inverse and execute two multiplication. Finding inverse, on the other hand, is what we don't want since it is costly.

So, at least there is a benefit at the beginning of scalar multiplication.

$\endgroup$
2
  • $\begingroup$ Thank you very much!! $\endgroup$
    – T. Rossi
    Feb 8, 2022 at 21:52
  • $\begingroup$ Far from a perfect answer, though.... $\endgroup$
    – kelalaka
    Feb 8, 2022 at 21:53

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.