# Solving MultiVar Congruences

Page 1 of 1

## 0 Replies - 3294 Views - Last Post: 08 July 2012 - 05:41 AM

### #1 LivingNightmare

Reputation: 21
• Posts: 129
• Joined: 07-July 10

# Solving MultiVar Congruences

Posted 08 July 2012 - 05:41 AM

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