5
$\begingroup$

Given a prime $p$ and $m \in Z_p^*$.

Assume we draw $a \stackrel{u}{\in} Z_p^*$ uniformly at random.

Will $a \cdot m \bmod p$ be distributed uniformly over $Z_p^*$?

$\endgroup$
3
  • 1
    $\begingroup$ For any $k \in Z^*_p$, the chance of getting $k$ is $1\over p-1$, because it only happens for one value of $a$, namely when $a \equiv m^{-1}k \pmod p$. Is that what you mean? $\endgroup$
    – Théophile
    Mar 9, 2016 at 19:54
  • $\begingroup$ That is exactly what I mean - thanks! $\endgroup$
    – joshlf
    Mar 9, 2016 at 20:00
  • $\begingroup$ Glad to help! I'll write it as an answer. $\endgroup$
    – Théophile
    Mar 9, 2016 at 20:30

1 Answer 1

3
$\begingroup$

Yes, the $am$ will be distributed uniformly modulo $p$. For any $k \in \mathbb Z^*_p$, the chance of getting $k$ is $\frac1 {p-1}$, because it happens for only one value of $a$, namely when $a \equiv m^{-1}k \pmod p$.

Note that if $p$ is not prime, then the same result holds only when $\gcd(m,p)=1$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .