[LivingNightmare]

Hi,

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).

Advice?

Thanks!

This post has been edited by LivingNightmare: 08 July 2012 - 05:43 AM