# ECC Complexity order of point addition, scalar point multiplication and selecting random point

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?

• I notice that there is no question in this post. $\;$ – user991 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})$
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})$.