1
$\begingroup$

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!

$\endgroup$
4
  • $\begingroup$ It might be useful to give a reference to the paper you were reading if it is publicly available. $\endgroup$
    – Suzu Hirose
    Commented Jun 11, 2022 at 22:00
  • $\begingroup$ Yes, sorry here is the link: cs.cornell.edu/courses/cs4820/2019sp/handouts/MillerRabin.pdf $\endgroup$
    – Hustler885
    Commented Jun 12, 2022 at 6:02
  • $\begingroup$ The relevant bit in inside Remark 17, at the bottom of page 9. $\endgroup$
    – Sam Nead
    Commented Jun 12, 2022 at 15:50
  • $\begingroup$ 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) ? $\endgroup$
    – Hustler885
    Commented Jun 12, 2022 at 16:08

1 Answer 1

Reset to default
2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thank you, that's what I suspected do you have any references I can read on why they need just log(N) bits? $\endgroup$
    – Hustler885
    Commented Jun 12, 2022 at 6:04
  • $\begingroup$ 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. $\endgroup$
    – Sam Nead
    Commented Jun 12, 2022 at 15:34
  • $\begingroup$ I could not find a reference for this on my shelf. Sorry! $\endgroup$
    – Sam Nead
    Commented Jun 12, 2022 at 15:39

You must log in to answer this question.

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