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 ?
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.
