patternMinor
"Fuzzy" Chinese Remainder Theorem
Viewed 0 times
remainderchinesetheoremfuzzy
Problem
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 $232=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(357) &< 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 Program
\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 $232=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(357) &< 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 Program
Solution
This problem can be approached with the Coppersmith method. For details, see my answer at MO to a similar question.
Context
StackExchange Computer Science Q#94122, answer score: 2
Revisions (0)
No revisions yet.