3
$\begingroup$

I have some "fuzzy" congruences like these: \begin{align} \\ x&\equiv a_1 \mod 3 \text{ with } a_1 \in \{0,1\},\\ x&\equiv a_2\mod 5 \text{ with } a_2 \in \{2,3,4\},\\x&\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) &< 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&\equiv a_i \mod m_i &\text{ with } a_i \in U_i \text{ and } U_i \subset \{0,1,...,m_i-1\} \wedge |U_i| = t \wedge \\&&\forall i,j: |i-j|=1 \Rightarrow |U_i[i]-U_i[j]| = 1 \\ x \mod \prod_i m_i &< k \end{align}

Is it partical feasible to calculate one solution for parameters like $\prod_i m_i \approx 10^{1000}$, all $m_i < 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 &\equiv 1 \mod m_i \\ e_i &\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) < k$ with $minValue(U_i) <= a_i <= 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 < 1000$, $k \approx 10^{2}$ and $t = 3$.

Is there a more efficent way to solve this?

$\endgroup$
  • 2
    $\begingroup$ Without the "consecutive" requirement, the problem is NP-hard. I don't know whether that changes when taking into account the "consecutive" requirement. With this requirement, it seems another way to formulate the problem is: given $b_1,\dots,b_n$ and $m_1,\dots,m_n$ and $c$ and $k$ such that $b_i \le t$ for all $i$, we seek to find $x$ such that $0 \le x < k$ and $x-c \bmod m_i \le b_i$ for each $i$. $\endgroup$ – D.W. Jul 10 '18 at 20:42
  • $\begingroup$ thx for the quick answer! "Without the "consecutive" requirement, the problem is NP-hard.": Could you get me a hint how i can prove this? I tried to develope a reduction-proof with the Integer Programming Problem(ILP), but i don't know how to transform arbitrary ILP-equiations like $\sum_i p_i \cdot v_i < c$ (v_i are the variables and p_i are the const factors) to a “Fuzzy” Chinese Remainder Theorem instance. $\endgroup$ – CRTFan123 Jul 12 '18 at 16:21
  • 1
    $\begingroup$ The proof is too long to list in a comment, but if you want to ask a new question about that version, I will answer it with a detailed reduction. $\endgroup$ – D.W. Jul 12 '18 at 16:39
  • $\begingroup$ I also have a question concerning your reformulation of the problem. I'm not sure what these $b_1,...,b_n$ means and how they will change if we alter for example $a_3 \in \{5,6\}$ to $a_3 \in \{2,3\}$. Could you explain it for me by one of the example congruences in the original question? $\endgroup$ – CRTFan123 Jul 12 '18 at 16:45
0
$\begingroup$

This problem can be approached with the Coppersmith method. For details, see my answer at MO to a similar question.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.