- 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]

## Tuesday, October 8, 2013

### Notes - The Chinese Remainder Theorem

The following are notes from Introduction to Cryptography with Coding Theory.

Subscribe to:
Post Comments (Atom)

## No comments:

## Post a Comment