It is $p-1$. I give an detailed explanation of why it is. ##1. First, I give an Corollary, it is used to prove the Elgamal Signature Verification. **Corollary** If $a$ and $p$ are relative prime integers, and $p$ is a prime integer,then $a^i \equiv a^j \pmod p$,where i and j are nonnegative integers, if and only if $i \equiv j \pmod {p-1}$. This Corollary give the relationship of $p$ and $p-1$. One of the methods to prove it is based on a Theorem. The Theorem lies in 《elementary number thoery 6th》 **Theorem 9.2**. It can alse be used to prove the DSA. **Theorem 9.2** If $a$ and $n$ are relative prime integers with $n>0$,then $a^i \equiv a^j \pmod n$,where i and j are nonnegative integers, if and only if $i \equiv j \pmod {ord_n^a}$ Specially, when $p$ is a prime integer, ${ord_p^a}=\varphi(p)=p-1$ , so we prove the Corollary. hence: $$i \equiv j \pmod {p-1} \Leftrightarrow a^i \equiv a^j \pmod p.$$ ##2. Now, we review the Elgamal Signature, and prove it using the Corollary. ###2.1 Key Generation for Elgamal Digital Signature >1. Choose a large prime $p$. >2. Choose a primitive element $\alpha$ of $Z_p^*$. >3. Choose a random integer $d \in \{2,3, . . . , p-2\}$. >4. Compute$\beta = \alpha^d \pmod p$. >The public key is $k_{pub}=(p, \alpha, \beta)$, and private key $k_{pr}=d$ ###2.2 Elgamal Signature Generation The signing consists of two main steps: choosing a random value $k$, which forms an ephemeral private key, and computing the actual signature of $x$. >1. Choose a random ephemeral key $k \in \{0,1,2, . . . , p-2\}$ such that $gcd(k, p-1) = 1$. >2. Compute the signature parameters: $$r \equiv \alpha^k mod p$$ $$s \equiv (x-d\cdot r)k^{-1} \pmod {p-1}$$ hence, the signature is: $$sig_{k_{pr}}(x,k)=(r,s)$$ ###2.3 Elgamal Signature Verification 1. Compute the value $$t \equiv \beta^r \cdot r^s \pmod p$$ 2. The verification follows from: $$ t\begin{cases} \equiv \ \alpha^x \pmod p\ \ \ \ \Rightarrow \ \ \ \ valid \ \ signature\\\\ \not \equiv \ \alpha^x \ \pmod p\ \ \ \ \Rightarrow \ \ \ \ invalid \ \ signature \end{cases} $$ ###2.4 Proof Prove that: $$ \alpha^x \equiv \beta^r \cdot r^s \pmod p$$ since: $$ \beta^r \cdot r^s \pmod p \equiv (\alpha^d)^r(\alpha^k)^s \pmod p \equiv \alpha^{d\cdot r+k\cdot s} \pmod p$$ So, we require that : $$\alpha^x \equiv \alpha^{d\cdot r+k\cdot s} \pmod p$$ According the Corollary we give above, the relationship holds **if and only if**: $$ x \equiv d\cdot r+k\cdot s \pmod {p-1}$$ hence, we get $s$: $$s\equiv (x - d \cdot r)k^{-1} \pmod {p-1}$$ This is just the construction rule of the signature parameters s follows. The condition that $gcd(k, p-1) = 1$ is required since we have to invert the ephemeral key modulo $p-1$ when computing s. ##3. Conclusion From above discription, we know that why it is $p-1$, not $p$. ## Reference 1. 《elementary number theory 6th》 2. 《Understanding cryptography》