2
$\begingroup$

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$?

Improve this question
$\endgroup$
0
5
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\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

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.