Solving a system of inequalities in modulo N I have a problem that boils down to two unknowns,

doturitip9

doturitip9

Answered question

2022-07-01

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 M + A mod N = X 2
And:
X 1 < L 1 mod N
X 2 < L 2 mod N

Answer & Explanation

lywiau63

lywiau63

Beginner2022-07-02Added 13 answers

Why don't you try the Extended Euclidean algorithm to solve 1. X 2 M . X 1 = ( A mod N )?
This will give you the principal solution ( X 1 , X 2 ). You can then write the general solution for ( X 1 , X 2 ) parametrized on an integer n. This will be a linear equation in n for ( X 1 , X 2 ).
You can then apply your inequality constraints,
X 1 < ( L 1 mod N )
X 2 < ( L 2 mod N )
and obtain the value of n that meets those constraints.
Here's a closed form expression for n:
1. X 2 M . X 1 = ( A mod N )
Set X 1 = n , n Z. The general solution becomes ( X 1 , X 2 ) = ( n , ( A mod N ) + M . n )
Apply the constraints:
X 1 < ( L 1 mod N ) n < ( L 1 mod N )
This gives an upper bound for n.
X 2 < ( L 2 mod N ) ( A mod N ) + M . n < ( L 2 mod N )
n < ( L 2 mod N ) ( A mod N ) M
n < m i n ( L 1 mod N , ( L 2 mod N ) ( A mod N ) M )
Joel French

Joel French

Beginner2022-07-03Added 10 answers

Try X 1 = 0). If it results in X 2 L 2 then calculate D = ( N X 2 ) / M .
Try X 1 + D mod 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.

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?