# Solving a system of inequalities in modulo N

I have a problem that boils down to two unknowns, $X_1$ and $X_2$, where:

$X_1 \cdot M + A\bmod N = X_2$

And:

$X_1 \lt L_1\bmod N$

$X_2 \lt L_2\bmod N$

I can try every possible $X_1 \lt L_1$ until I hit one that produces an $X_2 \lt L_2\bmod N$ and solve one such problem in less than a minute. However, I have thousands of these to solve, so any increase in efficiency will greatly help.

Two questions I found indicate that inequality is meaningless in modulo / congruences. However, in this case, the inequality has a very specific meaning - to limit the range of valid values for $X_1$ and $X_2$. Those questions are:

solving-an-inequality-modulo-1

do-inequations-exist-with-congruences

## 1 Answer

I settled upon this solution:

Try $X_1 = 0$.

If it results in $X_2 \ge L_2$ then calculate $D = \lceil (N - X_2) / M \rceil$.

Try $X_1 + D\bmod M$.

Repeat as needed. This allows me to skip over most values of $X_1$ that will not produce an $X_2$ in the required range.