Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am facing this problem in calculating the order of a process which involves ECC point addition: $P+Q$ , scalar multiplication: $aP$, and selecting random points in the group. The group is of prime order say $q$.

What is the time complexity order of these operations? Is it $O(n)$, $O(log(n))$ or something different?

share|improve this question
I notice that there is no question in this post. $\;$ – Ricky Demer Apr 23 '14 at 12:41
Are you wondering about order of operations in elliptic curves? – mikeazo Apr 23 '14 at 13:31
Yes. I want to know the complexity order of these operations like for eg O(n) ,O(log(n)) etc – Prasanth Apr 25 '14 at 3:49
@Prasanth where $n$ is? The size of the underlying field? – mikeazo Apr 25 '14 at 12:32

It depends on the multiplication algorithm used. Let $n$ be the bit size of the finite field used, and let $O(n^k)$ be the complexity of the multiplication algorithm used (e.g. $k=2$ for schoolbook multiplication, or $k=1.585$ for Karatsuba multiplication). Then:

  • Point addition: $O(n^k)$ (a constant number of multiplications)
  • Scalar multiplication: $O(n^{k+1})$
  • Selecting random point: depends on the method, but usually the same as scalar multiplication.

As pointed out by poncho, the point addition (and the scalar multiplication) can require a multiplication inverse, whose complexity again depends on the algorithm and may be larger than the complexity of multiplication. For example, binary euclidean takes $O(n^2)$, Fermat's little theorem takes $O(n^{k+1})$.

share|improve this answer
Actually, it is considerably more complex than that. For example, if you're adding two points in homologous format, and want the result in homologous format, there's a multiplicative inverse involved, and that's more expensive than all the rest of the operations combined. – poncho Apr 25 '14 at 13:24
@poncho you're right, I've edited the answer. – Conrado PLG Apr 25 '14 at 13:36

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.