I need help solving the following two congruences:
s1 = (k^-1)(m1 + a*r1) mod q
s2 = (k^-1)(m2 + a*r2) mod q
All values are known except for k and a.
I know that to solve a single linear congruence, one can use the EEA. And to solve multiple linear ones (single variable), you can use the chinese remainder theorem, but I've never encountered a scenario like this (and this isn't even for a math class ). What's the general procedure/algorithm/theorem that one uses to solve one of this form? I tried doing a substitution on k, but then one gets this very messy non-linear congruence, with nested mods (which isn't any easier to solve).
This post has been edited by LivingNightmare: 08 July 2012 - 05:43 AM