# RSA Time Complexity on Best Case, Average Case and Worst Case

I am currently learning the work arounds about RSA algorithm. I wanted to know the time complexity of the encryption part and decryption part on Best Case, Average Case and Worst Case.

Im new in analysis of algorithms that's why Im having a hard time analyzing algorithms. Explaning it to me step by step will be great or if anyone knows a reliable published paper that explains the time complexity of this algorithm. Can you please give me the link so that I can study it by myself. Thank you and have a blessed day.

## 1 Answer

There's no precise time complexity of RSA, only time complexity of RSA implementations, because various implementation have significantly different complexities (even asymptotic). And it is unusual to worry about best/average/worst case for a given implementation, because (for a given size of parameters) the time varies little, typically much less than from an implementation to the other.

Asymptotic time complexity for an implementation of RSA using elementary algorithms, commonly used in practice, is $O(n^3)$ for private key use (signature generation, and decryption) and $O(n^2)$ for public-key use (signature verification, and encryption), where the public modulus $N$ has $n$ bits (that's the customary metric for key size), and public exponent $e$ has a fixed size, e.g. $e=2^{(2^4)}+1=65537$ ($F_4$) as customary. For the derivation and more, see this answer.