How to solve for b in a = b mod q

[John Harris]

Homework Statement

How do I solve for b in a= b mod q

Homework Equations

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

The Attempt at a Solution

Unsure how to move the mod q to the other side.

 

[Simon Bridge]

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?

 

[John Harris]

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?

Got to make sure I work for it... Any odd number. b divides q-a

 

[Simon Bridge]

Good - you just solved the problem for a specific example.
Next step is to see if you can generalize.

 

[John Harris]

Good - you just solved the problem for a specific example.
Next step is to see if you can generalize.

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

 

[Simon Bridge]

Go through it one step at a time - make sure you know what each bit means.

 

[John Harris]

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.

 

[SammyS]

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.

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?

 

[John Harris]

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?

But this is an equality not a congruence.
3=19 mod 8
19≠3mod 8

 

[SammyS]

But this is an equality not a congruence.
3=19 mod 8
19≠3mod 8

Yes, I overlooked the ' = ' sign.

 

[SammyS]

But this is an equality not a congruence.
3=19 mod 8
19≠3mod 8

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 \$.

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

What they are doing here is certainly strange. What information, if any, do we know regarding, H(m), r, and k ?