Notes for Network and Data Security

Chinese Remainder Theorem

Theorem Let n and m be relatively prime, positive integers. Let a and b be integers. If a=b (n) and a=b (m) then a=b (nm).

Proof Suppose a!=b (nm), so (nm)!|(a-b). Since n and m are relatively prime, either n!|(a-b) or m!|(a-b). In the first case, a!=b (n), or in the second case a!=b (m).

It is necessary that n and m be relatively prime. As a counter-example choose m=n. Two numbers congruent mod n need not be congruent mod n**2!

The following is a bijection from Z_(mn) to Z_n cross Z_m, where n and m are relatively prime, positive integers. Given x_mn in Z_(mn), select and integer x such that x=x_mn Z_(mn). Map this to (x_n, x_m) where x=x_n (n) and x=x_m (m).

Proving the bijection follows the usual course: checking that the map is well defined, checking that it is injective, finally, checking that it is surjective.

The map is well-defined, since if x=y (mn) then (mn)|(x-y) so n|(x-y) and m|(x-y). The previous theorem shows that this map is injective: if x and y are such that x=y (n) and x=y (m) then x=y (mn). Surjectivity is most quickly checked by counting the number of elements in domain and codomain: they both have mn elements.

It is important for us to approach surjectivity from a second perspective. Given prescribed values a and b, find the x such that x=a (n) and x=b(m). This shows surjectivity constructively: given any element (a,b) in Z_n cross Z_m we construct the element x, unique in Z_mn, which maps by the bijection to (a,b). It is also important to note that this construction is computationally efficient.

By the Euclidean algorithm, we can efficiently find integers s and t such that s*n + t*m = 1. Consider the integer x = b*s*n + a*t*m. Because s*n = 1 (m), x=b (m). Similarly, x=a (n). Hence by this formula we can create x given (a,b). (Some might recognize this formula is Lagrange interpolation.)

The great significance of the Chinese Remainder Theorem is a result that this bijection, this pairing of element from Z_(n*m) to Z_n cross Z_m, preserves arithmetic. That is, calculating x+y and x*y in Z_(n*m) gives a result parallel to calculating with x and y in the decomposed represention of Z_n cross Z_m. In Z_n cross Z_m, addition and multiplcation is componentwise, (a,b)+(c,d) =(a+c,b+d) and (a,b)*(c,d)=(a*c,b*d). We first prove this and then list four applications.

Theorem Let n and m be relatively prime, positive integers. Let a and b be integers and a=a_n (n), b=b_n (n), a=a_m (m) and b=b_m (m). Then a + b = a_n + b_n (n) and a + b = a_m + b_m (m), and a * b = a_n * b_n (n) and a * b=a_m * b_m (m).

Proof Since n|(a-a_n) and n|(b-b_n), then n|((a-a_n)+(b-b_n)) so n|((a+b)-(a_n+b_n)), likewise with m. Also n|(a-a_n)b and n|(b-b_n)a_n, so n|((a-a_n)b+(b-b_n)a_n) so n|(ab - a_n b_n), likewise with m.

There are four facts of great use to be readily derived from the Chinese remainder theorem.

1. That Euler's Phi function is multiplicative: if n and m are positive, relatively prime integers, phi(n*m)=phi(n)*phi(m).
2. The Fermat theorem states that a^(phi(n)+1)=a (n) for a relatively prime to n. If n is square free, that is, p^2 does not divide n for any prime p, then a^(phi(n)+1)=a (n) for all a.
3. In the case of n=pq, p and q are distinct primes, RSA depends upon a^((p-1)*(q-1))=1 (p*q). In fact, for k the least common multiple of p-1 and q-1, already a^k=1 (p*q). That is, for some integer r, k*r=(p-1)*(q-1). Indeed a^(k*r)=1 (p*q), but that is because already a^k=1 (p*q). Hence, while the encryption and decryption exponents are inverses mod phi(n), then can just as well be inverses mod k, which is smaller than phi(n). (At least one bit smaller since p-1 and q-1 are both even.)
4. Any x such that x*x=1 (n) is a square root of 1 in Z_n. If there are k primes p_1, p_2, ... , p_k such that p_i|n, then there are 2^k square roots of 1 in Z_n. For instance, if n=12, then k=2, the primes being p_1=2 and p_2=3. There are four square roots of 1 in Z_12. They are 1, 11, 5 and 7.