# 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. $\;$ – 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})$.

-
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