14.1: Cyclic Groups

Last updated
Save as PDF

Page ID: 7404

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\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]{\| #1 \|}\) \( \newcommand{\inner}[2]{\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]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

Definition \(\PageIndex{1}\)

Let g ∈ ℤ^∗_n. Define ⟨g⟩n = {gⁱ % 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.

If ⟨g⟩_n = ℤ^∗_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⁻¹. Then g⁻ⁱ can be defined as g⁻ⁱ ≝ (g⁻¹)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}, ℤ^∗₁₃, {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, ℤ^∗₁₃ 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⟩ = {gⁱ | 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 = g^x and Y = g^y for some integers x,y. Using the multiplication operation of ?, the product is XY= g^x+y, which is also in ?.
Any cyclic group is closed under inverses. Take any X ∈ ?; then it must be possible to write X = g^x for some integer x. We can then see that g^−x ∈ ? by definition, and g^−xX = g^−x+x = g⁰ is the identity element. So X has a multiplicative inverse (g^−x) 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 g^x 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 g^x % 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 g^x = 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.