Introduction To Algorithms 2Nd Edition Incl Exercises Edition [Electronic resources] نسخه متنی

31.4 Solving modular linear equations

We now consider the problem of finding solutions to the equation

(31.21)

where a > 0 and n > 0. There are several applications for this problem; for example, we will use it as part of the procedure for finding keys in the RSA public-key cryptosystem in Section 31.7. We assume that a, b, and n are given, and we are to find all values of x, modulo n, that satisfy equation (31.21) has a solution if and only if b ∈ 〈a〉. Lagrange's theorem (Theorem 31.15) tells us that |〈a〉| must be a divisor of n. The following theorem gives us a precise characterization of 〈a〉.

Theorem 31.20

For any positive integers a and n, if d = gcd(a, n), then

(31.22)

in Z_n, and thus

|〈a〉| = n/d.

Proof We begin by showing that d ∈ 〈a〉. Recall that EXTENDED-EUCLID(a, n) produces integers x′ and y′ such that ax′ + ny′ = d. Thus, ax′ ≡ d (mod n), so that d ∈ 〈a〉.

Since d ∈ 〈a〉, it follows that every multiple of d belongs to 〈a〉, because any multiple of a multiple of a is itself a multiple of a. Thus, 〈a〉 contains every element in {0, d, 2d, ..., ((n/d) - 1)d}. That is, 〈d〉 ⊆ 〈a〉.

We now show that 〈a〉 ⊆ 〈d〉. If m ∈ 〈a〉, then m = ax mod n for some integer x, and so m = ax + ny for some integer y. However, d | a and d | n, and so d | m by equation (31.4). Therefore, m ∈ 〈d〉.

Combining these results, we have that 〈a〉 = 〈d〉. To see that |〈a〉| = n/d, observe that there are exactly n/d multiples of d between 0 and n - 1, inclusive.

Corollary 31.21

The equation ax ≡ b (mod n) is solvable for the unknown x if and only if gcd(a, n) | b.

Corollary 31.22

The equation ax ≡ b (mod n) either has d distinct solutions modulo n, where d = gcd(a, n), or it has no solutions.

Proof If ax ≡ b (mod n) has a solution, then b ∈ 〈a〉. By Theorem 31.17, ord(a) = |〈a〉|, and so Corollary 31.18 and Theorem 31.20 imply that the sequence ai mod n, for i = 0, 1, ..., is periodic with period |〈a〉| = n/d. If b ∈ 〈a〉, then b appears exactly d times in the sequence ai mod n, for i = 0, 1, ..., n - 1, since the length-(n/d) block of values 〈a〉 is repeated exactly d times as i increases from 0 to n - 1. The indices x of the d positions for which ax mod n = b are the solutions of the equation ax ≡ b (mod n).

Theorem 31.23

Let d = gcd(a, n), and suppose that d = ax′ + ny′ for some integers x′ and y′ (for example, as computed by EXTENDED-EUCLID). If d | b, then the equation ax ≡ b (mod n) has as one of its solutions the value x₀, where

x₀ = x′(b/d) mod n.

Proof We have

and thus x₀ is a solution to ax ≡ b (mod n).

Theorem 31.24

Suppose that the equation ax ≡ b (mod n) is solvable (that is, d | b, where d = gcd(a, n)) and that x₀ is any solution to this equation. Then, this equation has exactly d distinct solutions, modulo n, given by x_i = x₀ + i(n/d) for i = 0, 1, ..., d - 1.

Proof Since n/d > 0 and 0 ≤ i(n/d) < n for i = 0, 1, ..., d - 1, the values x₀, x₁, ..., x_d-1 are all distinct, modulo n. Since x₀ is a solution of ax ≡ b (mod n), we have ax₀ mod n = b. Thus, for i = 0, 1, ..., d - 1, we have

and so x_i is a solution, too. By Corollary 31.22, there are exactly d solutions, so that x₀, x₁, ..., x_d-1 must be all of them.

We have now developed the mathematics needed to solve the equation ax ≡ b (mod n); the following algorithm prints all solutions to this equation. The inputs a and n are arbitrary positive integers, and b is an arbitrary integer.

