I need someone help me about . how can compute time complexity for this algorithm (Menezes-Vanstone Elliptic Curve Cryptography). I have spent much time reading journals and papers but as yet have been unable to find any record of that performance complexity. It is known that the algorithm is encryption function is :

$C1 = k1 * m1$ mod p

$C2 = k2 * m2$ mod p

The decryption function is:

$m1 = C1 * k1^ {-1}$ mod p.

$m2 = C2 * k2^{ -1}$ mod p.

I think the encryption function it take $O(N)^{2}$

where $T(C1) = O(\log n)^2$ bit operations.

$T(C2) = O(\log n)^2$ bit operations.

and the decryption function it take $O(N)^{3}$. where

$T(m1) = O(\log n)^2 + T(k1^{-1})$.

$T(k1^{-1}) = O(\log n)^3$, by extend Euclid’s method.

$T(m1) = O(\log n)^2 + O(\log n)^3$ bit operations.

$T(m2) = O(\log n)^2 + O(\log n)^3$ bit operations.

Is that true?.

  • 1
    $\begingroup$ Your proposed running times don't make any sense, because you haven't defined $N$ or $n$. Want to try again? $\endgroup$ – D.W. Dec 1 '14 at 7:20

Your bounds seem to be correct, assuming $n$ is the length of $p$, though writing $T(C1) = O(\log n)^2$ is wrong on two counts. First, it should be $O(\log^2 n)$ or $O((\log n)^2$) on the right. While $O(\log n)^2$ has the same meaning, it's not a "closed form", rather like writing $O(\sum_{k=1}^n k)$ instead of $O(n^2)$. Second, $T(C1)$ looks like $C1$ is some parameter like the input length or the number of vertices, whereas you intended $T(C1)$ to be the time needed to compute $C1$. Better notation would be $T_{C1}$, say, and you could include the input length $n$ as a parameter.

Moreover, note that there are faster integer multiplication algorithms, and some of them are used in practice in cryptographic contexts (not necessarily the ones which are asymptotically best). So you can get even better bounds on the running time depending on the implementation.

The reason you couldn't find the time complexity is that the algorithms use a constant number of two very common operations, namely multiplication and inverse modulo $p$, so the running times can be read immediately by experienced practitioners. This is even the case with more complicated operations such as modular exponentiation.

| cite | improve this answer | |

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.