This seems like a question that should have an easy answer, but I don't have a definitive one:

If I have two $n$ bit numbers $a, p$, what is the complexity of computing $a\bmod p$ ?

Merely dividing $a$ by $p$ would take time $O(M(n))$ where $M(n)$ is the complexity of multiplication. But can $\bmod$ be performed slightly faster ?

  • 1
    $\begingroup$ Maybe a dumb question, but can you convert $a$ to be written in base $p$ and then look at the LSB? $\endgroup$ – Pål GD Jun 27 '13 at 20:45
  • 2
    $\begingroup$ You could, but that seems like extra work, and would probably require division. $\endgroup$ – Suresh Jun 28 '13 at 0:33

Shoup (Section 3.3.5, Theorem 3.3, p. 62) gives a bound for computing the residue $r$ in time $O(n\log q)$ where $a = q\cdot p +r$ and $\log a = n$.

I guess that if $p$ and $a$ are both roughly $n$ bit numbers, then $q$ (and hence $\log q$) should be rather small, giving $O(n)$.

If $a$ is an $n$-bit number, and $p$ is relatively small, then the multiplication approach should be faster.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.