# Complexity of taking mod

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 ?

• Maybe a dumb question, but can you convert $a$ to be written in base $p$ and then look at the LSB? Commented Jun 27, 2013 at 20:45
• You could, but that seems like extra work, and would probably require division. Commented Jun 28, 2013 at 0:33

## 1 Answer

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.