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

#1 LivingNightmare  Icon User is offline

  • D.I.C Head
  • member icon

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

Solving MultiVar Congruences

Posted 08 July 2012 - 05:41 AM


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

Is This A Good Question/Topic? 0
  • +

Page 1 of 1