# 14.1: Cyclic Groups

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

Definition $$\PageIndex{1}$$

Let g ∈ ℤn. Define ⟨g⟩n = {gi % n| i ∈ ℤ}, the set of all powers of g reduced mod n. Then g is called a generator of ⟨g⟩n, and ⟨g⟩n is called the cyclic group generated by g mod n.

Ifgn = ℤn , then we say that g is a primitive root mod n.

The definition allows the generator g to be raised to a negative integer. Since g ∈ ℤn, it is guaranteed that g has a multiplicative inverse mod n, which we can call g−1. Then g−i can be defined as g−i ≝ (g−1)i. All of the usual laws of exponents hold with respect to this definition of negative exponents.

Example $$\PageIndex{1}$$:

Taking n = 13, we have: Thus 2 is a primitive root modulo 13. Each of the groups {1}, ℤ13, {1,3,9} is a cyclic group under multiplication mod 13.

A cyclic group may have more than one generator, for example: Similarly, there are four primitive roots modulo 13 (equivalently,13 has four different generators); they are 2, 6, 7, and 11.

Not every integer has a primitive root. For example, there is no primitive root modulo 15. However, when p is a prime, there is always a primitive root modulo p (and so ℤp is a cyclic group).

Let us write ? = ⟨g⟩ = {gi | i ∈ ℤ} to denote an unspecified cyclic group generated by g. The defining property of ? is that each of its elements can be written as a power of g. From this we can conclude that:

• Any cyclic group is closed under multiplication. That is, take any X,Y∈ ?; then it must be possible to write X = gx and Y = gy for some integers x,y. Using the multiplication operation of ?, the product is XY= gx+y, which is also in ?.
• Any cyclic group is closed under inverses. Take any X ∈ ?; then it must be possible to write X = gx for some integer x. We can then see that gx ∈ ? by definition, and gxX = gx+x = g0 is the identity element. So X has a multiplicative inverse (gx) in ?.

These facts demonstrate that ? is indeed a group in the terminology of abstract algebra.

Discrete Logarithms

It is typically easy to compute the value of gx in a cyclic group, given gand x. For example, when using a cyclic group of the form ℤn, we can easily compute the modular exponentiation gx % n using repeated squaring.

The inverse operation in a cyclic group is called the discrete logarithm problem

Definition $$\PageIndex{2}$$

The discrete logarithm problem is: given X ∈ ⟨g⟩, determine a number x such that gx = X. Here the exponentiation is with respect to the multiplication operation in ? = ⟨g⟩.

The discrete logarithm problem is conjectured to hard (that is, no polynomial-time algorithm exists for the problem) in certain kinds of cyclic groups.

14.1: Cyclic Groups is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Mike Rosulek.