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.

If I have a group $\mathcal{G}$ of order $N=npq$ and subgroups $\mathcal{G_n,G_p,G_q}$ of order $n$, $p$, $g$ respectively and if $g$ is a generator of $\mathcal{G}$ why then $g^{nq}$ is a generator of $\mathcal{G_p}$, $g^{np}$ is a generator of $\mathcal{G_q}$ and $g^{pq}$ is a generator of $\mathcal{G_n}$ ? I am trying to understand a research paper

share|improve this question
2  
As it is, it looks like a homework question directly copied from the book. Could you add some context to why you need this, or what this has to do with cryptography? –  Paŭlo Ebermann Oct 26 '12 at 23:21
    
curious, I'd also like to point you to the FAQ, particularly the section titled "Do we accept basic level/homework questions?" and the resources linked to from there. –  D.W. Oct 28 '12 at 4:03
    
@PaŭloEbermann It's not a homework. I was trying to come up with something i was reading in a paper –  curious Oct 28 '12 at 23:57

2 Answers 2

up vote 3 down vote accepted

Every element $g$ in a group $G$ generates a subgroup of $G$ of order $r$, where $r$ is the smallest (non-zero) integer such that $g^r = 1$. Moreover, if $g^s = 1$ for some positive value $s$, then $s$ is a multiple of $r$. Finally, $r$ necessarily divides the order of $G$ (i.e. the number of elements in $G$).

Therefore, if your group order is $N = ab$ for two integers $a$ and $b$, then $(g^a)^b = g^N = 1$, therefore the order of $g^a$ is a divisor of $b$. If $b$ is prime, then the order of $g^a$ can only be $1$ or $b$. However, only $1$ can have order $1$, therefore $g^a$ can have order $1$ only if $g^a = 1$.

In your case, I suppose that you envision $N= npq$ where $n$, $p$ and $q$ are three distinct primes. Thus, $g^{np}$ can have order only $1$ or $q$. But this cannot be $1$ because $g$ generates the whole of $G$, not a strict subgroup. The conclusion follows.

share|improve this answer

If $\mathcal{G}$ is of order $N$ (who doesn't look like a prime number btw) and $g$ is a generator of $\mathcal{G}$ then $g$ has order N. Since $(g^{nq})^p=1$ and $\forall 1\le k <p, (g^{nq})^k\neq 1$ (g has order $N$ and $knq<N$) then $g^{nq}$ generates a subgroup of $\mathcal{G}$ of order $p$ and there's only one such subgroup : $\mathcal{G_p}$. The reasoning is the same for the rest. Hope it's clear and correct

share|improve this answer

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.