Let $p$ be a prime number. Consider two fixed values $a,b\in\mathbb Z/p\mathbb Z$, where $b\neq0$, and a uniformly random value $r\leftarrow \mathbb Z/p\mathbb Z$.
Is $v=a+b\cdot r$ a uniformly random value in $\mathbb Z/p\mathbb Z$?
$\begingroup$
$\endgroup$
0
Add a comment
|
$\begingroup$
$\endgroup$
4
Yes. For fixed $a\in\mathbb Z/n\mathbb Z$ and $b\in(\mathbb Z/n\mathbb Z)^\ast$ — note that $b$ must be invertible modulo $n$, which need not necessarily be a prime (but if it is, invertibility is equivalent to $b\neq0$), the map $$ f\colon\;\mathbb Z/n\mathbb Z\to\mathbb Z/n\mathbb Z,\; r \mapsto a+br $$ is a bijection, hence it preserves uniform distribution. That is: If $R\colon\;\Omega\to\mathbb Z/n\mathbb Z$ is a uniformly distributed random variable, then $f(R)\colon\Omega\to\mathbb Z/n\mathbb Z$ is as well.
The direct argument is: If $\forall y\in\mathbb Z/n\mathbb Z.\;\Pr[R=y]=1/n$, then for any $x\in\mathbb Z/n\mathbb Z$, $$ \Pr[f(R)=x] = \Pr[a+bR=x] = \Pr[R=b^{-1}(x-a)] = 1/n \text, $$ therefore $f(R)$ is uniformly distributed on $\mathbb Z/n\mathbb Z$.
-
$\begingroup$ Could you please have a look at this question: crypto.stackexchange.com/questions/28995/… $\endgroup$ – user13676 Sep 7 '15 at 14:31
-
$\begingroup$ Is $v=a\cdot y+b$ a uniformly random value where $a,b$ are uniformly random values and $y$ is a fixed value? I'm considering a field $\mathbb{F}^*_p$. Thank you $\endgroup$ – user13676 Sep 8 '15 at 13:06
-
$\begingroup$ @user13676 Where are you stuck in trying to answer this question by yourself? Try coming up with an argument similar to the proof above. $\endgroup$ – yyyyyyy Sep 8 '15 at 14:02
-
$\begingroup$ I seems it is not uniformly random in field [1,p). Because it depends on the distribution of both $a$ and $b$. But why $v$ is uniformly random in [0,p) field? I'm getting confused. Shall I ask a separate question? $\endgroup$ – user13676 Sep 8 '15 at 15:03
