3
$\begingroup$

There are several algorithms for efficient scalar multiplication of an arbitrary point P(x,y) by some positive integer k in elliptic curves defined over $F_{p}$ or $F_{2^{m}}$.

The scalar multiplication deals with point doubling (adding P(x,y) to itself) and point addition(adding two different points (P(x,y), Q(X,Y)). These point doubling and additions, fundamentally, further deal with additions, squaring, multiplications and inversion operations.

My question here is that though there are considerable addition and squaring operations involved in scalar point multiplication, ( for example, a single point addition requires 8 additions, 1 squaring, two multiplications and one inversion ) why is the inversion multiplication ratio (I/M) is of special interest for researchers in performance evaluation of different algorithms for scalar point multiplication ?

I do understand that the inversion and multiplication operations are dominant in elliptic curve arithmetic, but aren't these addition and squaring operations, not dominant enough to be considered ?

I would encourage the readers to go through the table 3.13, page no. 145 in this book so that you may get a clear idea of my question. Please have a look at the last 2 columns titled "EC operations" and "field operations" in this table.

$\endgroup$
  • 1
    $\begingroup$ I'd expect squaring to be counted as a (fraction of) a multiplication. For example, some papers, I read, counted a squaring as 2/3 of a multiplication. $\endgroup$ – CodesInChaos Mar 13 '16 at 10:58
3
$\begingroup$

When we perform, say, a point addition of two elliptic curve points, we need to work with elements of the field that the elliptic curve is defined over. There are several operations we may need to perform, and the total cost of the point addition is the sum of the cost of all the field operations we need to do (plus some overhead, which is typically pretty small):

  • We may need to add and subtract field elements. There two operations have about the same cost, and so we typically don't distinguish them. They're also quite cheap (compared to the other operations required), so it is quite common to ignore them when coming up with an approximation of the total cost.

  • We may need to multiply two elements. The cost of this operation is often the 'unit' where all other costs are measured against.

  • We may need to square an element. This can be done by just handing the element to the multiply routine; however there are symmetries that we can take advantage of to make this specific operation cheaper. For odd-characteristic fields, this squaring operation will be somewhere between 0.5 and 1 times the cost of a multiply. Different implementations will differ in the precise figure; we try to account for that.

  • We may need to find the multiplicative inverse of an element; that is, given $x$, find the value $y$ such that $xy = 1$, where $1$ is the multiplicative identity. This operation is by far the most expensive operation for just about any representation.

This $I/M$ value tries to capture exactly how expensive an inverse operation is; an $I/M$ value of 8 estimates that an inverse operation is about as expensive as the total of 8 multiplication operations.

We need an estimate here to guide us which mix of operations will run quickest in total. If we have an $I/M$ of 5, then an optimization that replaces one inverse with 6 multiplies is a loss. However, if we have an $I/M$ value of 8; then it is a win.

Now, in my experience, $I/M$ ratios tend to be quite high; a ratio of 8 would be far smaller than what I've seen.

$\endgroup$
  • $\begingroup$ On prime fields, an inversion costs over 100 multiplications, so we rarely use more than one inversion (at the end of a scalar multiplication, converting from projective/extended coordinates to affine coordinates). But I think the ratio is much smaller in binary fields, so trade-offs are more interesting there. $\endgroup$ – CodesInChaos Mar 13 '16 at 19:22
  • $\begingroup$ Thanks, , that helped. I am currently doing my master thesis focusing on efficient scalar multiplication algorithms for binary curves. Like what @Codes said, the ratio(I/M) is very small, typically ranging from 5 to 10 in binary curves. This is very less comparatively, with prime curves. However, i do not understand this line from your answer "We need an estimate here to guide us which mix of operations will run quickest in total." I would like you to elaborate a little on it. Thanks in advance $\endgroup$ – KMK Mar 13 '16 at 21:25
  • $\begingroup$ @KMK: one quick example is to look at the Window TNAF entry (unknown point) from the table they have listed; for I/M=5, the affine version takes the equivalent of 284 multiplications, while the projective is slower (341). However, if I/M=8, then it's the projective which is faster (365 multiplicative equivalents vs 386). Hence, the optimal way of computing it depends on the relative speed of the two operations. BTW: since you're talking about binary (even characteristic) curves, the squaring operation is also quite cheap. $\endgroup$ – poncho Mar 13 '16 at 22:20
  • $\begingroup$ How do projective coordinates (homogeneous or Jacobian) avoid costly inversions? $\endgroup$ – JDong Dec 11 '16 at 20:35
  • 1
    $\begingroup$ @JDong: because we can do point addition/doubling without doing an inversion with projective coordinates. Now, if we need the result in affine coordinates (explicit $x, y$ solution to the curve equation), then we do need to do an inversion to convert back, however if we're doing (say) a point multiplication, we can do all the computations with projective (and convert only at the end) $\endgroup$ – poncho Dec 11 '16 at 21:12

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.