<p>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.</p>

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

CC BY-SA 3.0
2015-08-04T11:29:22.943Z
When $B$ is fixed, $A\bmod B$ is computable by a finite automaton, hence in space $O(1)$ and time $O(a)$.
Emil Jeřábek
CC BY-SA 3.0
2015-08-04T11:30:35.597Z
Interesting, could you please describe the algorithm? Also is this what is used in crypto?
Turbo
CC BY-SA 3.0
2015-08-05T04:29:55.620Z
@RickyDemer I see then I have not explained well. Hope this explains better.
Turbo
CC BY-SA 3.0
2015-08-05T07:50:16.653Z
@EmilJeřábek corrected the question ($B$ is fixed per $b$ bits).
Turbo
CC BY-SA 3.0
2015-08-18T05:15:16.463Z
I'm a little unclear on what you mean When you say $B$ is fixed per $b$ bits. Here's how I understand what you are saying:

There exists a sequence $B_1, B_2, ...$ where $B_i$ has $i$ bits. There exists a linear function $f$. The problem takes as input integer $A$ with $a$ bits; let $b = f^{-1}(a)$ such that $a = f(b)$. The task is to output $A \mod B_b$. Is that right?

Because if that's what you mean, you could have a problem if the sequence $B_1, B_2, ...$ is not computable.
Mikhail Rudoy
CC BY-SA 3.0
2015-08-22T15:45:36.603Z
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.
Ryan Williams
<cc.complexity-theory><ds.algorithms>
Bit complexity of modulo operations?
Turbo
# Bit complexity of modulo operations?

(Asked by: username_0 on 2015-08-04)

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

**Tags:** cc.complexity-theory, ds.algorithms
> **Comments:**
> **username_1**: When $B$ is fixed, $A\bmod B$ is computable by a finite automaton, hence in space $O(1)$ and time $O(a)$.  
> **username_0**: Interesting, could you please describe the algorithm? Also is this what is used in crypto?  
> **username_0**: @RickyDemer I see then I have not explained well. Hope this explains better.  
> **username_0**: @EmilJeřábek corrected the question ($B$ is fixed per $b$ bits).  
> **username_2**: I'm a little unclear on what you mean When you say $B$ is fixed per $b$ bits. Here's how I understand what you are saying:  There exists a sequence $B_1, B_2, ...$ where $B_i$ has $i$ bits. There exists a linear function $f$. The problem takes as input integer $A$ with $a$ bits; let $b = f^{-1}(a)$ such that $a = f(b)$. The task is to output $A \mod B_b$. Is that right?  Because if that's what you mean, you could have a problem if the sequence $B_1, B_2, ...$ is not computable.  
> **username_3**: 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.  

---

## 0 answers

