How to calculate complexity of ElGamal cryptosystem?

Question

How to calculate time and space complexity of ElGamal encryption and decryption as there are two exponentiation operation during encryption and one during decryption? Here is my code for encryption:

for i=1:d 
    pow=pow*g;
    y=pow%p;
for j=1:r
    pow1=pow1*g;
    C1=pow1*g;
    pow2=pow2*y;
    C2=(M*pow2)%p;

I think the first for loop will execute $O(d)$ times and second for loop will execute $O(r)$ so total time complexity of this is $O(d)+O(r)$ as it is not known which is bigger among $r$ and $d$.

Answer 1

Well, there are some major problems with your code. Technically, the time estimate of your code is correct (that is, if you insert modulo operations when you update pow1 and pow2), however no one would actually use that algorithm to do ElGamal.

Lets hit some of the issues:

• You use an $O(N)$ algorithm to compute $x^N$; in real usage, exponents are huge (perhaps around $2^{256}$), and an algorithm that takes $O(2^{256})$ iterations is utterly infeasible. In practice, we use an algorithm that performs in $O(\log N)$ operations (modular multiplications), such as this one; this reduces the amount of work to something that can be implemented in practice.

• On the less drastic, but still real issue: your code appears to assume that you have the private key $d$ when doing encryption; in practice, you'll start with the public key (which I believe in your code is $y$.

• Also, while I'm listing nits, you also need to perform a modular reduction when you compute C1 as well. Furthermore, you don't need to recompute C1 and C2 in the loop; you're interesting only in the final values, and so you can compute those after you have the final values of pow1 and pow2.

I'm sure there are other issues I missed. However, the bottom line is that if you really want to compute the time complexity of ElGamal, you need to use the algorithm that we actually implement in practice.