# number theory question in a group with unknown order

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

• Of course, a more efficient way to select a uniformly distributed $h \in \mathbb{G}$ would be to select a random uniformly distributed $z$..., and set $h = z$. If you don't have a way to select a random uniformly distributed $z$, then the method in the paper isn't uniformly distributed either... – poncho Feb 18 at 20:52

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$$.
• $z.z'-1$ means $z.z'^{-1}$ right? – arman haghighi Feb 18 at 18:27
• Thank you for your answer. how it is related to the fact that gcd($n,\prod e_i$)=1? – arman haghighi Feb 18 at 18:37
• @arman haghighi : You are right, my former proof did not use that $\gcd(n,\prod e_i)=1$. It now does. On top of that, it is much simpler. – fgrieu Feb 18 at 19:04