Cyclic Group

algebra

Definition

Cyclic Group

A cyclic group is a group $(G,\circ )$ that can be generated by a single element. There exists an element $g\in G$, called a generator, such that every element $x\in G$ can be written as a power (or multiple) of $g$:

$$G=⟨g⟩=\{g^n\mid n\in \mathbb{Z}\}$$

where $g^n$ denotes the $n$-fold application of the group operation.

Finite and Infinite Cyclic Groups

Finite Cyclic Groups

If $G$ has finite order $n$, then $G$ is isomorphic to the additive group of integers modulo $n$:

$$G\cong ({\mathbb{Z}}_n,+)$$

The generator $g$ satisfies $g^n=e$, and the elements are $\{e,g,g^2,\dots ,g^{n-1}\}$.

Infinite Cyclic Groups

If $G$ has infinite order, then $G$ is isomorphic to the additive group of integers:

$$G\cong (\mathbb{Z},+)$$

Properties

Abelian

Every cyclic group is abelian.

Proof. Let $G=⟨g⟩$ and let $x,y\in G$. Then $x=g^m$ and $y=g^n$ for some $m,n\in \mathbb{Z}$. Hence

$$x\circ y=g^m\circ g^n=g^{m+n}=g^{n+m}=g^n\circ g^m=y\circ x.$$

Subgroups

Every subgroup of a cyclic group is cyclic.

If $G=⟨g⟩$ has finite order $n$, then for each divisor $d$ of $n$ there exists exactly one subgroup of order $d$, namely $⟨g^{n/d}⟩$.

Generators

Let $G=⟨g⟩$ be a finite cyclic group of order $n$. An element $g^k$ is a generator of $G$ iff $k$ and $n$ are coprime.

Consequently, the number of distinct generators of $G$ is $\phi (n)$, where $\phi$ denotes Euler’s totient function.

Examples

Integers Modulo n

$({\mathbb{Z}}_n,+)$ is cyclic for every $n\ge 1$. The element $1$ is always a generator.

Multiplicative Group of a Finite Field

For a prime $p$, the multiplicative group $({\mathbb{Z}}_p^{\ast },\cdot )$ is cyclic of order $p-1$. Its generators are exactly the primitive roots modulo $p$.

Trivial Group

The group $\{e\}$ consisting of only the identity element is cyclic, generated by $e$.

Relation to Discrete Logarithm

Discrete Logarithm

In a finite cyclic group $G=⟨g⟩$ of order $q$, every element $h\in G$ can be written uniquely as $h=g^x$ for some $x\in \{0,1,\dots ,q-1\}$. The exponent $x$ is the discrete logarithm of $h$ with respect to $g$. This underlies the security of Diffie-Hellman and ElGamal.