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.