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

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
0
$\begingroup$

Different implementations might use different methods to generate primes. For example, the following answer discusses how to generate primes faster, but might be more vulnerable... What is “Fast Prime”?

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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