Skip to main content
Engineering LibreTexts

14.1: Cyclic Groups

  • 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 = {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:

    Figure14-1.jpg

    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:

    Figure14-2.jpg

    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.

    • Was this article helpful?