# Efficiently finding an integer satisfying a certain congruence

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$

-
And what is $r$? It appears ex nihilo in the last congruence... – Arturo Magidin Jun 1 '11 at 20:47
$r$ is actually $q$. Sorry, I made a typo – Jernej Jun 1 '11 at 22:10

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.

-
A triviality is to take $z = a$ but $a$ is not known as it is Alice private key. Am I missing something? – Jernej Jun 2 '11 at 0:37
More than just "whenever $s$ and $t$ differ by a multiple of $12q$"; what you really want here is the converse: if $s$ and $t$ differ by a multiple of $12q$, then $12^s\equiv 12^t\pmod{p}$. – Arturo Magidin Jun 2 '11 at 3:04
That's what I meant--I'll change the confusing wording. – Elliott Jun 2 '11 at 3:08
Okay so qa-qz is a multiple of 12q which means a-z is a multiple of 12 which implies I only need to check 12 candidates for z? – Jernej Jun 2 '11 at 10:39
Correct :) having only 12 cases to check is very efficient. – Elliott Jun 2 '11 at 19:08