-2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.