2
$\begingroup$

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,\ ...$?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – CodesInChaos Mar 8 '13 at 13:50
  • $\begingroup$ The answer depends upon the group, and potentially upon how group elements are represented. What group did you have in mind? $\endgroup$ – D.W. Mar 8 '13 at 18:17
  • $\begingroup$ It was just a general question. I didn't have a specific group in my mind. $\endgroup$ – user4811 Mar 8 '13 at 20:19
5
$\begingroup$

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

$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – poncho Mar 8 '13 at 15:00

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.