DLP en un grupo cíclico

Question

Dejemos que $q$ sea un primo. $G$ es un grupo cíclico de orden $q^2$ . Demuestre que para resolver el DLP en $G$ es suficiente para resolver dos DLP distintos en dos grupos de orden $q$ .

---

Estamos buscando un $x$ tal que $\alpha^x=\beta$ en este grupo $G$ .

Por la CRT $G \cong C_q \times C_q$ ¿es así? Así que tomando el isomorfismo CRT se obtiene

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

Así que tenemos que resolver $\alpha^x=\beta$ en $C_q$ ¿ahora? ¿Pero es esto correcto? Lo dudo porque en el ejercicio quieren dos DLP distintos

Answer 1

Escribe $x=x_1+x_2q$ . Resolver $a^{x_1} = b \bmod{q}$ para encontrar $x_1$ . Sea $a^q \bmod{q} = c$ , $b a^{-x_1} \bmod{q}=d$ . Encuentre $x_2$ resolviendo $c^{x_2} = d \bmod{q}$ .