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?
Thanks in advance!
I think you may be mixing up the bit-sizes.
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.