0

I'm implementing a Merkle-Hellman cryptosystem and I have a question about a small detail.

In order for it to work, all potential subsets of the super-increasing sequence must have distinct sums. That is very easy to prove because the set is super-increasing.

However, I assume it to be true that these sums times r modulo q (where q is larger than any of the sums and r and q are relatively prime) are also distinct, but I can't prove it.

Basically, this is what I need proven:

Given two integers x and y.  
For any q larger than x and y, choose r such that gcd(r, q) = 1.
Prove that: x * r ≢ y * r (mod q)

Any help would be greatly appreciated. Thanks!

Patrick
  • 3
  • 1

1 Answers1

0

If $\gcd(r,q)=1$, then $$xr \not\equiv yr \pmod q$$ occurs if and only if $$x \not\equiv y \pmod q.$$

Proof: If $x \equiv y \pmod q$, then $xr \equiv yr \pmod q$. Now assume $x \not\equiv y \pmod q$. Since $\gcd(r,q)=1$, we know $r$ is invertible in $\mathbb{Z}_q$ (i.e., $r$ is a unit); its inverse can be found using the Extended Euclidean Algorithm. Hence, if $xr \equiv yr \pmod q$ then $x \equiv xrr^{-1} \equiv yrr^{-1} \equiv y \pmod q,$ giving a contradiction.

This means you need to ensure that $x \not\equiv y \pmod q$.

Rebecca J. Stones
  • 26,845