Results 1 to 1 of 1

Thread: Solving MultiVariable Congruences

  1. #1
    Jul 2012

    Solving MultiVariable Congruences

    Hello Everyone,

    This is my first post here in this forum, so I look forward to discussing things with everyone here. But for now, I have a little problem. I know that to solve a single linear congruence, once can use the Extended Euclidean Algorithm, and to solve a system of linear congruences, one can use the CRT. However, I believe that these only work with one variable.

    I have the following two congruences:
    s_1 = k^{-1}(m_1 + a r_1) \mod q \\
    s_2 = k^{-1}(m_2 + a r_2) \mod q
    If all of the variables are known (but k and a), how do I go about on solving this? I tried eliminating k, but then I obtain this messy non-linear congruence, that I don't know how to solve as well. I would also like to point out that this isn't for a math course, but a CS course involving a little cryptography... so I'm guessing the solution shouldn't be to complicated.


    EDIT: I am looking for a general procedure/algorithm for solving something like this. The goal of the question is to show that even if someone does not know k, he can still determine the value of a ( for a CS security/cryptography course). If more info is needed, I would be glad to provide.
    Last edited by Nizbel99; Jul 8th 2012 at 03:12 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. solving linear congruences...please help
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Oct 30th 2010, 02:07 AM
  2. solving cubic congruences
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Sep 27th 2010, 06:18 AM
  3. Solving linear congruences
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Mar 12th 2010, 10:46 PM
  4. Solving Congruences
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: Aug 5th 2009, 10:34 PM
  5. Solving congruences
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 31st 2009, 11:16 PM

Search Tags

/mathhelpforum @mathhelpforum