Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.