We know that using FFT we can compute multiplication of an $a$ bit number with a $b$ bit number in $(a+b)^{1+\epsilon}$ time.My question is supposing we want to compute $A\bmod B$ where $A$ is an $a=f(b)$ bit number for some linear function of $b$ with $B$ a $b$ bit number, what is the time and space complexity of such an operation? Could it be done in fully linear ($O(a+b)$) time and space complexity (at least assuming $B$ is fixed per $b$ bits and $A$ is input)? I have been unable to find such a reference or procedure for this operation even when $B$ is fixed (which is the case useful in operations such as Diffie Hellman key exchange).
Bit complexity of modulo operations?
cc.complexity theory;ds.algorithms