I am trying to solve an exercise from a cryptography textbook and I am stuck with these specific subquestion - any kind of suggestion is welcome!
Let $\alpha = 12$ be a generator of the group $(\mathbb{Z}_p)^{*}$ where $p = 12q+1$ is a prime and $q$ is a very large prime. Assume Alice private key is $a$.
Show that it is possible to efficiently (without use of the discrete logarithm on $q$) find an integer $z$ such that $ 12^{qz} \equiv y_A^q \pmod{p}$ where $y_A = \alpha^a$
You're trying to find an integer $z$ such that $12^{qz} \equiv 12^{qa}$ mod $p$. What does it take for $12^{qz}$ to be equivalent to $12^{qa}$ (mod $p$)?
Recall Euler's theorem: since $\alpha$ and $p$ are relatively prime, $\alpha^{\varphi(p)} \equiv 1$ (mod p). But we have $\varphi(p) = p - 1 = 12q$ because $p$ is prime; thus $\alpha^{12q} \equiv 1$ (mod p).
This means that if $s$ and $t$ differ by a multiple of $12q$, then $12^s \equiv 12^t$ (mod $p$). What does this tell you about $12^{qa}$ vs $12^{qz}$?
I can give further hints if you need them.