Exponentiation in Groups

Section 15.1 Exponentiation in Groups

Recall that \(\cdot:\Z \times \Z \to \Z\) (multiplication) is a binary operation on the set \(\Z\) of integers. We defined exponentiation as repeated multiplication. For \(a\in\Z\) and \(n\in\N\) we introduced the notation

\begin{equation*} a^n := \underbrace{a \cdot a \cdot \ldots \cdot a}_{n \text{ copies of }a } \end{equation*}

and also defined \(a^0:=1\text{.}\) We generalize this definition of powers of integers to powers of group elements.

Following the definition of powers of integers in Definition 1.54, we introduce exponentiation notation for group elements as repeated application of the group operation. To be able to distinguish exponentiation with respect to different binary operations in our notation of powers of group elements we always give the binary operation next to the exponent.

Definition 15.1.

Let \((G,\star)\) be a group and \(b\in G\text{.}\)

We set \(\gexp{b}{0}{\star}=e\) where \(e\in G\) is the identity of the group \((G,\star)\text{.}\)
For \(n\in\N\) we set \(\gexp{b}{n}{\star}=\underbrace{b\star b\star\dots\star b}_{n \text{ copies of }b}\text{.}\)

We read \(\gexp{b}{n}{\star}\) as “\(b\) to the \(n\) by \(\star\)”. We call \(b\) the base and \(n\) the exponent.

It follows from the definition that in a group \((G,\star)\) we have \(\gexp{b}{1}{\star}=b\) for all \(b\in G\text{.}\) For the identity \(e\) of any group we have \(\gexp{e}{x}{\star}=e\) for all \(x\in\W\text{.}\)

The properties of powers of integers from Theorem 1.59 and Theorem 1.60 also hold for powers of group elements:

Theorem 15.2.

Let \((G,\star)\) be a group and \(b\in G\text{.}\) Let \(m\in\N\) and \(n\in\N\text{.}\) In \((G,\star)\) we have

\(\displaystyle \displaystyle\gexp{b}{m}{\star}\star \gexp{b}{n}{\star} = \gexp{b}{(m+n)}{\star}\)
\(\displaystyle \displaystyle \gexp{(\gexp{b}{m}{\star})}{n}{\star} = \gexp{b}{(m\cdot n)}{\star}\)

Proof.

Both statements are proven by counting the number of copies of the base \(b\) when rewriting the powers according to Definition 15.1.

\begin{align*} \gexp{b}{m}{\star}\star \gexp{b}{n}{\star} \amp = \underbrace{b\star\dots\star b}_{m \text{ copies of } b } \star \underbrace{b\star\dots\star b}_{n \text{ copies of } b}\\ \amp = \underbrace{b\star\dots\star b}_{m + n \text{ copies of }b} = \gexp{b}{(m+n)}{\star} \end{align*}
\begin{align*} \gexp{(\gexp{b}{m}{\star})}{n}{\star} \amp = \underbrace{\gexp{b}{m}{\star}\star\dots\star \gexp{b}{m}{\star}}_{n \text{ copies of }\gexp{b}{m}{\star}} \\ \amp = \underbrace{\underbrace{b\star\dots\star b}_{m \text{ copies of }b } \star\dots\star \underbrace{b\star\dots\star b}_{m \text{copies of }b}}_{n\text{ copies of } \underbrace{(b\star\dots\star b)}_{m \text{ copies of }b} } \\ \amp = \underbrace{b\star\dots\star b}_{m \cdot n\text{ copies of }b} = \gexp{b}{(m\cdot n)}{\star} \end{align*}

Note that the notation of inverses with respect to binary operations in Definition 13.29 is chosen such that the properties proven above also work for negative exponents. In a group \((G,\star)\) with identity \(e\) for \(a\in G\) we have

\begin{equation*} \gexp{a}{1}{\star} \star \gexp{a}{-1}{\star} = \gexp{a}{(1 + (-1))}{\star}=\gexp{a}{0}{\star}=e\text{.} \end{equation*}

Although our definition of exponentiation works in every group we restrict our examples to the groups \((\Z_p^\otimes,\otimes)\) where \(p\) is a prime number where the operation \(\otimes:\Z_p^\otimes\times\Z_p^\otimes\to\Z_p^\otimes\) is given by \(a\otimes b=(a\cdot b)\bmod p\text{.}\)

Specializing Definition 15.1 to the group \((\Z_p^\otimes,\otimes)\) we have for all \(b\in\Z_p^\otimes\) that

\begin{equation*} \gexp{b}{0}{\otimes}=1 \end{equation*}

and for all \(b\in\Z_p^\otimes\) and all \(n\in\N\) that

\begin{equation*} \gexp{b}{n}{\otimes} =\underbrace{b\otimes b\otimes\dots\otimes b}_{n\text{ copies of }b }= (\underbrace{b\cdot b\cdot\dots\cdot b}_{n\text{ copies of }b })\fmod p= (b^n)\fmod p. \end{equation*}

The second equality above holds because of Theorem 3.50.

Example 15.3. Powers of elements of \((\Z_{11}^\otimes,\otimes)\).

In \((\Z_{11}^\otimes,\otimes)\) where \(a\otimes b=(a\cdot b)\fmod 11\) we have

