Computational Complexity: ECC multiplication vs Modular multiplication

Question

How does performing scalar multiplication on an elliptic curve compare to exponentiation in a multiplicative group modulo a prime?

I.e. on a given elliptic curve of size $|t|$, what's the complexity of computing $kP$ with respect to $|k|$ and $|t|$?

And in comparison, what's the computational complexity of a modular exponentiation of form $g^a \bmod p$ with respect to $|g|=|p|$ and $|a|$?

It would already be a big help to know the answer for double-and-add and square-and-multiply respectively.

Answer 1

If you only care about computational complexity, it's similar:

• In ECC: the number of double-and-add steps is proportional to $O(|k|)$ (one double every bit, one add for each $1$ bit, in the non-windowed algorithm). Each double/add is a sequence of a constant number of field multiplications, squarings, additions and subtractions. Multiplication and squarings are the expensive ones, and using Karatsuba algorithm, they are $O(|t|^{1.58}$). Therefore the result is $O(|k||t|^{1.58})$.
• Modular exponentiation is the same. Square-and-multiply is $O(|a|)$. Each square/multiply is $O(|p|^{1.58}$). Therefore the result is $O(|a||p|^{1.58}$)

Of course, if you need to be more precise, you'll have to decide on a specific point multiplication / modular exponentiations algorithms, since there are ones that use windows and precomputation tables; and in ECC, also specific formulas for point addition and doubling.