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

  • 5
    $\begingroup$ When $B$ is fixed, $A\bmod B$ is computable by a finite automaton, hence in space $O(1)$ and time $O(a)$. $\endgroup$ – Emil Jeřábek Aug 4 '15 at 11:29
  • $\begingroup$ Interesting, could you please describe the algorithm? Also is this what is used in crypto? $\endgroup$ – T.... Aug 4 '15 at 11:30
  • $\begingroup$ If I understand Emil's suggestion correctly, then it uses space $\: \Theta \hspace{.02 in}(b) \:$ and time $\: \Theta \hspace{.02 in}(a\hspace{-0.04 in}\cdot \hspace{-0.04 in}b) \;$. $\hspace{.68 in}$ ($\hspace{.02 in}$When $B$ is fixed, that gives what he wrote.) $\;\;\;\;$ $\endgroup$ – user6973 Aug 4 '15 at 16:23
  • 1
    $\begingroup$ @EmilJeřábek corrected the question ($B$ is fixed per $b$ bits). $\endgroup$ – T.... Aug 5 '15 at 7:50
  • 2
    $\begingroup$ Perhaps he would be OK with a preprocessing model: you give me a $b$-bit $B$. I run some algorithm for $poly(B)$ steps, creating some data structure of $O(B)$ size. Finally you give me any $A$ of $O(B)$ bits and I can compute $A ~mod~ B$ in $O(B)$ time, using the data stucture. $\endgroup$ – Ryan Williams Aug 22 '15 at 15:45

Your Answer

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

Browse other questions tagged or ask your own question.