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$


$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:




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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.