Xrfgtjtk

my first question! I work a lot with numbers (finance) but very much an amateur mathematician - please be gentle. I have the following problem that has come from discussions about cryptography:

Given a set of prime numbers $p_1, p_2,...,p_n$ and sets $S_{p_1},S_{p_2},..., S_{p_n}$ containing a selection of modular residue classes with respect to each prime, find the smallest positive integer $q$ that is congruent to a residue class in each $S_i, i = 1,...,n$.

Example:

$p_1 = 7$, $p_2 = 11$, $p_3 = 13 $

$S_1 = {[0]_7,[1]_7,[6]_7}$

$S_2 = {[1]_{11},[5]_{11},[6]_{11},[10]_{11}}$

$S_3 = {[2]_{13},[5]_{13},[8]_{13},[11]_{13}}$

By the Chinese Remainder Theorem (CRT) there will always be a solution if the $S_i$s are non-empty. A brute force approach is to take all combinations of elements from the $S_i$s, apply the CRT to each one in turn and keep track of the smallest.

For example, if we take the first elements from each of the sets above, we can use CRT to solve the following system of equations for q:
$$
q equiv 0 mod 7 \
q equiv 1 mod 11 \
q equiv 2 mod 13
$$

In this case q = 210.

Repeating this process for all the other combinations, we can establish that the smallest possible q is actually 21 ( $equiv [0]_7 equiv [10]_{11} equiv [8]_{13} $)

Of course, this is fine to do when the number of primes and the size of the $S_i$s is small, but blows up quite quickly if they get larger. I'm interested in establishing whether a better algorithm could do this more efficiently and ultimately what is the complexity of this problem in a computational sense.

Any smart ideas? Literature recommendations or theorems in particular that might point me in the right direction would be most appreciated!

Edit: @Yong Hao Ng gives a good improvement on brute force in his answer below, but I think the problem still blows up subexponentially as the number of primes grows, assuming that the number of residue classes for each prime p is roughly p/2. I'm wondering if that's anyone who can improve on this, or indeed suggest why you can't improve on this!

Edit: serious flaw with previous algorithm. Improved algorithm to cater to sparse solutions, which are more common for large data sets.

Split the primes into $P_1$ and $P_2$ such that the number of residue classes are as close as possible. Let $Q_1,Q_2$ be the product of primes in $P_1$ and $P_2$ respectively.

First we compute the residue classes $R_1$ and $R_2$ of $P_1$ and $P_2$ respectively. We extend $R_1$ to also satisfy $equiv 0pmod{Q_2}$ and call it $S_1$. i.e. each $s_1in S_1$ satisfies
$$
begin{align}
s_1pmod{Q_1} &in R_1\
s_1 &equiv 0 pmod{Q_2}
end{align}
$$
Similarly, we extend $R_2$ to also satisfy $equiv 0 pmod{Q_1}$. So each $s_2in S_2$ satisfies
$$
begin{align}
s_2 &equiv 0 pmod{Q_1}\
s_2 pmod{Q_2} &in R_2
end{align}
$$
Therefore $S_1,S_2$ are CRTs $pmod{Q_1Q_2}$, the full composite.

Now consider all the different sums
$$
m = s_1+s_2 pmod{Q_1Q_2},quad s_1in S_1, s_2in S_2
$$
Taking $pmod {Q_1}$, since $s_2equiv 0 pmod{Q_1}$ we have
$$
m equiv s_1 pmod{Q_1} in R_1
$$
Similarly, taking $pmod{Q_2}$, since $s_1equiv 0 pmod{Q_2}$ we have
$$
m equiv s_2 pmod{Q_2} in R_2
$$
Therefore the $m$ constructed in this way is exactly all the residue classes $pmod{Q_1Q_2}$ of the original problem.

This means it suffices to find the smallest $m pmod{Q_1Q_2}$ possible. Since $0leq s_1,s_2< Q_1Q_2$, this is either the sum of the smallest $s_1$ and $s_2$, or a sum of $s_1,s_2$ is just a bit more than $Q_1Q_2$.

Let $S_1$ and $S_2$ be sorted. To find the smallest for the latter type, we start with the largest $s_1$ and find the smallest $s_2$ such that $s_1+s_2geq Q_1Q_2$. Now we iteratively move to a smaller $s_1$, at each step if the new $s_1$ causes $s_1+s_2< Q_1Q_2$ then we also move $s_2$ to a larger one until $s_1+s_2geq Q_1Q_2$. It can be seen that this traverse $S_1,S_2$ exactly once.

For the overall complexity analysis, suppose for simplicity that $R_1,R_2$ each has $approx m$ classes, so $2m$ CRTs computed. Then the bruteforce method would compute $2m + m^2approx m^2$ CRTs.

This method would require $2m$ CRTs for constructing $S_1$ and $S_2$. It then requires $2m$ (modulo) sums to check for all the $m=s_1+s_2$.

Assuming that CRT is more costly than the modulo sums, the complexity roughly drops from $m^2$ CRTs to $2m$ CRTs.