

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.

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} $$