9
$\begingroup$

I couldn't find this explained in another question, but is there an actual reason as to why Jacobian coordinates are used for elliptic curves? Do they provide some sort of advantage in terms of performance? Or are they easier to use for security proofs?

$\endgroup$
11
$\begingroup$

Point addition in affine coordinates involves the computation of modular inverses for elements of the underlying finite field. Modular inversion can be done with the extended Euclidean algorithm, although its cost is around 100 times the cost of a single addition or multiplication in the finite field.

Point addition in projective and Jacobian coordinates, however, doesn't require to compute any modular inverse. Hence, the cost of adding two elliptic curve points in projective or Jacobian coordinates is much smaller than in affine representation.

The following is the result of a test I've just run for curve secp256k1, where 'a' means number of additions, 's' number of subtractions, and 'm' number of multiplications, and 'i' number of inversions:

## Addition in affine coordinates ##
{'a': 0, 's': 154, 'm': 299, 'i': 149}

## Addition in Jacobian coordinates ##
{'a': 1, 's': 5, 'm': 17, 'i': 0}

These numbers mean that, for this implementation (which is far from optimized, but serves as an example), addition in affine coordinates is approximately 20 times costlier than in Jacobian.

$\endgroup$

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.