# Time Complexity of Modular Multiplication

I was reading a paper about the Miller-Rabin primality test and I came across the statement that the time-complexity of a modular multiplication is equivalent to $$\mathcal{O}((logN)^2)$$ using the naive algorithm for multiplication ( for common multiplication $$\mathcal{O}(N^2)$$). I am getting intuitively that multiplying a number modulo $$N$$ would be less computationally expensive however I can't seem to find a formal way to prove it. Do you have any ideas?

• It might be useful to give a reference to the paper you were reading if it is publicly available. Commented Jun 11, 2022 at 22:00
• Yes, sorry here is the link: cs.cornell.edu/courses/cs4820/2019sp/handouts/MillerRabin.pdf Commented Jun 12, 2022 at 6:02
• The relevant bit in inside Remark 17, at the bottom of page 9. Commented Jun 12, 2022 at 15:50
• My main problem with that remark is that it says that the operation is repeated s <= log_2N so the Miller-Rabin algorithm is O((logN)2). But in the case s = log_2N then would'it be O((logN)4) ? Commented Jun 12, 2022 at 16:08

Naive multiplication (in both cases) requires time (and space) at most "the square of the number of bits in the representation". Numbers modulo $$N$$ can be represented using about $$\log_2(N)$$ bits. Numbers with $$N$$ bits can be represented with, well, $$N$$ bits.
• A natural number $k$, when written in the usual way in binary, requires $\log_2(k)$ bits to write down (with a special case for $k = 0$, taking a ceiling when $k$ is not a power of two, and adding one when $k$ is a power of two). If we are performing arithmetic modulo $N$, then we can work with the representatives $0, 1, 2, \ldots, N - 1$. By the first sentence, each of these requires at most $\log_2(N)$ bits to write down. Commented Jun 12, 2022 at 15:34