# How to calculate complexity of ElGamal cryptosystem?

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

• Your time complexity assumptions are correct for this algorithm, and space complexity is $O(1)$ in the number of variables or $O(n)$ if you consider the length of the numbers. However, the algorithm can be achieved faster, because of what poncho wrote in his answer. Basically, it is like calculating $a \cdot b$ as $a+a+a...+a$ with $b$ summands.
– tylo
Jul 21, 2014 at 15:42

• 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$.