"Fuzzy" Chinese Remainder Theorem I have some "fuzzy" congruences like these:
\begin{align} \\ x&amp;\equiv a_1 \mod 3 \text{ with } a_1 \in \{0,1\},\\ x&amp;\equiv a_2\mod 5 \text{ with } a_2 \in \{2,3,4\},\\x&amp;\equiv a_3 \mod 7 \text{ with } a_3 \in \{5,6\}\\ \end{align}
These example moduli would provide a unique solution for $x \mod lcm(3,5,7)$, if the $a_i$ were fixed. 
Because the $a_i$ are not fixed, these "fuzzy" congruences lead to $2*3*2=12$ possible solutions for $x \mod lcm(3,5,7)$.

To reduce the number of possible solutions for $x$, there exists an additional condition, which provides an upper bound for $x$. For example:
\begin{align} x \mod lcm(3*5*7) &amp;&lt; 5 \end{align}

We can assume that all moduli $m_i$ are primes, f.e. $lcm(m_1,m_2,...) = \prod_i m_i$. 
Furthermore each $a_i$ has at most $t$ possible values ($t=3$ in the upper example). Additionally, the possible values of $a_i$ are consecutive ($a_2 \in \{1,3,4\}$ is not allowed).
So the generic equations look like:
\begin{align} x&amp;\equiv a_i \mod m_i &amp;\text{ with } a_i \in U_i \text{ and } U_i \subset \{0,1,...,m_i-1\} \wedge |U_i| = t \wedge \\&amp;&amp;\forall i,j: |i-j|=1 \Rightarrow |U_i[i]-U_i[j]| = 1
\\ x \mod \prod_i m_i &amp;&lt; k \end{align}

Is it partical feasible to calculate one solution for parameters like $\prod_i m_i \approx 10^{1000}$, all $m_i &lt; 100000$, $k \approx 10^{50}$ and $t \approx 50$?

I tried to use the Chinese Remainder Theorem Method to find a solution for x:

Set $M_i:=lcm(m_1,m_2,...)/m_i$. It holds $gcd(M_i,m_i)=1$. 

Hence, we can use the Extended Euclidean algorithm to find 2 Integers $r_i$ und $s_i$, which fulfill $r_i \cdot m_i + s_i \cdot M_i = 1$.

Set $e_i:=s_i \cdot M_i$, then \begin{align} e_i &amp;\equiv 1 \mod m_i \\ e_i &amp;\equiv 0 \mod m_j, j \neq i\end{align}.

The number $x:=\sum_{i=1}^n a_i \cdot e_i \mod lcm(m_1,m_2,...)$ is a solution.

Now i tried to solve $(\sum_{i=1}^n a_i \cdot e_i \mod \prod_i m_i) &lt; k$ with $minValue(U_i) &lt;= a_i &lt;= maxValue(U_i)$.

These equations can be formulated as an Integer Programming instance (add an additional variable for the mod Operation). I tried to use mathematica to solve these, but it seems unfeasible even for "small" parameters like $\prod_i m_i \approx 10^{50}$, all $m_i &lt; 1000$, $k \approx 10^{2}$ and $t = 3$.

Is there a more efficent way to solve this?
This problem can be approached with the Coppersmith method. For details, see my answer at MO to a similar question.