Section15.1Exponentiation 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.4.1, 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.

Definition15.1.1.

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

1. We set $$\gexp{b}{0}{\star}=e$$ where $$e\in G$$ is the identity of the group $$(G,\star)\text{.}$$

2. 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.4.6 and Theorem 1.4.7 also hold for powers of group elements:

Both statements are proven by counting the number of copies of the base $$b$$ when rewriting the powers according to Definition 15.1.1.

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*}
2. \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.4.5 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.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.4.14.

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

1. $$\gexp{1}{0}{\otimes}=1$$ by Definition 15.1.1 Item 1

2. $$\gexp{2}{0}{\otimes}=1$$ by Definition 15.1.1 Item 1

3. $$\gexp{2}{1}{\otimes}=2$$ by Definition 15.1.1 Item 2

4. $$\gexp{2}{2}{\otimes}=2\otimes 2= (2\cdot 2) \bmod 11 = 4 \bmod 11 = 4$$ by Definition 15.1.1 Item 2

5. $$\gexp{2}{3}{\otimes}=2\otimes 2\otimes 2=(2\cdot 2\cdot 2) \bmod 11 = 8 \bmod 11 = 8$$ by Definition 15.1.1 Item 2

6. $$\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.1 Item 2

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

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.

1. 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.1.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{.}$$

2. We compute $$6^8$$ in the integers and the compute the result $$\fmod 11\text{.}$$

\begin{equation*} 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.1.4 Item 1, where we essentially follow Definition 15.1.1, is called naive exponentiation. This is the strategy that we already had used in Algorithm 2.6.1 for computing powers of integers. Replacing the multiplication of integers by the group operation we obtain a naive exponentiation algorithm for group elements.

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

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

In the Diffie Hellman Key Exchange:

Alice and Bob agree on a prime number p and a generator g for the group ({1,2,3,...,p-1},*) where a*b = (a$$\cdot$$b) mod p. We write g^c for $$g^{c*}\text{.}$$

Bob chooses an element b in {1,2,3,...,p-1} and computes B :=

• select

• g*a

• g*b

• g^a

• g^b

• g^p

• A^b

• B^a

.

Alices chooses an element a in {1,2,3,...,p-1} and computes A :=

• select

• g*a

• g*b

• g^a

• g^b

• g^p

• A^b

• B^a

.

Bob sends

• select

• a

• b

• g

• p

• A

• B

to Alice.

Alice sends

• select

• a

• b

• g

• p

• A

• B

to Bob.

• select

• a

• b

• g

• p

• A

• B

from Bob.

• select

• a

• b

• g

• p

• A

• B

from Alice

Bob computes the shared secret

• select

• g*a

• g*b

• g^a

• g^b

• g^p

• A^b

• B^a

.

Alice computes the shared secret

• select

• g*a

• g*b

• g^a

• g^b

• g^p

• A^b

• B^a

.

$${\verb!g^b!}$$

$${\verb!g^a!}$$

$$\text{B}$$

$$\text{A}$$

$$\text{B}$$

$$\text{A}$$
$${\verb!A^b!}$$
$${\verb!B^a!}$$