I have the following equation:
$$((a w_i + b) \text{ mod } p) \text{ mod } q = ((2({{a w_{i-1} + b}}) - at_{i-1} \cdot 2^{m} + at_{i+m-1} -b) \text{ mod } p) \text{ mod } q$$
Where:
- $\text{mod}$ is the binary operator that returns the remainder of integer division, equivalent to
%in computer programming - $p$ and $q$ are primes with $p > q$
- $a \neq 0$ and $b$ are integers in $\{0, ..., p-1\}$
- $t$ is a number in base 2 represented as a sequence in $\{0, 1\}^*$
- $w_i = t[i, ..., i+m-1]$ is a subsequence of $t$.
I want to rewrite the right hand side of the above equation as a function of $$((aw_{i-1} + b)\text{ mod } p) \text{ mod }q$$ in such a way that the function can be computed in constant time. For example, something of the form:
$$((a w_i + b) \text{ mod } p) \text{ mod } q = (\boxed{((aw_{i-1} + b)\text{ mod } p) \text{ mod } q} + [...]) \text{ mod } p) \text{ mod } q$$ or $$((a w_i + b) \text{ mod } p) \text{ mod } q = \boxed{((aw_{i-1} + b)\text{ mod } p) \text{ mod } q} + [...]$$ or $$((a w_i + b) \text{ mod } p) \text{ mod } q = \boxed{((aw_{i-1} + b)\text{ mod } p) \text{ mod } q} \cdot [...] + [...]$$
Would be ok. I've made some attempts, but I can't come up with any transformation that does work.
Note: as mentioned in a response to a (now apparently deleted) comment, instead of seeing the result of $a \mod p$ as a modulo class $[a]_p \in \mathbb Z / p\mathbb Z$, in this context you should consider it an integer, given by the representative of the equivalence class, in $\{0, ..., p-1\}$. Think of it as $\text{mod} : \mathbb Z \times \mathbb Z \to \mathbb N$.