Computational complexity of RSA What's the computational complexity or RSA? One can assume it's O(prime length^2) it you consider multiplication by column, but speed tests slightly differ on slow operations with private key and differ a lot on public key. Why?

&gt; openssl speed rsa1024 rsa2048 rsa4096

                  sign    verify    sign/s verify/s
rsa 1024 bits 0.002544s 0.000124s    393.1   8049.2
rsa 2048 bits 0.017023s 0.000467s     58.7   2140.7
rsa 4096 bits 0.121189s 0.001824s      8.3    548.2
A more concrete answer for the data observed from OpenSSL:


naive bignum multiplication is $O(n^2)$ and so is modular multiplication (which is what is actually needed here). However OpenSSL (for these sizes) uses Karatsuba multiplication which lowers this to roughly $O(n^{1.6})$ (thanks frgieu) and also Montgomery reduction which is only a constant factor.
for publickey the number of multiplications is fixed (and small) so the total operation is the same big-O as one multiplication.
for privatekey the number of multiplications also scales with $n$ giving a total roughly $O(n^{2.6})$ . OpenSSL also uses CRT which halves the size of the multiplications and doubles their number (plus wrap-up and sanity check), and windowing which reduces the number of multiplications by about 1/3, but those are both constant factors and ignored for big-O.


OpenSSL doesn't 1.1.1 does implement the imprecisely named 'multi-prime' form of PKCS1, which changes the privatekey benefit from CRT, but to get speed results for it you must specify -primes N and a sufficiently large (total) size.