Skip to main content
[ "article:topic", "showtoc:no", "license:ccbync", "authorname:mrosulek" ]
Engineering LibreTexts

14.1: Cyclic Groups

  • Page ID
    7404
  • Definition \(\PageIndex{1}\)

    Let g ∈ ℤn. Define ⟨g⟩n = {gi % ni ∈ ℤ}, the set of all powers of 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 ⟨gn = ℤ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 XYgx+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.