ECC: application of multiple multiplicative inverses

Question

I've recently read about "Montgomery trick" on Application of Montgomery's Trick to Scalar Multiplication by Pradeep Kumar Mishra and Palash Sarkar which provides a way to compute several multiplicative inverses at once using this technique:

if x = 1/(ab), then 1/a = xb and 1/b = xa

I've also analyzed various algorithms for computing multiplicative inverse on Modular Inverse Algorithms without Multiplications by Laszlo Hars.

At the top of the page 12 they briefly mention:

Still, in case of elliptic curve cryptography the most straightforward (affine) point representation and implementation of the point addition is the best (the projective, Jacobian and Chudnovsky-Jacobian coordinates are slower, see [8]). T

Of course, projective coordinates usually using delayed inverse, but more multiplications per point addition.

Affine coordinates need less total operations, but inverse is calculated at every point addition instead of once at the end.

As I understand, Montgomery trick can eliminate a computation of inverse at every step.

However, I struggle to understand how to apply this technique.

Let's say I have 4 points in affine coordinates on some weierstrass curve. Affine addition formula requires an inverse of X-coordinate difference between two points. Which means that I can't add all 4 points together with only one inversion.

I could do P1+P2 and P3+P4 with one inversion, but then I need to add P1,2 together with P3,4, which means that another inversion is needed. So at the end it is slower than using projective coordinates, if inverse cost compared to multiplication is high.

I understand how to apply "Mongomery trick" to a case where we calculate a bunch of independent scalar multiplications at once, and then convert all resulting points to affine system using only one inverse. But I don't understand how to use it in a single multiplication which consists of many additions, and if this even possible at all.

Answer 1

Your analysis is pretty much on point. The cost of batch inversion is only justified if we have a computation involving a relatively large number of simultaneous point additions. In a project I work on, we set a threshold of 70 additions based on our benchmarks. Our code is here if you're interested.

To generalize your example a bit, a single summation involving $n$ points could be reduced to one involving $\lceil n/2 \rceil$ points by simultaneously adding pairs of points. So we would need a rather large summation (140 terms in our case), or several simultaneous summations, to justify the cost of inversion. Even then, we would eventually fall back to projective formulas after this reduction shrinks the problem size below our threshold.

In practice, the cost of inversion isn't likely to be justified for single multiplication problems, at least assuming ~256 bit scalars. The affine formulas are quite useful in the multi-scalar setting, though. We use a multi-scalar variant of Yao's method, which involves computing a summation of precomputed points for each digit in $1 \dots 2^w - 1$. Not only are these summations potentially large, they are also independent of one another, so the whole first (and most expensive) phase of the algorithm can be viewed as $2^w - 1$ simultaneous summations.