Schnorr group membership

265 Views Asked by At

Consider the multiplicative group of integers modulo $p$ (where $p$ is prime). Suppose this has a subgroup of order $q$ (where $q$ is prime). (Such a subgroup is known as Schnorr group.)

Let $0 < x < p$. Why is $x^q \equiv 1 \pmod{p}$ sufficient to show that $x$ lies in the given subgroup?

1

There are 1 best solutions below

5
On BEST ANSWER

1) The multiplicative group of integers modulo a prime, also denoted $\;\Bbb F_p^*\;$, is a cyclic group, just as any finite subgroup of the multiplicative group of a field is.

2) A finite cyclic group has one unique subgroup of order any divisor of the group's order.

Thus, modulo $\;p\;$ , we have that

$$\text{For}\;x\neq1\pmod p\;:\;\;\;\;x^q=1\iff \langle x\rangle\;\;\text{has order}\;\;q\;\;in\;\;\Bbb F_p^*\iff$$

$$\iff\langle x\rangle \;\;\text{is THE subgroup of order}\;\;q$$