# How to build $\operatorname{Hom}(\mathbb{Z}_p^*,\mathbb{Z}_{pq}^*)$ without solving DLP?

For given two distinct primes p and q, I want to construct all homomorphisms from the multiplicative group $\mathbb{Z}_p^*$ to the multiplicative group $\mathbb{Z}_{pq}^*$.

Thanks to Jyrki Lahtonen's suggestion, we now know that we can define all possible homomorphisms from $\mathbb{Z}_p^*$ to $\mathbb{Z}_{pq}^*$ by $$f(g^i_1)=w_j^i$$ for in total $d(p-1)$ possible $w_j,j=1,2,ā¦,d(pā1)$, of $\mathbb{Z}^ā_{pq}$ that satisfy the equation $w_j^{pā1}=1$, where $g_1$ is a generator of $\mathbb{Z}_p^*$ and $d=\gcd(p-1,q-1)$.

However, the above homomorphisms $f$ requires us to solving the discrete logarithm problems (DLP) over $\mathbb{Z}_p^*$. My question is: Is it possible to explicitly ENUMERATE ALL these homomorphisms $f$ without solving the DLP problems?

-
I agree with you. So, I updated my question. In fact, I also dislike the second "homomorphism". I want a non-trivial and efficiently computable homomorphisms from $\mathbb{Z}_p^*$ to $\mathbb{Z}_{pq}^*$. Thanks your earlier comments and suggestions. But your suggestions need to compute DLP, which is difficult in general. – Pigmann Jun 20 '13 at 8:42
Yes, it does require DLP. I saw this coming (and removed the no longer relevant comments). – Jyrki Lahtonen Jun 20 '13 at 9:02
Thanks for your effort to clarify this problem. Then, do you have any idea to solve it without solving DLP? – Pigmann Jun 20 '13 at 9:49