# Difference between when select x from $\mathbb{Z}_{p-1}$ and $\mathbb{Z}_p$ in discrete logarithm Problem?

Reading "Security Arguments for Digital Signatures and Blind Signatures" paper, I confused by some questions.

• Q1. when it refers to "El Gamal signature scheme",

The key generation algorithm: it chooses a random large prime $$p$$, of length $$n$$ polynomial in $$k$$, and a generator $$g$$ of $$(\mathbb{Z}/p\mathbb{Z})^*$$, both public. Then, for a random secret key $$x \in \mathbb{Z}/(p − 1)\mathbb{Z}$$, it computes the public key $$y = gx \mod p$$

why $$x$$ select from group $$\mathbb{Z}_{p-1}$$,but not $$\mathbb{Z}_p$$? what is the difference?

• please check the update of your question with latex. – kelalaka Mar 31 at 10:00

## 2 Answers

$$\mathbb{Z}_p=\mathbb{Z}/p\mathbb{Z}$$ denotes a finite field that is just integers mod the prime $$p$$, i.e., $$\{0,1,\ldots,p-1\}$$. This field (by definition of a field) has two operations: addition and multiplication, where the multiplication group (denoted by $$\mathbb{Z}_p^*$$) is defined only on the non-zero elements $$\{1,2,\ldots,p-1\}$$. Then, since $$g$$ is a generator of the multiplicative group of size $$p-1$$, the exponent $$x$$ should be sampled from $$\mathbb{Z}_{p-1}=\{0,1,\ldots,p-2\}$$ (which by the way is not a finite field).

Because $$\mathbb{Z}/{p\mathbb{Z}}$$ when used for El-Gamal is used in its multiplicative form: we have a generator $$g$$ such that all powers of $$g$$ cycle through $$\{1,2,\ldots,p-1\}$$ (so $$0$$ is excluded) and as $$g^{p-1} =1 \pmod{p}$$ by Fermat's little theorem, the powers $$x$$ we use for the generator and which we use as the private key in the DL scheme essentially takes values in $$\{0,\ldots,p-2\}$$ (as $$x=0$$ and $$x=p-1$$ both yield $$g^x=1$$), i.e. $$g^x = g^{x'} \pmod{p}$$ iff $$x = x'\pmod{p-1}$$. Hence the fact we have $$p-1$$ choices for $$x$$.