# Number of operations for Elgamal cryptosystem

In page 408 of Hoffstein, Piper, and Silverman's Introduction to Mathematical Cryptography, it says

"Roughly speaking, in order to achieve $$k$$ bits of security, encryption and decryption for Elgamal, RSA, and ECC, requires $$\mathcal{O}(k^3)$$ operations, while encryption and decryption for lattice-based systems requires only $$\mathcal{O}(k^2)$$ operations".

Why does Elgamal encryption and decryption require $$\mathcal{O}(k^3)$$ operations?

Roughly speaking, in order to achieve $$k$$ bits of security, encryption and decryption for Elgamal, RSA, and ECC, require $$\mathcal{O}(k^3)$$ operations, while encryption and decryption for lattice-based systems require only $$\mathcal{O}(k^2)$$ operations.
That quote uses "$$k$$ bits of security" where there should be "a security parameters of $$k$$ bits" or "key size of $$k$$ bits". In particular, having RSA and ECC together can only mean that a confusion is made between security in bits (that I now note $$b$$) and key size $$k$$. As an aside, the quote uses $$\mathcal{O}$$ where formally there should be $$\Theta$$ or $$\Omega$$, see this for the difference. That's a common, I do it often!
Let's independently derive the cost counted as instructions on standard computers with fixed-width word (as customary), for $$b$$-bit security meaning $$\Theta(2^b)$$ work for an attacker to break the system,
Consider RSA with $$k$$-bit public modulus, and ElGamal as originally formulated, that is the group $$\Bbb Z_p^*$$ with $$p$$ a $$k$$-bit public prime and a generator for all or most of the group. The cost of the private-key operation is dominated by $$\Theta(k)$$ modular multiplications. Each of these has costs $$\Theta(k^2)$$ work using common algorithms, $$\Theta(k^{\approx1.6})$$ for large parameters with Karatsuba, $$\Theta(k^{\approx1.5})$$ for huge parameters with Toom-Cook, $$\Theta(k\log k)$$ in theory only. Ignoring anything better than Toom-Cook, we get $$\Theta(k^3)$$ to $$\Theta(k^{2.5})$$ work. For RSA, subtract $$1$$ from the exponent for public-key use (encryption, signature verification) and fixed public exponent.
The two algorithms considered are vulnerable to GNFS, with heuristic cost $$L_{(2^k)}\left[1/3,\sqrt{64/9}\,\right]$$ in L-notation. Assuming this remains the best attack, and keeping only the first parameter in the interest of simplicity and a little safety margin (from the standpoint of the legitimate user), we have like $$\Theta(k^{1/3})$$-bit security.
At $$b$$-bit security, the work for ElGamal as originally formulated, and RSA signature/decryption, thus comes out roughly as $$\Theta(b^9)$$ to $$\Theta(b^{7.5})$$.