$\newcommand{\Z}{\mathbb{Z}}$

A cyclic group $G$ is a type of algebraic structure in abstract algebra which definition is based on the concept of a group and group generators.

Cyclic groups provide the mathematical foundation for many cryptographic protocols and schemes. The hardness of certain mathematical problems in cyclic groups, such as the discrete logarithm problem, forms the basis for the security of these cryptographic systems.

Cyclic Groups and Generators

Given a group $G$ with identity $e$, the order of $a \in G$ is defined as $ord(a) := \text{min} \set{n ∈ \Z : a^n = e }$

Where $a^n$ represents the repeated application of the group operation to $a$, $n$ times

$-$

Definition. A group $G$ is said to be cyclic if there exist at least one element $g \in G$, called a generator (or base or primitive root), such that every element in $G$ can be obtained by repeated application of the group operation on $g$.

$-$

Definition. The number $g \in G$ is a generator of $G$ if $ord(g) = |G|$.

$-$

Proposition. If $g$ is a generator of $G$ then $\set{g^1, .. , g^{|G|}}$ are all distinct.

Proof. For two exponents $0 \leq i \lt j \lt |G|$, we set $r = j - i < |G|$. If $g^j = g^j$ then $g^i = g^{i+r} = g^i·g^r$. Given that $g$ is invertible then we can cancel $g^i$ on both sides leaving with $1 = g^r$. But then $g$ is not a generator as $r < |G|$.

$-$

In this post we’re mostly focusing on groups $\mathbb{Z}_n^* = \set{ x: x < n \land gcd(x,n) = 1 }$ defined with group operation the product modulo $n$.

Example. Given $p = 19$ we know that $\Z_p^*$ is a group with respect to the product modulo $p$ and that $|Z_p^*| = 18$

$$7^1 \bmod 19 = 7 , ... , 7^3 \bmod 19 = 1 → ord(7) = 3$$ $$2^1 \bmod 19 = 2 , ... , 2^{18} \bmod 19 = 1 → ord(2) = 18$$

For Euler’s theorem, if $(a,n) = 1$ then $a^{\phi(n)} = 1$, however the order $a$ can be smaller that $\phi(n)$.

Once we found one generator $g$ for an arbitrary group $G$, all the other generators are easily identified.

$-$

Proposition. Given a generator $g$ for a group $G$ with $|G| = n$, the order of $g^m$ is equal to $n/(m,n)$.

Proof. We are looking for the smaller $k$ such that $(g^m)^k = 1$. As $g$ is a generator with order $n$, then $m·k = n·w$, for some integer $w$. In other words, $m·k$ is the least multiple of $m$ which is also a multiple of $n$ (i.e. the $lcm(m,n)$).

$$ m·k = lcm(m,n) → k = lcm(m,n)/m = (m·n)/gcd(m,n)/m = n/gcd(m,n) $$

$-$

Corollary. Given $g$ a generator of $G$ with order $n$, $g^m$ is another generator iff $(m,n) = 1$.

Proof According to the previous proposition $g^m$ has order $n/(m,n) = n$.

Alt (← direct): $(m,n) = 1 → 1 = m·s + n·t → g = g^{m·s + n·t} = (g^m)^s$. Given that $g^m$ generates $g$, then it generates the whole $G$.

$-$

Corollary. The number of different generators for a group $G$ with order $n$ is $\phi(n)$. Thus, if a group $G$ has prime order then any element of $G$ is a generator.

Subgroups

A subgroup $H$ is a subset of a group $G$ that is itself a group under the same operation as $G$.

The identity of $G$ is also the identity of $H$.

Cosets

A subgroup $H$ of $G$ may be used to decompose $G$ into disjoint, equal-size subsets called cosets.

If $a ∈ G$ then $a·H$ is the left coset determined by applying the group operation to each element of $H$. Note that $a·H$ is not a subgroup as it is missing the identity element.

In general, we can distinguish between left cosets and right cosets, depending on if the operation is applied to the left or to the right of the elements of $H$. When the operation is commutative this distinction doesn’t add much. Furthermore, $H$ itself is both a left coset and a right coset.

The number of left cosets of $H$ in $G$ is equal to the number of right cosets of $H$ in $G$. This value is called the index of $H$ in $G$, written as $[G:H]$.

$-$

Proposition. Any coset $a·H$ has the same number of elements of $H$.

Proof. We can easily define a bijective function from $a·H$ to $H$ using the inverse of $a ∈ G$.

$-$

Proposition. Two cosets are either disjoint or equal.

Proof. Given two cosets $a·H$ and $b·H$. If $a·h_i = b·h_j$ for some $i$ and $j$, then since $h_i ∈ H$ we can write $a = b·h_j·h_i^{-1} = b·h_z$ for some $h_z ∈ H$. Now, given an arbitrary $a·h_t ∈ a·H$ we can write $a·h_t = b·h_z·h_t = b·h_w ∈ b·H$. Thus, we can write $a·H ⊆ b·H$. Using a similar argument we prove that $b·H ⊆ a·H$ and thus $a·H = b·H$.

Lagrange theorem

Lagrange Theorem. For any finite group $G$, the order of every subgroup $H$ of $G$ divides the order of $G$.

Proof. Let $G$ order be $n$ and $H$ order be $m$. Because every coset $a_i·H$ contains the element $a_i·e = a_i$, with $e$ the identity element of $H$ (and $G$), then $G$ can be written as the union of the cosets $G = \bigcup_{i=1}^{n} a_i·H$. After removal of any duplicated coset, we are left with $G = a_1·H \cup .. ∪ a_s·H$, with $s ≤ n$. Given that each coset has the same number of elements of $H$ we have that $n = s·m$.

Proof (Alt). When $G$ is cyclic and generated by $g$ then $H$ is generated by some $g^m$. The order of $g^m$ is $n/(m,n)$ and thus the order of $H$ trivially divides $n$.

Further Properties

Proposition. For a cyclic group $G$ of order $n$, there is exactly one subgroup of order $d$ for each divisor $d$ of $n$.

Proof. Let $g$ a generator of $G$ and $h = g^k$ a generator of $H$, a subgroup of $G$. Then $k·d = n·q$ for some integers $q$. We have the smallest $k$ by setting $q=1$. Follows that $k = n/d$, and thus there is a unique subgroup with order $d$, which is generated by the generator $g^k$.

$-$

Proposition. Given a cyclic group $G$ of order $n$, the number of elements in $G$ is equal to $\sum_{d|n} \phi(d)$

Proof. For each divisor $d$ of $n$, let $E_d$ be the set of elements in $G$ that have order $d$. By definition, the number of elements in $G$ with order $d$ is given by $\phi(d)$. Thus we can partition the elements of $G$ based on their order.

$-$

Proposition. If $p$ is prime then $\Z_p^*$ is cyclic.

Proof. For the previous proposition $\sum_{d|(p-1)} \phi(d) = p-1$. Since $\phi(d)$ counts the number of elements of each order ad their sum over all divisors of $p-1$ is exactly $p-1$, at least one of these $\phi(d)$ must correspond to $d = p-1$.