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?

  • $\begingroup$ Why what happens? Why $\mathbb{Z}_{p^n}^*$ is cyclic? $\endgroup$
    – mikeazo
    Jul 31 '15 at 18:41
  • $\begingroup$ why the construction of elgamal it is not good in the specific group $\endgroup$
    – Paris Lamp
    Jul 31 '15 at 18:43
  • $\begingroup$ 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. $\endgroup$
    – mikeazo
    Jul 31 '15 at 18:44
  • $\begingroup$ @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. $\endgroup$
    – fkraiem
    Jul 31 '15 at 19:04
  • 1
    $\begingroup$ @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. $\endgroup$
    – yyyyyyy
    Jul 31 '15 at 19:11

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.

  • 1
    $\begingroup$ 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. $\endgroup$
    – poncho
    Jul 31 '15 at 19:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.