1
$\begingroup$

I'm trying to understand the cost of operation in elliptic curve (only Weierstrass curve for simplicity) from Wikipedia and there seems to be lack of online information/papers regarding this. I understand the concepts of EC, EDSA, point addition, multiplication, inverse and doubling.

My question is: what does the values of the table represent?

Why aren't the units in seconds?

Why does ADD have more operation, I thought they were the "cheapest"?

If someone could provide a sort of overview, it would be much appreciated.

Improve this question
$\endgroup$
2
  • $\begingroup$ I think the linked table counts elementary operations in the underlying finite field; but I'm unsure if there's a distinction made between addition, multiplication, inversion, hence the present comment is not an answer. I find it intuitively normal that doubling is cheaper than addition: there's less input; also points doubling amounts to addition with self, and the two points added being equal is a special case that allows a shortcut. $\endgroup$
    – fgrieu ♦
    Jan 18 '17 at 14:06
  • 1
    $\begingroup$ @fgrieu: actually, the text above the linked above states that they are counting field multiplication and squarings (both as a cost of 1), inversions (as a cost of 100; obviously, none of the listed operations require an inversion), and everything else (including multiplication by a constant) as free. $\endgroup$
    – poncho
    Jan 18 '17 at 14:26
4
$\begingroup$

Per poncho's comment: the values given in the linked table are the number of multiplication or squaring operations in the finite field on which the Elliptic Curve is defined (which could for example be $\mathbb Z_p$ for some prime $p$); the cost of other operations in this field is either ignored as marginal (addition, subtraction, multiplication by a small integer constant) or absent (field inversion, which if present would account for 100).

The units are not in second, because counting field operations allows independence from both the speed of the hardware used, and the size parameter of the field (like $p$), which would influence the result in second. Know the duration of multiplication in your field using your device, multiply by the integer in the table, and you have some approximation of the duration for a sequential implementation.

ADD usually has more operations than DBL, because point addition on an Elliptic Curve usually turns out to be more computationally intensive than point doubling (as pointed by CurveEnthusiast in comment, that's not absolute): the later can be viewed as a special case of the former where the two inputs are equal, which allows a shortcut (or rather, requires it). As a crude analogy, it is slightly harder to compute $124865+138747$ than it is to compute $2\cdot124865$; for a start, there's more input.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Note that ADD is not inherently slower (although it usually is). In affine short Weierstrass the ADD is cheaper than DBL. $\endgroup$
    – CurveEnthusiast
    Jan 18 '17 at 20:22

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.