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

  • 2
    $\begingroup$ 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? $\endgroup$ Commented Oct 26, 2012 at 23:21
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Commented Oct 28, 2012 at 4:03
  • $\begingroup$ @PaŭloEbermann It's not a homework. I was trying to come up with something i was reading in a paper $\endgroup$
    – curious
    Commented Oct 28, 2012 at 23:57

2 Answers 2


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.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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