Skip to main content
Polish
Source Link
fgrieu
  • 145.6k
  • 12
  • 319
  • 611

There's no firmprecise 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, e.g. $e=F_4=2^{(2^4)}+1=65537$$e=2^{(2^4)}+1=65537$ ($F_4$) as customary). For the derivation and more, see this answer.

There's no firm time complexity of RSA, 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, 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=F_4=2^{(2^4)}+1=65537$ as customary). For the derivation and more, see this 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.

Source Link
fgrieu
  • 145.6k
  • 12
  • 319
  • 611

There's no firm time complexity of RSA, 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, 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=F_4=2^{(2^4)}+1=65537$ as customary). For the derivation and more, see this answer.