Introduction To Algorithms 2Nd Edition Incl Exercises Edition [Electronic resources]

31.6 Powers of an element

Just as it is natural to consider the multiples of a given element a, modulo n, it is often natural to consider the sequence of powers of a, modulo n, where :

modulo n. Indexing from 0, the 0th value in this sequence is a⁰ mod n = 1, and the ith value is aⁱ mod n. For example, the powers of 3 modulo 7 are

whereas the powers of 2 modulo 7 are

In this section, let 〈a〉 denote the subgroup of generated by a by repeated multiplication, and let ord_n(a) (the "order of a, modulo n") denote the order of a Section 31.3), we now translate Corollary 31.19 into the notation of to obtain Euler's theorem and specialize it to , where p is prime, to obtain Fermat's theorem.

Theorem 31.30: (Euler's theorem)

For any integer n > 1,

Theorem 31.31: (Fermat's theorem)

If p is prime, then

Proof By equation (31.20), φ(p) = p - 1 if p is prime.

This corollary applies to every element in Z_p except 0, since . For all a ∈ Z_p, however, we have a^p ≡ a (mod p) if p is prime.

If , then every element in is a power of g, modulo n, and we say that g is a primitive root or a generator of . For example, 3 is a primitive root, modulo 7, but 2 is not a primitive root, modulo 7. If possesses a primitive root, we say that the group is cyclic. We omit the proof of the following theorem, which is proven by Niven and Zuckerman [231].

Theorem 31.32

The values of n > 1 for which is cyclic are 2, 4, p^e, and 2p^e, for all primes p > 2 and all positive integers e.

If g is a primitive root of and a is any element of , then there exists a z such that g^z ≡ a (mod n). This z is called the discrete logarithm or index of a, modulo n, to the base g; we denote this value as ind_n,g(a).

Theorem 31.33: (Discrete logarithm theorem)

If g is a primitive root of , then the equation g^x ≡ g^y (mod n) holds if and only if the equation x ≡ y (mod φ(n)) holds.

Proof Suppose first that x ≡ y (mod φ(n)). Then, x = y + kφ(n) for some integer k. Therefore,

Conversely, suppose that g^x ≡ g^y (mod n). Because the sequence of powers of g generates every element of 〈g〉 and |〈g〉| = φ(n), Corollary 31.18 implies that the sequence of powers of g is periodic with period φ(n). Therefore, if g^x ≡ g^y (mod n), then we must have x ≡ y (mod φ(n)).

Taking discrete logarithms can sometimes simplify reasoning about a modular equation, as illustrated in the proof of the following theorem.

Theorem 31.34

If p is an odd prime and e ≥ 1, then the equation

has only two solutions, namely x = 1 and x = -1.

Proof Let n = p^e. Equation (31.30) can be written

After noting that ind_n,g(1) = 0, we observe that equation (31.31) is equivalent to

To solve this equation for the unknown ind_n,g(x), we apply the methods of Section 31.4. By equation (31.19), we have φ(n) = p^e(1 - 1/p) = (p - 1)p^e-1. Letting d = gcd(2, φ(n)) = gcd(2, (p - 1) p^e-1) = 2, and noting that d | 0, we find from Theorem 31.24 that equation (31.32) has exactly d = 2 solutions. Therefore, equation (31.30) has exactly 2 solutions, which are x = 1 and x = -1 by inspection.

A number x is a nontrivial square root of 1, modulo n, if it satisfies the equation x² ≡ 1 (mod n) but x is equivalent to neither of the two "trivial" square roots: 1 or -1, modulo n. For example, 6 is a nontrivial square root of 1, modulo 35. The following corollary to Section 31.8.

Corollary 31.35

If there exists a nontrivial square root of 1, modulo n, then n is composite.

Proof By the contrapositive of Theorem 31.34, if there exists a nontrivial square root of 1, modulo n, then n can't be an odd prime or a power of an odd prime. If x² ≡ 1 (mod 2), then x ≡ 1 (mod 2), so all square roots of 1, modulo 2, are trivial. Thus, n cannot be prime. Finally, we must have n > 1 for a nontrivial square root of 1 to exist. Therefore, n must be composite.

Raising to powers with repeated squaring

A frequently occurring operation in number-theoretic computations is raising one number to a power modulo another number, also known as modular exponentiation. More precisely, we would like an efficient way to compute a^b mod n, where a and b are nonnegative integers and n is a positive integer. Modular exponentiation is an essential operation in many primality-testing routines and in the RSA public-key cryptosystem. The method of repeated squaring solves this problem efficiently using the binary representation of b.

Let 〈b_k, b_k-1, ..., b₁, b₀〉 be the binary representation of b. (That is, the binary representation is k + 1 bits long, b_k is the most significant bit, and b₀ is the least significant bit.) The following procedure computes a^c mod n as c is increased by doublings and incrementations from 0 to b.

MODULAR-EXPONENTIATION(a, b, n)
1  c ← 0
2  d ← 1
3  let 〈bk, bk-1, ..., b0〉 be the binary representation of b
4  for i ← k downto 0
5        do c ← 2c
6                  d ← (d · d) mod n
7                  if bi = 1
8                            then c ← c + 1
9                                   d ← (d · a) mod n
10  return d

The essential use of squaring in line 6 of each iteration explains the name "repeated squaring." As an example, for a = 7, b = 560, and n = 561, the algorithm computes the sequence of values modulo 561 shown in Figure 31.4; the sequence of exponents used is shown in the row of the table labeled by c.

Figure 31.4: The results of MODULAR-EXPONENTIATION when computing a^b (mod n), where a = 7, b = 560 = 〈1000110000〉, and n = 561. The values are shown after each execution of the for loop. The final result is 1.

The variable c is not really needed by the algorithm but is included for explanatory purposes; the algorithm maintains the following two-part loop invariant:

Just prior to each iteration of the for loop of lines 4-9,

1. The value of c is the same as the prefix 〈b_k, b_k-1, ..., b_i+1〉 of the binary representation of b, and

2. d = a^c mod n.

We use this loop invariant as follows:

• Initialization: Initially, i = k, so that the prefix 〈b_k, b_k-1, ..., b_i+1〉 is empty, which corresponds to c = 0. Moreover, d = 1 = a⁰ mod n.

• Maintenance: Let c′ and d′ denote the values of c and d at the end of an iteration of the for loop, and thus the values prior to the next iteration. Each iteration updates c′ ← 2c (if b_i = 0) or c′ ← 2c + 1 (if b_i = 1), so that c will be correct prior to the next iteration. If b_i = 0, then d′ = d² mod n = (a^c)² mod n = a^2c mod mod n. If b_i = 1, then d′ = d² a mod n = (a^c)²a mod n =a^2c+1 mod mod n. In either case, d = a^c mod n prior to the next iteration.

• Termination: At termination, i = -1. Thus, c = b, since c has the value of the prefix 〈b_k, b_k-1, ...,b₀〉 of b′s binary representation. Hence d = a^c mod n = a^b mod n.

If the inputs a, b, and n are β-bit numbers, then the total number of arithmetic operations required is O(β) and the total number of bit operations required is O(β³).

Exercises 31.6-1

Draw a table showing the order of every element in . Pick the smallest primitive root g and compute a table giving ind_11,g(x) for all .

Exercises 31.6-2

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

Exercises 31.6-3

Assuming that you know φ (n), explain how to compute a^-1 mod n for any using the procedure MODULAR-EXPONENTIATION.