1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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... $\endgroup$ – poncho Feb 18 at 20:52
1
$\begingroup$

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

| improve this answer | |
$\endgroup$
  • $\begingroup$ $z.z'-1$ means $z.z'^{-1}$ right? $\endgroup$ – arman haghighi Feb 18 at 18:27
  • $\begingroup$ Thank you for your answer. how it is related to the fact that gcd($n,\prod e_i$)=1? $\endgroup$ – arman haghighi Feb 18 at 18:37
  • 1
    $\begingroup$ @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. $\endgroup$ – fgrieu Feb 18 at 19:04
  • $\begingroup$ that fully make sense thank you! $\endgroup$ – arman haghighi Feb 18 at 19:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.