2
$\begingroup$

I would think that the time complexity would depend on the exponent, not the number of bits in the modulus. For example, if the exponent were 5, using the "naive" method, we would perform 5 multiplications. Squaring and multiplying would reduce the number of multiplications dependent on the exponent as well. However, I don't see where the number of bits in the modulus comes in to play.

$\endgroup$
1
  • 2
    $\begingroup$ The cost of multiplying numbers depends on the size of those numbers. $\endgroup$ Nov 30 '15 at 10:15
3
$\begingroup$

The number of CPU cycles required to perform each multiplication increases with the size of the modulus $N$, since the operands can be as large as $N$, and also multiplication is followed by reduction modulo $N$.

Depending on what exactly you are analysing, you may sometimes consider $N$ to be constant (e.g., if you are comparing two exponentiation algorithms) and discard it when doing asymptotic complexity analysis, but if $N$ can vary, then certainly a larger $N$ means your computation will take more CPU cycles.

$\endgroup$
1
  • $\begingroup$ Right. Trying to make it even clearer: time complexity is about the number of operations that a CPU performs, not the number of mathematical operations on variables performed. The two things are proportional (and within a small factor) when we deal with floating point operations or small integers fitting one or two words; but the width of large integers comes into play. $\endgroup$
    – fgrieu
    Nov 30 '15 at 12:43
1
$\begingroup$

In RSA encryption(decryption) we use the binary exponential method. In this method, you should first compute the binary form of $e$. Let $\ell$ be the number of bits in $e$, and let $e_i$ denote the $i$-th bit of $e$, so that $e=\sum\limits_{i=0}^\ell e_i \cdot 2^i$.

Now, with below algorithm, you can compute $c=m^e \bmod n$:

$z:=1$
$\text{for } i:= \ell \text{ down to } 0 \text{ do:}$
$\quad z:=z^2 \bmod n$
$\quad \text{if } e_i = 1 \text{ then } z:=(z \cdot m) \bmod n$
$\text{end for}$
$\text{return } z$

Now suppose $n$ be the $k$ bit number and $0\leq m_1,m_2\leq n-1$. We know that computational complexity for computing $m_1\cdot m_2 \bmod n$ is $O(k^2)$. So computational complexity of encryption is $O(\ell k^2)$.

This show that speed of encryption or decryption depend on bit size of $n$ much more than $e$ or $d$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy