|
|
< Day Day Up > |
|
We now consider the problem of finding solutions to the equation
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). There may be zero, one, or more than one such solution.
Let 〈a〉 denote the subgroup of Zn generated by a. Since 〈a〉 = {a(x) : x > 0} = {ax mod n : x > 0}, 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〉.
 |
For any positive integers a and n, if d = gcd(a, n), then
in Zn, 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.
|
|
The equation ax ≡ b (mod n) is solvable for the unknown x if and only if gcd(a, n) | b.
|
|
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).
|
|
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 x0, where
x0 = x′(b/d) mod n.
Proof We have
|
ax0 |
≡ |
ax′(b/d) |
(mod n) | |
|
≡ |
d(b/d) |
(mod n) |
(because ax′ ≡ d (mod n)) |
|
|
≡ |
b |
(mod n), |
and thus x0 is a solution to ax ≡ b (mod n).
|
|
Suppose that the equation ax ≡ b (mod n) is solvable (that is, d | b, where d = gcd(a, n)) and that x0 is any solution to this equation. Then, this equation has exactly d distinct solutions, modulo n, given by xi = x0 + 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 x0, x1, ..., xd-1 are all distinct, modulo n. Since x0 is a solution of ax ≡ b (mod n), we have ax0 mod n = b. Thus, for i = 0, 1, ..., d - 1, we have
|
axi mod n |
= |
a(x0 + in/d) mod n | |
|
= |
(ax0 + ain/d) mod n | ||
|
= |
ax0 mod n |
(because d | a) |
|
|
= |
b, |
and so xi is a solution, too. By Corollary 31.22, there are exactly d solutions, so that x0, x1, ..., xd-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 x0 = (-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 x0 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 x0 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.
|
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.
|
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.
|
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.
|
|
Consider the following change to line 3 of the procedure MODULAR-LINEAR-EQUATION-SOLVER:
3 then x0 ← x′(b/d) mod (n/d)
|
Will this work? Explain why or why not.
|
Let f(x) ≡ f0 + f1x + ··· + ft xt (mod p) be a polynomial of degree t, with coefficients fi drawn from Zp, where p is prime. We say that a ∈ Zp 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.
|
|
|
< Day Day Up > |
|
