Is $a+r \cdot b$ an uniformly random value when $a,b$ are fixed and $r$ is random value?

59 Views Asked by At

Imagine we have two fixed values $a,b \in \mathbb{Z}_p$ and a uniformly random value $r\leftarrow \mathbb{Z}_p$, for large prime number $p$.

Question: Is $v=a+b\cdot r$ an uniformly random value in $\mathbb{Z}_p$?

1

There are 1 best solutions below

1
On BEST ANSWER

Clearly, when $b=0$, $v=a$, so it is not a uniform random variable.

When $b \neq 0$, we have that $b$ has an inverse in $\mathbb{Z}_p$, so we have for $c \in \mathbb{Z}_p$ $$\mathbb{P} ( v = c) = \mathbb{P} ( a + b r =c) = \mathbb{P} ( b r = c - a) = \mathbb{P}(r =b^{-1}(c-a)) .$$ Since $r$ is uniform, we have $\mathbb{P}( r = \hat{c} ) = \frac{1}{P}$ for all $\hat{c} \in \mathbb{Z}_p$, so take $\hat{c} = r^{-1}(c-a)$ to conclude that $v$ is a uniform random variable.