What is the space that exponents of ElGamal encryption scheme live?

Lee Seungwoo

5/3/24, 10:04 AM

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.

1 + 0

elgamal-encryption

group-theory

Score:2

Crypto

Daniel S

5/3/24, 10:27 AM

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$.

+ 3

Lee Seungwoo

5/3/24, 10:36 AM

But then, why is (the order of $G$)=$p$? Isn't it a group of order $p-1$?

Daniel S

5/3/24, 10:38 AM

The order of $g$ is $p-1$ and $G$ is a group of order $p-1$

Lee Seungwoo

5/22/24, 4:31 AM

Thank you. I think I had some imprecise understanding in mathematical notations.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: What is the space that exponents of ElGamal encryption scheme live?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.