Group Theory

Definition of Group

Order of Group

Group Z^×_p

The multiplicative group $Z^{\times}_p$ is a group containing integers between 1 and p - 1 (p is a prime number): $Z^{\times}_p = { 1, 2, .... p-1 } \text { , where } p \text{ is a prime number.}$ and the basic operation of this group is multiplication. By taking the remainder on division by $p$, the results of multiplication of elements is ensured closure and limited between 1 to p - 1.

Multiplicative Group of Integers Modulo p

Examples

Let $G = \{ 1, 2, 3, 4 \}$ with prime $p = 5$ and generator $g = 2$.

$\begin{aligned} 2^1 \bmod 5 &= 2 \\ 2^2 \bmod 5 &= 2 \cdot 2 \bmod 5 \\ &= 4 \\ 2^3 \bmod 5 &= 4 \cdot 2 \bmod 5 \\ &= 3 \\ 2^4 \bmod 5 &= 3 \cdot 2 \bmod 5 \\ &= 1 \\ 2^5 \bmod 5 &= 1 \cdot 2 \bmod 5 \\ &= 2 \end{aligned}$

Let $G = \{ 1, 2, 3, 4, 5, 6, 7 \}$ with prime $p = 7$ and generator $g = 3$.

$\begin{aligned} 3^1 \bmod 5 &= 3 \\ 3^2 \bmod 5 &= 3 \cdot 3 \bmod 7 \\ &= 2 \\ 3^3 \bmod 5 &= 2 \cdot 3 \bmod 7 \\ &= 6 \\ 3^4 \bmod 5 &= 6 \cdot 3 \bmod 7 \\ &= 4 \\ 3^5 \bmod 5 &= 4 \cdot 3 \bmod 7 \\ &= 5 \\ 3^6 \bmod 5 &= 5 \cdot 3 \bmod 7 \\ &= 1 \\ 3^7 \bmod 5 &= 1 \cdot 3 \bmod 7 \\ &= 3 \end{aligned}$

Let $G = \{ x \vert 0 < x < 23 \cap x \in N \}$ with prime $p = 23$ and generator $g = 5$.

$\begin{aligned} 5^1 \bmod 23 &= 5 \\ 5^2 \bmod 23 &= 5 \cdot 5 \bmod 23 \\ &= 2 \\ 5^3 \bmod 23 &= 2 \cdot 5 \bmod 23 \\ &= 10 \\ 5^4 \bmod 23 &= 10 \cdot 5 \bmod 23 \\ &= 4 \\ 5^5 \bmod 23 &= 4 \cdot 5 \bmod 23 \\ &= 20 \\ 5^6 \bmod 23 &= 20 \cdot 5 \bmod 23 \\ &= 8 \\ 5^7 \bmod 23 &= 8 \cdot 5 \bmod 23 \\ &= 17 \\ 5^8 \bmod 23 &= 17 \cdot 5 \bmod 23 \\ &= 16 \\ 5^9 \bmod 23 &= 16 \cdot 5 \bmod 23 \\ &= 11 \\ 5^{10} \bmod 23 &= 11 \cdot 5 \bmod 23 \\ &= 9 \\ 5^{11} \bmod 23 &= 9 \cdot 5 \bmod 23 \\ &= 22 \\ 5^{12} \bmod 23 &= 22 \cdot 5 \bmod 23 \\ &= 18 \\ 5^{13} \bmod 23 &= 18 \cdot 5 \bmod 23 \\ &= 21 \\ 5^{14} \bmod 23 &= 21 \cdot 5 \bmod 23 \\ &= 13 \\ 5^{15} \bmod 23 &= 8 \cdot 5 \bmod 23 \\ &= 19 \\ 5^{16} \bmod 23 &= 19 \cdot 5 \bmod 23 \\ &= 3 \\ 5^{17} \bmod 23 &= 3 \cdot 5 \bmod 23 \\ &= 15 \\ 5^{18} \bmod 23 &= 15 \cdot 5 \bmod 23 \\ &= 6 \\ 5^{19} \bmod 23 &= 6 \cdot 5 \bmod 23 \\ &= 7 \\ 5^{20} \bmod 23 &= 7 \cdot 5 \bmod 23 \\ &= 12 \\ 5^{21} \bmod 23 &= 12 \cdot 5 \bmod 23 \\ &= 14 \\ 5^{22} \bmod 23 &= 14 \cdot 5 \bmod 23 \\ &= 1 \\ 5^{23} \bmod 23 &= 1 \cdot 5 \bmod 23 \\ &= 5 \end{aligned}$

Schnorr group

A Schnorr group is a subgroup of $Z^{\times}_p$, the multiplicative group of integers modulo $p$ for some large prime $p$.

The group can be generated by choosing $p, q, r$ such that $p = qr + 1 \text{ ,where } q, r \text{are also prime}$ Then choose any $h, 1 < h < p$ such that $h^r \neq 1 \pmod p$ The value $g = h^r \bmod p$ is the generator of a $Z^{\times}_p$ with prime order $q$.

Examples

Let $q = 11, r = 2, p = 23$. Then we choose a $h$ such that $h^2 \bmod 23 \neq 1$, where $1 < h < 23$. Suppose we select $h = 3$, then generator $g = 9$.

$\begin{aligned} 9^1 \bmod 23 &= 9 \\ 9^2 \bmod 23 &= 9 \cdot 9 \bmod 23 \\ &= 12 \\ 9^3 \bmod 23 &= 12 \cdot 9 \bmod 23 \\ &= 16 \\ 9^4 \bmod 23 &= 16 \cdot 9 \bmod 23 \\ &= 6 \\ 9^5 \bmod 23 &= 6 \cdot 9 \bmod 23 \\ &= 8 \\ 9^6 \bmod 23 &= 8 \cdot 9 \bmod 23 \\ &= 3 \\ 9^7 \bmod 23 &= 3 \cdot 9 \bmod 23 \\ &= 4 \\ 9^8 \bmod 23 &= 4 \cdot 9 \bmod 23 \\ &= 13 \\ 9^9 \bmod 23 &= 13 \cdot 9 \bmod 23 \\ &= 2 \\ 9^{10} \bmod 23 &= 2 \cdot 9 \bmod 23 \\ &= 18 \\ 9^{11} \bmod 23 &= 18 \cdot 9 \bmod 23 \\ &= 1 \\ \end{aligned}$

From above, we can verify the the generator $g = 9$ whose order is $q = 11$ such that $g^q = 1$. In summary, the above equations can be organized into the following table:

Therefore, we have a Schnorr group $G = \{1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18 \}$ with prime order $q = 11$, modulo $p = 23$ and generator $g = 9$, which is a subgroup of $Z^{\times}_p = Z^{\times}_{23} = \{ x \vert 0 < x < 23 \cap x \in N \}$.

References

• Group Z^×_p
• Primitive root modulo n
• Group Order
• Example for Cyclic Groups and Selecting a generator
• Schnorr group