7
$\begingroup$

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!

The code

$\endgroup$

1 Answer 1

4
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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). $\endgroup$ Aug 4, 2017 at 11:13
  • $\begingroup$ 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 $\endgroup$
    – Slade
    Aug 4, 2017 at 16:12
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 4, 2017 at 17:49
  • $\begingroup$ 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. $\endgroup$
    – Avv
    Apr 9, 2021 at 6:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .