# Asymmetric encryptions' computational complexity [duplicate]

I need to know the computational complexity of the public key encryption (e.g. Paillier), please.

(i.e.Paillier in his paper mentions that the computational complexity of most of public key encryptions is $O(n^3)$, but is not clear to me why)

• Hint: start by establishing that (for arguments of $n$ bits) the cost of the classic multiplication algorithm is $O(n^2)$ for arguments of $n$ bits; extend to $O(n^2)$ for $a\cdot b\bmod N$; then $O(n^3)$ for $x^d\bmod N$. There are faster algorithms, but they are not extremely useful in cryptography because $n$ is at most in the thousands (for RSA) or hundreds (for ECC).
– fgrieu
Dec 7 '14 at 14:25
• @fgrieu I don't get how you conclude $O(n^3)$ from $O(n^2)$. Dec 7 '14 at 14:35
• Using exponentiation by squaring, one needs $\mathcal O(n)$ underlying operations for a $n$-bit exponent. Hence, if the operation is computable in $\mathcal O(n^2)$ steps (which is mostly the case for practical systems, as mentioned above), the total cost is in $\mathcal O(n^3)$. Dec 7 '14 at 14:40
• Many thanks. I found a detailed explanation: crypto.stackexchange.com/questions/6164/… Dec 7 '14 at 15:10