Multiplication in $GF(2^n)$: binary representation and probability

95 Views Asked by At

Let $\{0,1\}^n$ denote the set of binary sequences of length $n$, and let $\{0,1\}^n\backslash \{ \mathbf{0}\}$ denote the set of binary sequences of length $n$ without the sequence made of $n$ zeros.

Consider $S$ drawn uniformly at random in $\{0,1\}^n\backslash \{ \mathbf{0}\}$ and $X$ drawn uniformly at random in $\{0,1\}^n$. Assume that $S$ and $X$ represent elements in $GF(2^n)$. Let $M$ be the binary representation of the product of $S$ and $X$ in $GF(2^n)$.

Questions:

  • Is $M$ uniformly distributed in $\{0,1\}^n$ when $S$ and $X$ are independent?

  • Is $M$ uniformly distributed in $\{0,1\}^n$ when $S$ and $X$ are not independent?