Solving a system of inequalities in modulo N

Question

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

Answer 1

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.

Answer 2

Why don't you try the Extended Euclidean algorithm to solve $1.X2 - M.X1 = (A \mod N)$?

This will give you the principal solution $(X1, X2)$. You can then write the general solution for $X1, X2)$ parametrized on an integer $n$. This will be a linear equation in $n$ for $X1, X2$.

You can then apply your inequality constraints,

$X1 < (L1 \mod N)$

$X2 < (L2 \mod N)$

and obtain the value of $n$ that meets those constraints.

---

Here's a closed form expression for $n$:

$1.X2 - M.X1 = (A \mod N)$

Set $X1 = n, n \in Z$. The general solution becomes $(X1,X2) = (n, (A \mod N) + M.n)$

Apply the constraints:

$X1 < (L1 \mod N) \implies n < (L1 \mod N)$

This gives an upper bound for $n$.

$X2 < (L2 \mod N) \implies (A \mod N) + M.n < (L2 \mod N)$

$n < { (L2 \mod N) - (A \mod N) \over M }$

$\therefore n < min(L1 \mod N, { (L2 \mod N) - (A \mod N) \over M })$