2
$\begingroup$

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?

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

1 Answer 1

Reset to default
2
$\begingroup$

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})$.

Improve this answer
$\endgroup$
4
  • 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
    Commented Apr 25, 2014 at 13:24
  • $\begingroup$ @poncho you're right, I've edited the answer. $\endgroup$
    – Conrado
    Commented Apr 25, 2014 at 13:36
  • $\begingroup$ Can you please elaborate how point addition is polynomial time? $\endgroup$
    – Sabito
    Commented Dec 4, 2020 at 5:45
  • 1
    $\begingroup$ @user134470 point addition is a fixed number of field multiplications, squarings and additions (and inversion, sometimes). Therefore the complexity of addition is the complexity of these field operations (a constant factor won't affect the complexity) $\endgroup$
    – Conrado
    Commented Dec 4, 2020 at 12:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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