14.1: Cyclic Groups
- Page ID
- 7404
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.
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−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 g−x ∈ ? by definition, and g−xX = g−x+x = g0 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 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.