# Cyclic Groups

Created:
2023-08-23

Updated:
2023-12-17

A cyclic group 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 ∈ G`

is defined as:

```
ord(a) := min{i ∈ Zₙ} such that aⁱ = e
```

Where `aⁱ`

represents the repeated application of the group operation to `a`

.

**Definition**. A group `G`

is said to be **cyclic** if there exist at least
one element `g ∈ 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 ∈ G`

is a **generator** of `G`

if `ord(g) = |G|`

.

**Proposition**. If `g`

is a generator of `G`

then `{g¹, .. , gᴳ}`

are
all distinct.

*Proof*

For two exponents `0 ≤ i < j < |G|`

, we set `r = j - i < |G|`

. If `gⁱ ≡ gʲ`

then
`gⁱ = gⁱ⁺ʳ = gⁱ·gʳ`

. Given that `g`

is invertible then we can cancel `gⁱ`

on
both sides leaving with `1 ≡ gʳ`

. But then `g`

is not a generator as `r < |G|`

.

∎

In this discussion we’re going to mostly focus on groups
`Zₙ* = { x: x < n and gcd(x,n) = 1 }`

defined by the group operation product
modulo `n`

.

*Example*. Given `p = 19`

we know that `Zp*`

is a group with respect to the
product modulo `p`

and that `|Zp*| = 18`

```
a = 7 → 7¹ mod 19 = 7, ..., 7³ mod 19 = 1 → ord(7) = 3
a = 2 → 2¹ mod 19 = 2, ..., 2¹⁸ mod 19 = 1 → ord(2) = 18
```

For *Euler*’s theorem, if `(a,n) = 1`

then `α^φ(n) = 1`

, however the order of an
element `α`

can be smaller that `φ(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ᵐ`

is equal to `n/(m,n)`

.

*Proof*

We are looking for the smaller `k`

such that `(gᵐ)ᵏ = 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ᵐ`

is another
generator iff `(m,n) = 1`

.

*Proof* According to the previous proposition `gᵐ`

has order `n/(m,n) = n`

.

*Alt* (← direct): `(m,n) = 1 → 1 = m·s + n·t → g = g^(m·s + n·t) = (gᵐ)ˢ`

.
Given that `gᵐ`

generates `g`

, then it generates the whole `G`

.

**Corollary**. The number of different generators in `|G|`

is `φ(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 the original group.

The identity of `G`

is also the identity of `H`

.

## Lagrange theorem

### Cosets

A subgroup `H`

of a group `G`

may be used to decompose the underlying set of `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.

There are left cosets and right cosets. Cosets have the same number of elements
as does `H`

. 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 ∈ H`

.

**Proposition**. Two cosets are either disjoint or equal.

*Proof*. Given two cosets `a·H`

and `b·H`

. If `c = a·hᵢ = b·hⱼ`

, then for any
`a·h' ∈ a·H`

given that `H`

is a group we can find a `t`

such that `h' = t·hᵢ`

.
But then `a·h' = a·t·hᵢ = b·t·hⱼ`

and thus `a·H ⊆ b·H`

. For the same argument we
prove `b·H ⊆ a·H`

and thus `a·H = b·H`

.

**Lagrange Theorem**. For any finite group `G`

, the number of elements of
every subgroup of `G`

divides the order of `G`

.

*Proof*. Let `G`

order be `n`

and `H`

order be `m`

.
`G`

can be written as the union of the cosets `G = a₁·H ∪ .. ∪ aₙ·H`

.
After removal of any duplicated coset, we are left with `G = a₁·H ∪ .. ∪ aₛ·H`

with `s ≤ n`

. Given that each coset has the same number of elements of `H`

we have that `n = s·m`

.

*Alt* Using the fact that any subgroup is generated by some g^m and that
the order of g^m = n/(m,n). Then the order of any subgroup divides the `n`

.
That is `n/(m,n)`

clearly divides `n`

.