1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

How to solve for b in a = b mod q

  1. Feb 25, 2015 #1
    1. The problem statement, all variables and given/known data
    How do I solve for b in a= b mod q

    2. Relevant equations
    I'm not sure what mod operations for equations are allowed. I would like to know.

    3. The attempt at a solution
    Unsure how to move the mod q to the other side.
     
  2. jcsd
  3. Feb 25, 2015 #2

    Simon Bridge

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Back up a bit:
    Pick some numbers for a and q, and see what values of b will make the relation true.
    i.e. 1 = b mod 2

    Try for some other numbers?
    What do you notice?
     
  4. Feb 25, 2015 #3
    Got to make sure I work for it... Any odd number. b divides q-a
     
  5. Feb 25, 2015 #4

    Simon Bridge

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Good - you just solved the problem for a specific example.
    Next step is to see if you can generalize.
     
  6. Feb 25, 2015 #5
    b=qk+a

    But I don't understand how they did it here. They solved for x without removing the mod or adding a k.
    s = k-1 (H(m) + x*r) mod q
    x
    = ((s * k) – H(m)) * r-1 mod q
     
  7. Feb 25, 2015 #6

    Simon Bridge

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Go through it one step at a time - make sure you know what each bit means.
     
  8. Feb 25, 2015 #7
    s = k-1 (H(m) + x*r) mod q

    I see how they got it to ((s * k) – H(m)) * r-1= x mod q
    But I don't see how they get it farther. If I knew I wouldn't be asking for help. I'm just asking for the simple equation property that they used. This isn't a HW assignment. I don't have time to derive it myself. What you asked me to do hasn't helped.
     
  9. Feb 25, 2015 #8

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    Are you saying that you can get from
    s = k -1 (H(m) + x*r ) mod q
    to
    ((s*k ) – H(m)) * r -1 = x mod q ,​

    but you can't solve that for x ?

    Well, if a ≡ b mod q, then b ≡ a mod q . Right?
     
  10. Feb 25, 2015 #9
    But this is an equality not a congruence.
    3=19 mod 8
    19≠3mod 8
     
  11. Feb 26, 2015 #10

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    Yes, I overlooked the ' = ' sign.
     
    Last edited: Feb 26, 2015
  12. Feb 27, 2015 #11

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    True, but the solution to the equation, ##\ 3=x\mod 8 \,,\ ## is ##\ x=3+8n \ ##.

    The mod function is periodic, so there are many solutions for x . One of the solutions is 3 itself. For that solution it is true that ##\ x=3\mod 8 \ ##.
    What they are doing here is certainly strange. What information, if any, do we know regarding, H(m), r, and k ?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: How to solve for b in a = b mod q
  1. Solve for a, b and c (Replies: 2)

  2. Solving sin(ax-b) (Replies: 5)

Loading...