\(\gexp{1}{0}{\otimes}=1\) by Definition 15.1 Item 1
\(\gexp{2}{0}{\otimes}=1\) by Definition 15.1 Item 1
\(\gexp{2}{1}{\otimes}=2\) by Definition 15.1 Item 2
\(\gexp{2}{2}{\otimes}=2\otimes 2= (2\cdot 2) \bmod 11 = 4 \bmod 11 = 4\) by Definition 15.1 Item 2
\(\gexp{2}{3}{\otimes}=2\otimes 2\otimes 2=(2\cdot 2\cdot 2) \bmod 11 = 8 \bmod 11 = 8\) by Definition 15.1 Item 2
\(\gexp{2}{4}{\otimes}=2\otimes 2\otimes 2\otimes 2=(2\cdot 2\cdot 2\cdot 2) \bmod 11=16\bmod 11 = 5\) by Definition 15.1 Item 2

When numbers become bigger the computations become easier when we compute \(\fmod\) after each multiplication.

Example 15.4. Two ways for computing \(\gexp{6}{8}{\otimes}\).

In the group \((\Z_{11}^\otimes,\otimes)\) where \(a\otimes b=(a\cdot b)\fmod 11\) we compute

\begin{equation*} \gexp{6}{8}{\otimes}=6\otimes 6\otimes6\otimes6\otimes6\otimes6\otimes6\otimes6\text{.} \end{equation*}

We use two approaches.

We directly follow the definition, that is, we repeatedly apply \(a \otimes b=(a\cdot b)\fmod 11\text{.}\) We first compute

\begin{equation*} \gexp{6}{2}{\otimes}=6\otimes 6=(6\cdot 6)\fmod 11=36 \fmod 11= 3 \end{equation*}

We now compute the other powers up to \(\gexp{6}{8}{\otimes}\) making use of the previous result. In every step we apply Theorem 15.2 Item 1.

\begin{align*} \gexp{6}{3}{\otimes}\amp =\gexp{6}{2}{\otimes}\otimes 6=3\otimes 6=(3\cdot 6)\fmod 11=18\fmod 11=7\\ \gexp{6}{4}{\otimes}\amp =\gexp{6}{3}{\otimes}\otimes 6=7\otimes 6=(7\cdot 6)\fmod 11=42\fmod 11=9\\ \gexp{6}{5}{\otimes}\amp =\gexp{6}{4}{\otimes}\otimes 6=9\otimes 6=(9\cdot 6)\fmod 11=54\fmod 11=10\\ \gexp{6}{6}{\otimes}\amp =\gexp{6}{5}{\otimes}\otimes 6=10\otimes 6=(10\cdot 6)\fmod 11=60\fmod 11=5\\ \gexp{6}{7}{\otimes}\amp =\gexp{6}{6}{\otimes}\otimes 6=5\otimes 6=(5\cdot 6)\fmod 11=30\fmod 11=8\\ \gexp{6}{8}{\otimes}\amp =\gexp{6}{7}{\otimes}\otimes 6=8\otimes 6=(8\cdot 6)\fmod 11=48\fmod 11=4 \end{align*}

We have computed \(\gexp{6}{8}{\otimes}=4\text{.}\)
We compute \(6^8\) in the integers and then compute the result \(\fmod 11\text{:}\)

\begin{equation*} \gexp{6}{2}{\otimes}=6^8\fmod 11=1679616\fmod 11=4 \end{equation*}

Note that we can easily conduct the computations in Item 1 by hand, but we would not want to compute \(6^8\) without the help of a calculator. When bases and exponents are larger, the second approach is not feasible anymore as the numbers become to large for most calculators.

Computing powers as in Example 15.4 Item 1, where we essentially follow Definition 15.1, is called naive exponentiation. This is the strategy that we already had used in Algorithm 2.44 for computing powers of integers. Replacing the multiplication of integers by the group operation we obtain a naive exponentiation algorithm for group elements.

Algorithm 15.5. Naive Exponentiation for Group Elements.

Input:: A group \((G,\star)\text{,}\) \(b\in G\text{,}\) and a non-negative integer \(n\)
Output:: \(\displaystyle \gexp{b}{n}{\star}\)

if \(n=0\) then return the identity of \((G,\star)\)
if \(n=1\) then return \(b\)
let \(c:=b\)
let \(i:=1\)
repeat
1. let \(c:=c\star b\)
2. let \(i:= i+1\)
until \(i=n\)
return \(c\)

In the video in Figure 15.6 we recall the definition of exponentiation in groups and go through the steps of the naive exponentiation algorithm in detail.

Figure 15.6. Exponentiation in Groups by Matt Farmer and Stephen Steward

Now work through computing the power of a group element in Checkpoint 15.7.

Checkpoint 15.7. Naive exponentiation.

Naive Exponentiation

With the naive exponentiation algorithm find \(3^{16}\bmod 23\text{.}\)

Input: Base \(b :=\) an exponent \(n:=\) and a modulus \(m:=\) .

let \(c:=3\) and let \(i:=1\text{.}\)

let \(c:=(c\cdot 3)\bmod 23 =\) and let \(i:=i+1 =\)

Because the statement \(i=16\) is true, the loop ends here.

Output: \(3^{16} \bmod 23 = c =\) .

Prev Top Next