14.1: Cyclic Groups

Definition 14.1: Term

Let \(g \in \mathbb{Z}_{n}^{*}\). Define \(\langle g\rangle_{n}=\left\{g^{i} \% n \mid i \in \mathbb{Z}\right\}\), the set of all powers of \(g\) reduced mod n. Then \(g\) is called a generator of \(\langle g\rangle_{n}\), and \(\langle g\rangle_{n}\) is called the cyclic group generated by \(g\) mod \(n\).

If \(\langle g\rangle_{n}=\mathbb{Z}_{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 \in \mathbb{Z}_{n}^{*}\), it is guaranteed that \(g\) has a multiplicative inverse \(\bmod n\), which we can call \(g^{-1}\). Then \(g^{-i}\) can be defined as \(g^{-i} \stackrel{\text { def }}{=}\left(g^{-1}\right)^{i}\). All of the usual laws of exponents hold with respect to this definition of negative exponents.

Example

Taking \(n=13\), we have:

\[\begin{aligned} &\langle 1\rangle_{13}=\{1\} \\ &\langle 2\rangle_{13}=\{1,2,4,8,3,6,12,11,9,5,10,7\}=\mathbb{Z}_{13}^{*} \\ &\langle 3\rangle_{13}=\{1,3,9\} \end{aligned}\]

Thus 2 is a primitive root modulo 13. Each of the groups \(\{1\}, \mathbb{Z}_{13}^{*},\{1,3,9\}\) is a cyclic group under multiplication mod \(13 .\)

A cyclic group may have more than one generator, for example:

\[\langle 3\rangle_{13}=\langle 9\rangle_{13}=\{1,3,9\}\]

Similarly, there are four primitive roots modulo 13 (equivalently, \(\mathbb{Z}_{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 \(\mathbb{Z}_{p}^{*}\) is a cyclic group).

Let us write \(\mathbb{G}=\langle g\rangle=\left\{g^{i} \mid i \in \mathbb{Z}\right\}\) to denote an unspecified cyclic group generated by \(g\). The defining property of \(\mathbb{G}\) 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 \in \mathbb{G} ;\) then it must be possible to write \(X=g^{x}\) and \(Y=g^{y}\) for some integers \(x, y\). Using the multiplication operation of \(\mathbb{G}\), the product is \(X Y=g^{x+y}\), which is also in \(\mathbb{G}\).
• Any cyclic group is closed under inverses. Take any \(X \in \mathbb{G} ;\) then it must be possible to write \(X=g^{x}\) for some integer \(x\). We can then see that \(g^{-x} \in \mathbb{G}\) by definition, and \(g^{-x} X=g^{-x+x}=g^{0}\) is the identity element. So \(X\) has a multiplicative inverse \(\left(g^{-x}\right)\) in \(\mathbb{G}\)

These facts demonstrate that \(\mathbb{G}\) 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 \(\mathbb{Z}_{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 \(14.2\) (Discrete Log)

The discrete logarithm problem is: given \(X \in\langle g\rangle\), determine a number \(x\) such that \(g^{x}=X\). Here the exponentiation is with respect to the multiplication operation in \(\mathbb{G}=\langle g\rangle\).

The discrete logarithm problem is conjectured to be hard (that is, no polynomial-time algorithm exists for the problem) in certain kinds of cyclic groups.