Algorithm for finding the smallest integer that satisfies several modular congruence conditions?

Question

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!

Answer 1

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 0\pmod{Q_2}$ and call it $S_1$. i.e. each $s_1\in S_1$ satisfies $$ \begin{align} s_1\pmod{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_2\in 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_1\in S_1, s_2\in S_2 $$ Taking $\pmod {Q_1}$, since $s_2\equiv 0 \pmod{Q_1}$ we have $$ m \equiv s_1 \pmod{Q_1} \in R_1 $$ Similarly, taking $\pmod{Q_2}$, since $s_1\equiv 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 $0\leq 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_2\geq 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_2\geq 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^2\approx 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.

Answer 2

In your example, we can rewrite S₁, S₂, and S₃ as follows:

• S₁ = ±3 ±3 _{(mod 7)}
• S₂ = ±2 ±3 _{(mod 11)}
• S₃ = ±3 ±5 _{(mod 13)}

You can verify that this representation results in the same residues for each set, no matter what signs (plus or minus) you choose. You always get back the full residues in each set as your original example.

Next, we can apply Garner's Formula to combine these, and arrive at:

• q = ±91 ±143 ±143 ±231 ±273 ±616 _{(mod 1001)}

You can choose any values for the signs, and the resulting sum, q, will always be a number that satisfies your constraints. In fact, these are all the possible numbers that will satisfy the constraints.

As a random example, we can arbitrarily choose the following signs

• q = +91 +143 -143 +231 -273 -616 _{(mod 1001)}
• q = 434 _{(mod 1001)}
• q = 0 _{(mod 7)}, 5 _{(mod 11)}, 5 _{(mod 13)}

This satisfies all the modular congruences and you can verify that the same will be true for all possible choices of plus/minus signs.

Now, we've reduced the task to choosing the correct signs that will result in the smallest number. This is of course, the optimization version of the partition problem, which is known to be NP-Hard.

However, the Karmarkar–Karp Algorithm is a very fast method to find a partition whose difference is at most 7/6^th that of the optimal partition. It will find a very small number that satisfies the modular congruences, though it may not be the absolute smallest.

The algorithm works by first sorting from largest to smallest, then removing the largest two items, adding their difference back into the list, and repeating until there is only one item left. Running the algorithm, we have the following steps:

• 616, 273, 231, 143, 143, 91
• 343, 231, 143, 143, 91
• 143, 143, 112, 91
• 112, 91, 0
• 21, 0
• 21

In this case, the algorithm found the optimal solution, but this may not always be the case.

To directly answer the question, I don't think there's a fast way to find the absolute smallest number to satisfy the constraints (it's probably NP-Hard). But there is a very fast way to find an approximation.