I am writing a paper on RSA, and I am calculating some encryption running times.

I have been told that the encryption running time is $O(n^2)$ where $n$ is the modulus. I have also been told that there is a constant $C$ such that $O(Cn^2)$ where $C$ relates to the machine used.

Does anyone have any idea where to find this $C$ for a certain computer?

  • $\begingroup$ Ok, but will the little-o notation give me the running time for RSA encryption? I am trying to find an upper bound for the public key exponent, so I decided on a max. time - the other factor is how quickly my computer can handle the computations (right?). $\endgroup$ Nov 10, 2015 at 13:10
  • 1
    $\begingroup$ You seem to confuse public exponent ($e$) and public modulus ($N$, with $n$ the number of bits in $N$); and have trouble putting Big-O notation to practical use. This answer might help for both. The software running on your computer matters more than your computer does. $\endgroup$
    – fgrieu
    Nov 10, 2015 at 13:27
  • $\begingroup$ I am not confusing them. But if I set an upper bound for N, I am effectively setting an upper bound for e because e cannot be greater that the totient of N. Thank you for your answer. $\endgroup$ Nov 10, 2015 at 13:57
  • 4
    $\begingroup$ @Mathematica Just benchmark different key sizes. $\endgroup$ Nov 10, 2015 at 14:29
  • 2
    $\begingroup$ By definition $O(n^2) = O(Cn^2)$ for any constant $C$ so the notation is at least not quite right. $\endgroup$
    – otus
    Nov 10, 2015 at 16:42

1 Answer 1


You don't seem to understand what complexity means. $O(Cn^2) = O(n^2)$, so “finding $C$” is not a valid question – any positive $C$ will do.

I recommend looking up some basic complexity theory introduction. There are many introductory books on the subject which can help you understand what this means.


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.