Page 305 - Discrete Mathematics and Its Applications

284 4 / Number Theory and Cryptography

EXAMPLE 12 Determine whether 2 and 3 are primitive roots modulo 11.

3
2
1
4
Solution: When we compute the powers of 2 in Z 11 , we obtain 2 = 2, 2 = 4, 2 = 8, 2 = 5,
6
7
8
9
5
2 = 10, 2 = 9, 2 = 7, 2 = 3, 2 = 6, 2 10 = 1. Because every element of Z 11 is a power of
2, 2 is a primitive root of 11.
3
2
4
1
When we compute the powers of 3 modulo 11, we obtain 3 = 3, 3 = 9, 3 = 5, 3 = 4,
5
3 = 1. We note that this pattern repeats when we compute higher powers of 3. Because not all
elements of Z 11 are powers of 3, we conclude that 3 is not a primitive root of 11. ▲
An important fact in number theory is that there is a primitive root modulo p for every
prime p. We refer the reader to [Ro10] for a proof of this fact. Suppose that p is prime and r is
a primitive root modulo p.If a is an integer between 1 and p − 1, that is, an element of Z p ,we
e
e
know that there is an unique exponent e such that r = a in Z p , that is, r mod p = a.
DEFINITION 4 Suppose that p is a prime, r is a primitive root modulo p, and a is an integer between 1 and
e
p − 1 inclusive. If r mod p = a and 0 ≤ e ≤ p − 1, we say that e is the discrete logarithm
of a modulo p to the base r and we write log a = e (where the prime p is understood).
r
EXAMPLE 13 Find the discrete logarithms of 3 and 5 modulo 11 to the base 2.
8
Solution: When we computed the powers of 2 modulo 11 in Example 12, we found that 2 = 3
4
and 2 = 5in Z 11 . Hence, the discrete logarithms of 3 and 5 modulo 11 to the base 2 are 8
and 4, respectively. (These are the powers of 2 that equal 3 and 5, respectively, in Z 11 .) We write
log 3 = 8 and log 5 = 4 (where the modulus 11 is understood and not explicitly noted in the
2 2
notation). ▲
The discrete logarithm The discrete logarithm problem takes as input a prime p, a primitive root r modulo p,
problem is hard! and a positive integer a ∈ Z p ; its output is the discrete logarithm of a modulo p to the base
r. Although this problem might seem not to be that difficult, it turns out that no polynomial
time algorithm is known for solving it. The difficulty of this problem plays an important role in
cryptography, as we will see in Section 4.6
Exercises

1. Show that 15 is an inverse of 7 modulo 26. c) a = 144, m = 233
2. Show that 937 is an inverse of 13 modulo 2436. d) a = 200, m = 1001
∗ 7. Show that if a and m are relatively prime positive inte-
3. By inspection (as discussed prior to Example 1), find an
gers, then the inverse of a modulo m is unique modulo
inverse of 4 modulo 9.
m.[Hint: Assume that there are two solutions b and c
4. By inspection (as discussed prior to Example 1), find an of the congruence ax ≡ 1 (mod m). Use Theorem 7 of
inverse of 2 modulo 17.
Section 4.3 to show that b ≡ c(mod m).]
5. Find an inverse of a modulo m for each of these pairs 8. Show that an inverse of a modulo m, where a is an in-
of relatively prime integers using the method followed in teger and m> 2 is a positive integer, does not exist if
Example 2. gcd(a, m) > 1.
a) a = 4, m = 9 9. Solve the congruence 4x ≡ 5 (mod 9) using the inverse
b) a = 19, m = 141 of 4 modulo 9 found in part (a) of Exercise 5.
c) a = 55, m = 89 10. Solve the congruence 2x ≡ 7 (mod 17) using the inverse
d) a = 89, m = 232 of 2 modulo 7 found in part (a) of Exercise 6.
6. Find an inverse of a modulo m for each of these pairs 11. Solve each of these congruences using the modular in-
of relatively prime integers using the method followed in verses found in parts (b), (c), and (d) of Exercise 5.
Example 2. a) 19x ≡ 4 (mod 141)
a) a = 2, m = 17 b) 55x ≡ 34 (mod 89)
b) a = 34, m = 89 c) 89x ≡ 2 (mod 232)