# Computational Complexity of Modular Exponentiation (from Rosen's Discrete Mathematics)

This is a block of code from Kenneth Rosen's Discrete Mathematics book, for calculating $$b^n \mod m$$, and it says that:

The number of bit operations should be big-O of $$\mathcal{O} \left ( \left (\log(m) \right )^2 \cdot \log(n) \right)$$.

I understand that, there are $$k$$ (which is the length in bits of the binary form of $$n$$) runs of the loop, so that there is a $$\log(n)$$ term, but I don't see where the $$\left (\log(m) \right)^2$$ term is coming from.

It seems like they are saying the two lines of the for loop, each perform a modular division with an integer $$m$$, whose length is $$\log(m)$$, but I am unsure if $$(x \cdot power)$$ and $$(power \cdot power)$$ should be considered the integer $$m$$. Or why they would be multiplied instead of just $$2\log(m)$$?

Thanks for the help!

For $a\times b \equiv \bmod m$ they use a quadratic multiplication / reduction algorithm with a complexity of $O(\log(m)^2)$. Multiply this with the number of loops, i.e. $k=\log(n),$ and you get $O(\log(m)^2 \times \log(n)).$
Note that the square power*poweris computed $k$ times, but x*power only $k/2$ on average (depending on the bit count of $a$).
• Note that for large moduli, there are multiplication algorithms that perform better than the $\Theta({\it length}^2)$ of ordinary long multiplication. (But a textbooks of the headings-in-colored-ink variety probably won't assume knowledge of them). Aug 4, 2017 at 11:13
• I can see where the $log(m)^2$ comes from because the two terms need to be multiplied (and the complexity for that algorithm is $O(n^2)$, but doesn't the $\mod(m)$ operation also have some level of complexity that we need to add? I can't tell where that comes in Aug 4, 2017 at 16:12
• Yes. But normally divison or mod has the same complexity as multiplication, here $O(\log(n)^2),$ and therefore the complexity for one loop is $O(\log(n)^2)+O(\log(n)^2) = O(\log(n)^2),$ for more info see en.wikipedia.org/wiki/…. You can see (as already noted by @henning-makholm) that multiplication and/or division can be implemented better than $O(\log(n)^2),$ e.g. the Karatsuba multiplication with $O(\log(n)^{1.585}).$ Don't be confused by the Wiki table, there n is the bit-size or digit-size not the number itself. Aug 4, 2017 at 17:49
• Thank you. Since multiplication of two integers is $O(n^2)$, then why it's $O(log(m)^2)$? In worst case scenario, we would have 2 miltiplications one for $x \cdot power$ and another for $power \cdot power$, is that correct? I am really not sure why we have $log (n)$ as well.