Chinese Remainder Theorem

Definition: A residue is the remainder of a division by a number called a modulus (i.e residue of 5/7 is 2).

Definition: A residue representation of a number x is the set of residues {r₁, r₂, …, r_k} with respect to moduli {m₁, m₂, …, m_k}.

If we use the residue representation {r₁,r₂,…, r_k} of x, the Chinese remainder theorem makes it possible to determine |x| provided the greatest common factor of any pair of moduli is 1 (i.e (r_i, r_j) = 1 , i ≠ j). Such moduli are known as pairwise relatively prime(M. Shahkarami and G.A. Jullien, 2002, University of Calgary).

For the case of RSA cryptography, we are only interested in having 2 factors, commonly called p and q. Their product is commonly called n = p × q.

In this case the Chinese Remainder Theorem says that if we know the residues:
            M_p = M mod p
            M_q = M mod q
       we can calculate:
            M mod n = M_p × y_q × q   +   M_q × y_p × p
       where n is the modulus p×q, and
            (y_q × q) mod p = 1;
y_q is often called the inverse of q modulo p, and is thus often written (q^-1 mod p)

We can prove that this value of M has the correct residues.
            M mod p = (M_p × y_q × q) mod p        because the second term is a multiple of p.
                           = (M_p mod p) × ( (y_q × q) mod p)
                           = M_p
       and similarly for M_q.

It only remains to prove that there is only one value of M mod n.

Imagine that there are two values of M, M₀ and M₁, each less than n.
            M₀ mod p = M_p
       and
            M₁ mod p = M_p
       Thus:
            ( M₁ – M₀ ) mod p = 0

In other words M₁ – M₀ is divisible by p, and by a similar argument it is also divisible by q. Because p and q are prime, this means that M₁ – M₀ is divisible by n. The only number less than n that is divisible by n is 0. therefore:
M₁ = M₀
i.e. there is only one solution.

In General

The Chinese Remainder Theorem is actually valid for many values, as hinted in the very first few paragraphs. We can express this as:
            x mod p₁ = a₁
            x mod p₂ = a₂
            x mod p₃ = a₃
            . . . . . . . . . . . . . .
            x mod p_k = a_k
The solution is:
            x = a₁ P₁ y₁ + a₂ P₂ y₂ + . . . . . . . . . .
                = S a_k P_k y_k

P_k is the product of all the p_i values, except for p_k, and y_k is the inverse of P_k modulo p_k, i.e.
( P_k y_k ) mod p_k = 1

We can see that x is a solution by calculating x mod p_k using the formula above. Only the single term
x mod p_k = ( a_k P_k y_k ) mod p_k
survives, because all the other values of P_i contain the factor p_k.

The definition of P_k and y_k above, lead to the desired result. We do need to be confident that we can always find a value y_k. This is the case for prime number values, and in fact for any set of values for which no two nmbers have a common factor.

A Party Trick

Ask someone to take their age calculate the remainder on division by 3. Then calculate the remainder on division by 5, and also by 7, to give three numbers, a, b and c.

You can then calculate the person's age as:
( a × 70 + b × 21 + c × 15 ) mod 105

For a 35-year-old we have a = 2, b = 0, c = 0. 70 × 2 = 140. Subtract 105 and the result is 35.

One year later we have a = 0, b = 1, c = 1. 21 + 15 = 36.

People older than 104 can usually be distinguished from young children without difficulty.