I am trying to prove that if $p$ is a decimal number having $m$ digits, then $p \bmod q$ can be performed in time $O(m)$ (at least theoretically), if $q$ is a prime number. How do I go about this?
A related question is asked here, but it is w.r.t to MATLAB, but mine is a general one.
The relevant text, that I am referring: chapter 32 -String Matching, PP:991, "Introduction to Algorithms" 3rd edition Cormen et al.
Best Answer
Assuming (as Jesko does) that $q$ is a constant and not part of the input, the usual long-division algorithm you learn at school will do quite nicely. The algorithm is the following:
Compute multiples $q$, $2q$, $3q$, $4q$, $\dots$, $10q$. This takes constant time, as it's independent of $q$.
Say $q$ has $k$ digits. Start with the first $k$ digits of $p$. Call this string $s$.
Compare it against each of the $10$ multiples of $q$; whichever $cq$ is the largest one smaller than $s$, write down $c$ as a digit of answer, subtract $cq$ from $s$, and "bring down" the next digit of $p$. That is, set $s$ to be $(s - cq)$ concatenated with the next digit of $p$.
If $s < q$, then it's your answer, stop. Else, go back to step $3$ and repeat.
Here's an image from Wikipedia, for the example of $q = 37$.