2
$\begingroup$

It is a bit stupid question, but I am so confused. Please examine my explanation. What is the space that exponents the generator $g$ of a cyclic group $G$ of prime order $p$?

I think it is $\mathbb{Z}_p$ since $|G|=p$, so that $G=\{g^0, g^1, \ldots, g^{p-1}\}$. Thus the space that the exponents live is $\mathbb{Z}_p$, which is a field.

But here is what I am confused. By Fermat's little theorem, $\forall a\in \mathbb{Z}_p-\{0\}, a^{p-1}\equiv 1 (mod \,p)$. Is this also holds for $g^{p-1}$? Namely, is $g^{p-1}\equiv 1 (mod \, p)$?

I think it isn't, because the statement of Fermat's little theorem is about power of elements in $\mathbb{Z}_p$, which is an additive cyclic group of order $p$, but in the ElGamal case, we are dealing with multiplicative cyclic group of order $p$.

Please examine my statements whether I am correct or not.

Thank you in advance.

$\endgroup$

1 Answer 1

2
$\begingroup$

As you have observed by Fermat we have $g^{p-1}\equiv1\pmod p$, however we also know that $g^0\equiv 1\pmod p$ so that $g^0$ and $g^{p-1}$ represent the same element of $G$. Therefore $|G|=p-1$ and the exponents lie in $\mathbb Z/(p-1)\mathbb Z$.

$\endgroup$
3
  • $\begingroup$ But then, why is (the order of $G$)=$p$? Isn't it a group of order $p-1$? $\endgroup$ Commented May 3, 2023 at 10:36
  • 1
    $\begingroup$ The order of $g$ is $p-1$ and $G$ is a group of order $p-1$ $\endgroup$
    – Daniel S
    Commented May 3, 2023 at 10:38
  • $\begingroup$ Thank you. I think I had some imprecise understanding in mathematical notations. $\endgroup$ Commented May 22, 2023 at 4:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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