# How difficult is it to check if a group element is in a sub group?

I am just curious. We have a group $G$ and its subgroup $H$ with a generator element $h \in H$. How difficult is it to check for $x \in G$ that $x \in \langle h \rangle$? Is there a better way than testing $x \equiv h^1,\ x \equiv h^2,\ x \equiv h^3,\ ...$?

• I guess there is a generic algo that runs in $\sqrt{s}$ time where $s$ is the order of the subgroup, and group specific algos that may be much faster. Mar 8, 2013 at 13:50
• The answer depends upon the group, and potentially upon how group elements are represented. What group did you have in mind?
– D.W.
Mar 8, 2013 at 18:17
• It was just a general question. I didn't have a specific group in my mind. Mar 8, 2013 at 20:19

If the group $G$ is finite and cyclic (and hence Abelian), it has exactly one subgroup of order $s$, for each $s$ which divides the order of $G$.
Since any subgroup of a cyclic group is also cyclic and hence Abelian, you might easily implement the operation in $H$ that is the equivalent of modular exponentiation in $Z_n^*$.
If you also already know the order $s$ of $h$, you know that, because of associativity and commutativity, that $(h^s)^t = (h^t)^s = 1$ for any $t$. Hence, checking that $x \in H$ is just a question of checking that $x^s = 1$.
• That may be sufficient, depending on the group. Just because $x^s = 1$ does not mean that $x$ is in the subgroup you're interested in, there might be a second subgroup of the same size, even if $G$ is Abelian. Consider the case where $G$ is isomorphic to $Z_s \times Z_s$; that has two subgroups of size $s$; just checking if $x^s=1$ will tell you if it's in one of the subgroups, just not which one. Now, where we're dealing with multiplicative groups $Z^*_p$, we never get groups like this; however, it can happen in the more general case. Mar 8, 2013 at 15:00