Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
I was reading a paper and I am struggling understanding one part of it. Lets say we have a group $G$ of an unknown order $n$. we know that $B<n<B+C$. both B and C are large values).
we choose a random element $z \in G$. and let's say we have some prime values $B+C<e_1,e_2,...,e_l$. We Calculate $h=z^ {\prod_i e_i}$.
The claim is as $\gcd(n,\prod e_i)=1$ (which is true as each prime is greater than $n$) we can say that $h$ is uniformly distributed in $G$. How can we prove this statement?
Define the function $$\begin{align} f: G&\to G\\ x&\mapsto x^{\prod_i e_i} \end{align}$$ $f$ is injective. Proof: if $f(x)=f(y)$ then $x^{\prod_i e_i}=y^{\prod_i e_i}$, thus $(x\cdot y^{-1})^{\prod_i e_i}=1$, thus the order $k$ of $(x\cdot y^{-1})$ is a divisor of $\prod_i e_i$. Since the order of any group element divides the group order, $k$ is also a divisor of $n$. Since $\gcd(n,\prod e_i)=1$, $k$ must be $1$. Thus $(x\cdot y^{-1})=1$, thus $x=y$.
Any injection over a finite set is a bijection. It follows that $f$ is a bijection over $G$.
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$.
