# Computational Complexity: ECC multiplication vs Modular multiplication

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|$$?

• Do you have any calculations for double and add or square and multiply? A good starting point would be to find out what the cost of double and add is for addOne co-ordinates and compare that to square and multiply. Then analyse each formulae to see how the cost rises when the respective parameters are increased. For example, how does the double and add formula increase when t increases. – user69644 Jul 10 '19 at 13:41
• Although not mentioned in your question, I’m guessing you may decide to use the method which is the cheapest. If so l, you may want to compare both methods with the same security parameter. – user69644 Jul 10 '19 at 13:44
• How many squarings do you need to calculate $g^(2^t)$? When do you do/what triggers a multiplication in the square-and-multiply algorithm? – j.p. Jul 11 '19 at 6:39
• The security parameter is a good point, although the operations seem to be equally expensive, they will be performed on different sized security parameters for the same security. Thanks for the hint! – Evolir Jul 12 '19 at 9:30

• 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}$$)