1

Let $q$ be a prime. $G$ is a cyclic group of order $q^2$. Show that for solving the DLP in $G$ it's enough to solve two distinct DLPs in two groups of order $q$.

---

We are looking for an $x$ such that $\alpha^x=\beta$ in this group $G$.

By the CRT $G \cong C_q \times C_q$ alright? So taking the CRT-isomorphism yields

$\phi(\alpha^x)=(\alpha^x \mod q, \alpha^x \mod q)\overset{!}{=} (\beta \mod q,\beta \mod q)=\phi(\beta)$

So we have to solve $\alpha^x=\beta$ in $C_q$ now? But is this correct? I doubt that because in the exercise they want two distinct DLPs ???

choco_addicted
  • 8,786
  • 8
  • 24
  • 53
unterbrause
  • 111
  • This is pretty hard to read because of the acronyms and the undefined function $\phi$. But $G\equiv C_q \times C_q$ is definitely not true; the Chinese Remainder Theorem only applies to two relatively prime integers. – Andrew Dudzik Mar 22 '14 at 10:27
  • Well $\Phi$ is the well-known CRT isomorphism. Okay you are right this is not true. But how does this exercise work then? – unterbrause Mar 22 '14 at 14:50

1 Answers1

0

Write $x=x_1+x_2q$. Solve $a^{x_1} = b \bmod{q}$ to find $x_1$. Let $a^q \bmod{q} = c$, $b a^{-x_1} \bmod{q}=d$. Find $x_2$ by solving $c^{x_2} = d \bmod{q}$.

duje
  • 433