Why inversion and multiplication operations are costly in elliptic curves?

Question

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.

Answer 1

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.