As part of a larger proof, I want to make the following statement:

Let G be finite abelian group.

Let $g\in G$ such that the order of $g^{q}$ is $q^{e}$ where $e\geq1$ and q is prime.

Let $h\in G$ such that $h$ is a power of $g$.

Moreover, let $x_{0}$ be a solution to the Discrete Logarithm Problem applied to $g^{q^{e}}$ and $h^{q^{e}}$.

That is, $(g^{q^{e}})^{x_{0}}=h^{q^{e}}$.

Therefore, $(g^{q^{e}})^{x_{0}}=h^{q^{e}} \iff h^{q^{e}}.(g^{q^{e}})^{-x_{0}}=1\iff(h.g^{-x_{0}})^{q^{e}}=1$.

Now, can I say that $(h.g^{-x_{0}})\in<g^{q}>$?

  • 1
    $\begingroup$ No${}{}{}{}{}{}$. $\endgroup$ – Angina Seng Nov 19 '17 at 22:36
  • $\begingroup$ I am pretty sure I can, since this is part of the Pohlig-Hellman algorithm proof. I just don't know how. $\endgroup$ – popololvic Nov 19 '17 at 22:38
  • $\begingroup$ Then you should say that $G$ is a finite abelian group since that information changes everything. $\endgroup$ – Levent Nov 19 '17 at 22:39
  • $\begingroup$ @jkbestami You need a lot more then $G$ just being a group to use the P-H algorithm. $\endgroup$ – Angina Seng Nov 19 '17 at 22:40
  • $\begingroup$ You are totally right Levent, and I made the edit. I know that you need more for the P-H algorithm but I think I have everything else except for the justification of this claim. $\endgroup$ – popololvic Nov 19 '17 at 22:41

For a cyclic group $H$ of order $n$, it is a theorem that there exists a unique subgroup $K\leq H$ of order $d$ for every divisor $d$ of $n$. Notice that the subgroup generated by $g$ is cyclic of order $q^{e+1}$. Now $h\cdot g^{-x_0}$ has order at most $q^e$. Say $h\cdot g^{-x_0}$ has order $q^d$. Then this element lies in the unique subgroup of order $q^d$ which is necessarily generated by $g^{e+1-d}$. Hence $h\cdot g^{-x_0}\in \langle g^{e+1-d}\rangle\subseteq\langle g^q\rangle$.

| cite | improve this answer | |
  • $\begingroup$ Thank you very much this is exactly what I needed. $\endgroup$ – popololvic Nov 19 '17 at 23:16
  • $\begingroup$ You are welcome, the key point is the so-called the fundamental theorem of cyclic groups. I believe that it is heavily used in cryptography. $\endgroup$ – Levent Nov 19 '17 at 23:18

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.