Solving a system of inequalities in modulo NI 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 &lt; L 1 mod N X 2 &lt; L 2 mod N

Question

Solving a system of inequalities in modulo NI 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    &amp;lt;      L    1    mod  N      X    2    &amp;lt;      L    2    mod  N

lywiau63 · Accepted Answer

Why don&#039;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  &amp;lt;  (  L  1    mod      N  )  X  2  &amp;lt;  (  L  2    mod      N  )and obtain the value of n that meets those constraints.Here&#039;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  &amp;lt;  (  L  1    mod      N  )    ⟹    n  &amp;lt;  (  L  1    mod      N  )This gives an upper bound for   n.  X  2  &amp;lt;  (  L  2    mod      N  )    ⟹    (  A    mod      N  )  +  M  .  n  &amp;lt;  (  L  2    mod      N  )  n  &amp;lt;            (      L      2            mod                  N      )      −      (      A            mod                  N      )        M    ∴  n  &amp;lt;  m  i  n  (  L  1    mod      N  ,            (      L      2            mod                  N      )      −      (      A            mod                  N      )        M    )

Joel French · Accepted Answer

Try       X    1    =  0). If it results in       X    2    ≥      L    2   then calculate   D  =  ⌈  (  N  −      X    2    )  /  M  ⌉.Try       X    1    +  D  mod  MRepeat as needed. This allows me to skip over most values of       X    1   that will not produce an       X    2   in the required range.

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

Answered question

Answer & Explanation

New Questions in Algebra I