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?

  • 2
    $\begingroup$ I notice that there is no question in this post. $\;$ $\endgroup$ – user991 Apr 23 '14 at 12:41
  • $\begingroup$ Are you wondering about order of operations in elliptic curves? $\endgroup$ – mikeazo Apr 23 '14 at 13:31
  • $\begingroup$ Yes. I want to know the complexity order of these operations like for eg O(n) ,O(log(n)) etc $\endgroup$ – Prasanth Apr 25 '14 at 3:49
  • $\begingroup$ @Prasanth where $n$ is? The size of the underlying field? $\endgroup$ – 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})$.

  • 1
    $\begingroup$ 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. $\endgroup$ – poncho Apr 25 '14 at 13:24
  • $\begingroup$ @poncho you're right, I've edited the answer. $\endgroup$ – Conrado Apr 25 '14 at 13:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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