Tuesday, October 8, 2013

Notes - The Chinese Remainder Theorem

The following are notes from Introduction to Cryptography with Coding Theory.
  • Chinese remainder theorem is used to break a congruence mod n into a system of congruences mod factors of n
    • Example
      • Number satisfies x≡ 25(mod 42)
      • means we can write x = 25 + 42k (k is some integer)
      • we can rewrite 42 as 7*6
      • x = 25 + 7(6k)
      • x = 25 + 6(7k)
  • Chinese Remainder Theorem
    • suppose gcd(m,n) = 1. If an integer c is a multiple of both m and n, then c is a multiple of mn. given integers a and b there exists exactly one solution x (mod mn)to the simultaneous congruences
      • x ≡ a (mod m)
    • x ≡ a (mod m)
      • x ≡ b (mod n)
  • Lemma
    • Let m,n be integers with gcd(m,n) = 1
    • if an integer c is a multiple of both m and n, then c is a multiple of mn
  • Example
    • Solve x ≡ 3 (mod 7), x ≡ 5 (mod 15)
    • 7*15 = 105
    • list congruences
      • 5,20,35,50,65,80
      • 3,10,17,24,31,38,45,52,59,66,73,80
      • x ≡ 80 mod 105
    • solve
      • nk ≡ a - b (mod m)
      • k ≡ (a - b)i (mod m) [i is the multiplicative inverse of n]

No comments:

Post a Comment