Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
1  
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. –  CodesInChaos Mar 8 '13 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 '13 at 18:17
    
It was just a general question. I didn't have a specific group in my mind. –  user4811 Mar 8 '13 at 20:19
add comment

1 Answer

up vote 4 down vote accepted

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

share|improve this answer
3  
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. –  poncho Mar 8 '13 at 15:00
    
@Poncho: Thanks, fixed. –  Henrick Hellström Mar 8 '13 at 15:57
    
Thanks, this helps! –  user4811 Mar 8 '13 at 20:19
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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