-2
$\begingroup$

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?

$\endgroup$
5
  • $\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$ – Mathematica Nov 10 '15 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 '15 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$ – Mathematica Nov 10 '15 at 13:57
  • 4
    $\begingroup$ @Mathematica Just benchmark different key sizes. $\endgroup$ – CodesInChaos Nov 10 '15 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 '15 at 16:42
4
$\begingroup$

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.

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