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 a0 mod n = 1, and the ith value is ai mod n. For example, the powers of 3 modulo 7 are
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
3i 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 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
2i mod 7 | 1 | 2 | 4 | 1 | 2 | 4 | 1 | 2 | 4 | 1 | 2 | 4 |
In this section, let 〈a〉 denote the subgroup of



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 Zp except 0, since






The values of n > 1 for which

If g is a primitive root of


If g is a primitive root of

gx | ≡ | gy+kφ(n) | (mod n) | |
≡ | gy · (gφ(n))k | (mod n) | ||
≡ | gy · 1k | (mod n) | (by Euler's theorem) | |
≡ | gy | (mod n). |
Conversely, suppose that gx ≡ gy (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 gx ≡ gy (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 = pe. Equation (31.30) can be written
(31.31) | ![]() |
After noting that indn,g(1) = 0, we observe that equation (31.31) is equivalent to
(31.32) | ![]() |
To solve this equation for the unknown indn,g(x), we apply the methods of Section 31.4. By equation (31.19), we have φ(n) = pe(1 - 1/p) = (p - 1)pe-1. Letting d = gcd(2, φ(n)) = gcd(2, (p - 1) pe-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 x2 ≡ 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 x2 ≡ 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 ab 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 〈bk, bk-1, ..., b1, b0〉 be the binary representation of b. (That is, the binary representation is k + 1 bits long, bk is the most significant bit, and b0 is the least significant bit.) The following procedure computes ac 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.
i | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
---|---|---|---|---|---|---|---|---|---|---|
bi | 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 ab (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 〈bk, bk-1, ..., bi+1〉 of the binary representation of b, and
d = ac mod n.
We use this loop invariant as follows:
Initialization: Initially, i = k, so that the prefix 〈bk, bk-1, ..., bi+1〉 is empty, which corresponds to c = 0. Moreover, d = 1 = a0 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 bi = 0) or c′ ← 2c + 1 (if bi = 1), so that c will be correct prior to the next iteration. If bi = 0, then d′ = d2 mod n = (ac)2 mod n = a2c modmod n. If bi = 1, then d′ = d2 a mod n = (ac)2a mod n =a2c+1 mod
mod n. In either case, d = ac mod n prior to the next iteration.
Termination: At termination, i = -1. Thus, c = b, since c has the value of the prefix 〈bk, bk-1, ...,b0〉 of b′s binary representation. Hence d = ac mod n = ab 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(β3).Exercises 31.6-1
Draw a table showing the order of every element in


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
