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}\).

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用