I don't know how to prove the following:

Let $a$ be randomly chosen out of $\{ 1,..., p-1\}$ and $b$ randomly chosen out of $\{ 0,..., p-1\}$. Let $m$ be a natural number smaller than a prime number $p$. Let $ h_{a,b}:$ $\{ 0,..., p-1\} \to \{0, ..., m-1 \}$ which is defined as $ h_{a,b} = (ax + b \mod p) \mod m$. Prove for all natural numbers $x, y$ with $x < y < p$: $ P_{a,b}(h_{a,b}(x)=h_{a,b}(y)) \le \frac{1}{m}$ where $P$ is the probability.

  • $\begingroup$ When asking a question like this, I encourage you to provide additional context, such as: Where did you encounter this task? What did you try, and what progress have you made? If you're stuck, working through a few examples with small numbers (e.g., with $p=3$ or $p=5$) is often useful for developing intuition. $\endgroup$
    – D.W.
    Jun 28 at 22:06

Let $k_{a,b}(x) = ax + b \bmod{p}$. If $x \neq y$ then $k_{a,b}(x), k_{a,b}(y)$ is a random pair of distinct numbers in $\{0,\ldots,p-1\}$. Therefore we have reduced your question into the following one:

Show that if $x \neq y$ are random distinct numbers in $\{0,\ldots,p-1\}$, then $$\Pr[x \bmod m = y \bmod m] \leq \frac{1}{m}.$$

Suppose that $p = dm + r$, where $1 \leq r \leq m-1$. Then $\Pr[x \bmod m = c]$ is either $d/p$ (for $c \ge r$) or $(d+1)/p$ (for $c < r$). It follows that $$ \Pr[x \bmod m = y \bmod m] = r \frac{(d+1)d}{p(p-1)} + (m-r) \frac{d(d-1)}{p(p-1)} = \frac{(p-m+r)d}{p(p-1)}. $$ Since $r < m$, we have $\frac{p-m+r}{p-1} \leq 1$. Also, $\frac{d}{p} \leq \frac{d}{dm} = \frac{1}{m}$. Altogether, we obtain an upper bound of $\frac{1}{m}$.

  • $\begingroup$ Why is the probabillity for $\Pr[x \bmod m = c]$ either $d/p$ (for $c \ge r$) or $(d+1)/p$ (for $c < r$)? $\endgroup$ Jun 28 at 16:42
  • $\begingroup$ And as a follow up question, shouldn't it be $m > r$ at the end because of the way you defined $r$? $\endgroup$ Jun 28 at 16:55
  • $\begingroup$ Right, thanks for the correction. As for calculating the probability that $x \bmod m = c$, you'll have to work it out. Perhaps try some concrete numerical examples. $\endgroup$ Jun 28 at 18:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.