MODULAR-LINEAR-EQUATION-SOLVER(a, b, n)
1  (d, x′, y′) ← EXTENDED-EUCLID(a, n)
2  if d | b
3      then x0 ← x′(b/d) mod n
4           for i ← 0 to d - 1
5                do print (x0 + i(n/d)) mod n
6      else print "no solutions"

As an example of the operation of this procedure, consider the equation 14x ≡ 30 (mod 100) (here, a = 14, b = 30, and n = 100). Calling EXTENDED-EUCLID in line 1, we obtain (d, x, y) = (2, -7, 1). Since 2 | 30, lines 3-5 are executed. In line 3, we compute x₀ = (-7)(15) mod 100 = 95. The loop on lines 4-5 prints the two solutions 95 and 45.

The procedure MODULAR-LINEAR-EQUATION-SOLVER works as follows. Line 1 computes d = gcd(a, n) as well as two values x′ and y′ such that d = ax′+ny′, demonstrating that x′ is a solution to the equation ax′ ≡ d (mod n). If d does not divide b, then the equation ax ≡ b (mod n) has no solution, by Corollary 31.21. Line 2 checks if d | b; if not, line 6 reports that there are no solutions. Otherwise, line 3 computes a solution x₀ to ax ≡ b (mod n), in accordance with Theorem 31.23. Given one solution, Theorem 31.24 states that the other d - 1 solutions can be obtained by adding multiples of (n/d), modulo n. The for loop of lines 4-5 prints out all d solutions, beginning with x₀ and spaced (n/d) apart, modulo n.

MODULAR-LINEAR-EQUATION-SOLVER performs O(lg n + gcd(a, n)) arithmetic operations, since EXTENDED-EUCLID performs O(lg n) arithmetic operations, and each iteration of the for loop of lines 4-5 performs a constant number of arithmetic operations.

The following corollaries of Theorem 31.24 give specializations of particular interest.

Corollary 31.25

For any n > 1, if gcd(a, n) = 1, then the equation ax ≡ b (mod n) has a unique solution, modulo n.

If b = 1, a common case of considerable interest, the x we are looking for is a multiplicative inverse of a, modulo n.

Corollary 31.26

For any n > 1, if gcd(a, n) = 1, then the equation ax ≡ 1 (mod n) has a unique solution, modulo n. Otherwise, it has no solution.

Corollary 31.26 allows us to use the notation (a^-1 mod n) to refer to the multiplicative inverse of a, modulo n, when a and n are relatively prime. If gcd(a, n) = 1, then one solution to the equation ax ≡ 1 (mod n) is the integer x returned by EXTENDED-EUCLID, since the equation

gcd(a, n) = 1 = ax + ny

implies ax ≡ 1 (mod n). Thus, we can compute (a^-1 mod n) efficiently using EXTENDED-EUCLID.

Exercises 31.4-1

Find all solutions to the equation 35x ≡ 10 (mod 50).

Exercises 31.4-2

Prove that the equation ax ≡ ay (mod n) implies x ≡ y (mod n) whenever gcd(a, n) = 1. Show that the condition gcd(a, n) = 1 is necessary by supplying a counterexample with gcd(a, n) > 1.

Exercises 31.4-3

Consider the following change to line 3 of the procedure MODULAR-LINEAR-EQUATION-SOLVER:

3 then x₀ ← x′(b/d) mod (n/d)

Will this work? Explain why or why not.

Exercises 31.4-4: ★

Let f(x) ≡ f₀ + f₁x + ··· + f_t x^t (mod p) be a polynomial of degree t, with coefficients f_i drawn from Z_p, where p is prime. We say that a ∈ Z_p is a zero of f if f(a) ≡ 0 (mod p). Prove that if a is a zero of f, then f(x) ≡ (x - a)g(x) (mod p) for some polynomial g(x) of degree t - 1. Prove by induction on t that a polynomial f(x) of degree t can have at most t distinct zeros modulo a prime p.