# ElGamal in $Z^*_{p^n}$

If $p$ is an odd prime and $n$ natural,it is known that the group $Z^*_{p^n}$ is cyclic.Explain why the selection-choice of the group $Z^*_{{3^{1000}}}$ for the construction of a cryptosystem ElGamal it's not good.

Can anyone explain me why this happens?

• Why what happens? Why $\mathbb{Z}_{p^n}^*$ is cyclic? Jul 31 '15 at 18:41
• why the construction of elgamal it is not good in the specific group Jul 31 '15 at 18:43
• I noticed you posted this a few weeks ago on math.SE. You shouldn't post the same question to multiple sites. If a question is not receiving enough attention on one site and is on-topic on another, you can flag it for moderator attention and ask them to migrate it. Jul 31 '15 at 18:44
• @mikeazo It is a well-known fact that $(\mathbf{Z}/p^n\mathbf{Z})^*$ is cyclic, see for example Chapter 4 of the book by Ireland and Rosen. Jul 31 '15 at 19:04
• @fkraiem Your answer is salvageable since $\lvert\mathbb Z_{p^n}^\ast\rvert=(p-1)p^{n-1}$ never has prime divisors larger than $p$. I suggest you make that minor edit and undelete. Jul 31 '15 at 19:11

## 1 Answer

The order of $(\mathbf{Z}/3^{1000}\mathbf{Z})^*$ is $\varphi(3^{1000}) = 2\times 3^{999}$, which is a highly composite number, and hence the discrete logarithm in this group is highly vulnerable to the Pohlig-Hellman algorithm.

If you are not familiar with the Pohlig-Hellman algorithm, you can peruse for example Section 2.9 of the book by Hoffstein, Pipher and Silverman. Sadly, the Wikipedia article about it is of quite low quality.

• Another way (and, it turns out, an equivalent way) of looking at it is that if we know that if we have a solution for $a^x = b \bmod 3^n$, then we can easily find a solution for $a^x = b \bmod 3^{n+1}$; hence we can start with $n=1$, and work our way up. Jul 31 '15 at 19:18