# 31.6 Powers of an element

## 31.6-1

Draw a table showing the order of every element in $\mathbb Z_{11}^*$. Pick the smallest primitive root $g$ and compute a table giving $\text{ind}_{11, g}(x)$ for all $x \in \mathbb Z_{11}^*$.

$g = 2$, $\{1, 2, 4, 8, 5, 10, 9, 7, 3, 6\}$.

## 31.6-2

Give a modular exponentiation algorithm that examines the bits of $b$ from right to left instead of left to right.

 1 2 3 4 5 6 7 8 9 MODULAR-EXPONENTIATION(a, b, n) i = 0 d = 1 while (1 << i) ≤ b if (b & (1 << i)) > 0 d = (d * a) % n a = (a * a) % n i = i + 1 return d 

## 31.6-3

Assuming that you know $\phi(n)$, explain how to compute $a^{-1} \mod n$ for any $a \in \mathbb Z_n^*$ using the procedure $\text{MODULAR-EXPONENTIATION}$.

$$\begin{array}{rlll} a^{\phi(n)} & \equiv & 1 & (\mod n), \\ a\cdot a^{\phi(n) - 1} & \equiv & 1 & (\mod n), \\ a^{-1} & \equiv & a^{\phi(n)-1} & (\mod n). \end{array}$$