# Cyclic Groups

Created:
2023-08-23

Updated:
2023-12-17

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

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

$-$

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