Linear Congruences, Chinese Remainder Theorem, Algorithms

Lecture 5 Linear Congruences, Chinese Remainder Theorem, Algorithms Recap - linear congruence ax ≡ b mod m has solution if and only if g = (a, m) divides b. How do we find these solutions? Case 1: g = (a, m) = 1. Then invert a mod m to get x ≡ a−1 b mod m. Al­ gorithmically, find ax0 + my0 = 1 with Euclidean Algorithm, then ax0 ≡ 1 mod m so x0 = a−1 , so x ≡ x0 b = a−1 b solves the congruence. (ax ≡ a(x0 b) ≡ (ax0 )b ≡ b mod m). Conclusion: There is a unique solution mod m. Case 2: g = (a, m) > 1. If g t b, there are no solutions. If g|b, write a = a' g, b = b' g, m = m' g so that ax ≡ b mod m ⇒ a' x = b' mod m' so that (a' , m' ) is now 1. The unique solution (found by Case 1) x mod m' also satisfied ax ≡ b mod m so that we have one solution mod m. We know any solution x̃ mod m must be congruent to x mod m' , so x̃ must have form x + m' k for some k. As k goes from 0 through g − 1 we get the g distinct integers mod m: x, x + m' , x + 2m' . . . x + (g − 1)m' , which all satisfy ax̃ ≡ b mod m because a(x + km' ) = ax + akm' = ax + a' gkm' = ax + m(a' k) ≡ ax (mod m) ≡ b (mod m) Conclusion: this congruence has g = (a, m) solutions mod m. Eg., 35x ≡ 14 (mod 28) (35, 28) = g = 7. To solve, first divide through by 7 to get 5x ≡ 2 mod 4. Solution of x ≡ 2 mod 4 is x = 2, which will also satisfy original congru­ ence. m' = 28 7 = 4 ⇒ all solutions mod 28 ≡ 2, 6, 10, 14, 18, 22, 26. Simultaneous System of Congruences to Different Moduli: Given x ≡ a1 x ≡ a2 .. . (mod m1 ) (mod m2 ) x ≡ ak (mod mk ) Does this system have a common solution? (Not always, eg., x ≡ 3 mod 8 and x ≡ 1 mod 12) In general, need some compatibility conditions. 1 Theorem 25 (Chinese Remainder Theorem). If the moduli are coprime in pairs (ie., (mi , mj ) = 1 for i = j), then the system has a unique solution mod m1 m2 . . . mk . Proof of Uniqueness. Suppose there are two solutions x ≡ y ≡ a1 mod m1 , x ≡ y ≡ a2 mod m2 , etc. Then m1 |(x − y), m2 |(x − y), etc. Since m’s are relatively prime in pairs, their product m1 m2 . . . mk divides x − y as well, so x ≡ y mod m1 m2 . . . mk . So solution, if exists, must be unique mod m1 m2 . . . mk . • Proof of Existence. Write solution as a linear combination of ai A1 a1 + A2 a2 + · · · + Ak ak Want to arrange so that mod ai all the Aj for j = i are ≡ 0 mod m, and Ai ≡ 1 mod mi . Let N1 = m2 m3 . . . mk N2 = m1 m3 . . . mk .. . Ni = m1 m2 . . . mi−1 mi+1 . . . mk So (Ni , mi ) = 1, since all the other m are coprime to mi . Let Hi equal the multi­ plicative inverse of Ni mod mi , and let Ai = Hi Ni . Then, Ai ≡ 0 mod mj for j = i and Ai ≡ 1 mod mi . So now let a = A1 a1 + A2 a2 + · · · + Ak ak = H1 N1 a1 + H2 N2 a2 + · · · + Hk Nk ak Then if we take mod mi all the terms except ith term will vanish (since mi |Nj for j = i). So a ≡ Hi Ni ai (mod mi ) ≡ ai (mod mi ) • Eg. x ≡ 2 mod 3, x ≡ 3 mod 5, x ≡ 5 mod 7, N1 = 5 · 7 = 35 ≡ 2 N2 = 3 · 7 = 21 ≡ 1 N3 = 3 · 5 = 15 ≡ 1 2 mod 3, mod 5, mod 7, H1 = 2 H2 = 1 H3 = 1 x = H1 N1 a1 + N2 H2 a2 + N3 H3 a3 (mod m1 m2 m3 ) = 2 · 35 · 2 + 1 · 21 · 3 + 1 · 15 · 5 (mod 105) = 278 (mod 105) ≡ 68 (mod 105) Note: Assuming we have m1 , m2 . . . mk that are relatively prime, the Chi­ nese Remainder Theorem says that any choice of a1 mod m1 , a2 mod m2 , etc. gives rise to particular x(a1 , a2 , . . . ak , m1 , . . . mk ) mod m1 m2 . . . mk . Number of choices that we have is m1 m2 . . . mk , which agrees with number of integers mod m1 m2 . . . mk . Note: Now note that x(a1 , a2 , . . . ak , m1 , . . . mk ) is coprime to m1 m2 . . . mk if and only if (ai , mi ) = 1. • If x is coprime to mi then it is relatively coprime to each of them, so since x ≡ ai mod mi we’ll also have (ai , mi ) = 1. • Conversely if (ai , mi ) = 1 for all i, then since x ≡ ai mod mi , this implies that (xi , mi ) = 1 holds for all i, so (x, mi ) = 1 as well. What is the number of x coprime to mi ? (by definition this is φ(m1 m2 . . . mk )) (# of choices of a1 ) (# of choices of a2 ) . . . \ -\ φ(m1 ) φ(m1 ) with each ai coprime to mi . This gives corollary that if mi coprime in pairs, φ( mi ) = φ(mi ). We can use this to understand φ(n) for any n. With mi coprime in pairs, n = pe11 p2e2 . . . pkek m1 = pe11 , m2 = pe22 . . . mk = pekk φ(n) = φ(p1e1 )φ(pe22 ) . . . φ(pekk ) All we need, then, is how to find φ(pe ). 3 φ(pe ) = # of {x|1 ≤ x ≤ pe and (x, p) = 1 and so (x, pe ) = 1} = pe − pe−1 = pe−1 (p − 1) 1 p = pe 1 − and so φ(n) = p1e1 −1 (p1 − 1)pe22 −1 (p2 − 1) . . . pekk −1 (pk − 1) = pe11 p2e2 . . . pkek =n � 1− p|n 1− 1 p1 1− 1 p2 ... 1 − 1 pk 1 p Numerical Calculations for Algorithms Want to do arithmetic modulo N (some large number). Benchmark = time to write down N , which is roughly the number of digits of N = c log N for some constant c. Addition is log N steps/time Multiplication is log2 N steps/time in the simplest way Karatsuba Multiplication This is a faster algorithm for multiplication (see http://en.wikipedia.org/wiki/Karatsuba_algorithm#Algorithm); reduces time to (log N )log 3/ log 2 Multiplication can be further improved by using Fast Fourier Transforms to log N poly(log log n). Exponentiation - we want to compute ab mod N , with a at most N and b is also small (∼ N ). Most obvious way would be repeated multiplication for N log2 N , but better to use repeated squaring. Write b in binary as b = br br−1 . . . b0 = 2r br + 2r−1 br−1 + · · · + b0 0 1 r then compute a2 , a2 , . . . a2 mod N by repeatedly squaring the previous one (at most log2 N for each). Then take 0 a2 b0 a2 1 b1 a2 for a total of log b log2 N ∼ log3 N steps. 4 2 b2 r . . . a2 br