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
Tell me more
×
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.
|
|
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 |
|||
|
|
