# 14.1: Cyclic Groups

- Page ID
- 7404

Definition \(\PageIndex{1}\)

*Let g* ∈ ℤ^{∗}* _{n}*. Define ⟨g⟩

*n*= {

*g*|

^{i}% 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⟩ = {*g ^{i}* |

*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*and^{x}*Y*=*g*for some integers^{y}*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*for some integer^{x}*x*. We can then see that*g*^{−x}∈ ? by definition, and*g*^{−x}*X*=*g*^{−x+x}=*g*^{0}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

*g*and

*x*. For example, when using a cyclic group of the form ℤ

^{∗}

*, we can easily compute the modular exponentiation*

_{n}*g*using repeated squaring.

^{x}% nThe 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.