Skip to main content
2 of 3
Polish
fgrieu
  • 141.1k
  • 12
  • 307
  • 588

Define the functions $f_i$ $$\begin{align} f_i: G&\to G\\ x&\mapsto x^{e_i} \end{align}$$ $f_i$ is injective. Proof: if $f_i(x)=f_i(y)$ then $x^{e_i}=y^{e_i}$, thus $(x\cdot y^{-1})^{e_i}=1$, thus the order of $(x\cdot y^{-1})$ divides $e_i$, thus is $1$ (it can't be $e_i$ since that's larger than the group order), thus $(x\cdot y^{-1})=1$, thus $x=y$.

Any injection over a finite set is a bijection. It follows that $f_i$ is a bijection over $G$.

The composition of all the $f_i$ is thus a bijection over $G$. That's also the function $$\begin{align} f: G&\to G\\ x&\mapsto x^{\prod_i e_i} \end{align}$$

Thus $h$ is constructed as the image of a uniformly random element $z$ of $G$ by a bijection $f$ over $G$. Hence $h$ is a uniformly random element of $G$.

fgrieu
  • 141.1k
  • 12
  • 307
  • 588