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 :

(31.29)

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

i	0	1	2	3	4	5	6	7	8	9	10	11
3ⁱ mod 7	1	3	2	6	4	5	1	3	2	6	4	5

whereas the powers of 2 modulo 7 are

i	0	1	2	3	4	5	6	7	8	9	10	11
2ⁱ mod 7	1	2	4	1	2	4	1	2	4	1	2	4

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 in . For example, <2> = {1, 2, 4} in , and ord₇(2) = 3. Using the definition of the Euler phi function φ(n) as the size of (see 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,

g^x	≡	g^y+kφ(n)	(mod n)
	≡	g^y · (g^φ(n))k	(mod n)
	≡	g^y · 1^k	(mod n)	(by Euler's theorem)
	≡	g^y	(mod n).

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

(31.30)

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

Proof Let n = p^e. Theorem 31.32 implies that has a primitive root g. Equation (31.30) can be written

(31.31)

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

(31.32)

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 Theorem 31.34 will be used in the correctness proof for the Miller-Rabin primality-testing procedure in 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 <b_k, b_k-1, ..., b₀> be the binary representation of b
 4  for i ← k downto 0
 5        do c ← 2c
 6                  d ← (d · d) mod n
 7                  if b_i = 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.

i	9	8	7	6	5	4	3	2	1	0

b_i	1	0	0	0	1	1	0	0	0	0
c	1	2	4	8	17	35	70	140	280	560
d	7	49	157	526	160	241	298	166	67	1

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,

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
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.