Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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
2  
I notice that there is no question in this post. $\;$ –  Ricky Demer Apr 23 at 12:41
    
Are you wondering about order of operations in elliptic curves? –  mikeazo Apr 23 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 at 3:49
    
@Prasanth where $n$ is? The size of the underlying field? –  mikeazo Apr 25 at 12:32
add comment

1 Answer 1

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
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 at 13:24
    
@poncho you're right, I've edited the answer. –  Conrado PLG Apr 25 at 13:36
add comment

Your Answer

 
discard

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.