Chinese Remainder Theorem

Prepared by Antonius Cahya Prihandoko

mc-crtWith a particular condition, the Chinese Remainder Theorem (CRT) is employed to obtain a single value x which is congruent to several different values in different modulus. It should be noted that all number of modulus have to be pairwise relative prime, that is no two of them have a common factor. Otherwise the existence of a solution cannot be guaranteed. For example, find an integer x which satisfies the following congruences.

  x \equiv 3 \bmod 8
x \equiv 4 \bmod 9
x \equiv 2 \bmod 5

A simple algorithm to compute x is, for each congruence, find a solution for such congruence which is a multiple of each other modulo and sum together all solutions. In practical, a multiple of 9 \times 5 which is congruent to 3 \bmod 8 is 315. In a similar way, an easy computation yields 40 and 72, for the second and third congruence, respectively. The sum of these three results can be analyzed follows.

  315+40+72 \equiv 315 \equiv 3 \bmod 8
315+40+72 \equiv 40 \equiv 4 \bmod 9
315+40+72 \equiv 72 \equiv 2 \bmod 5

Thus, 315+40+72 = 427  fulfills all congruences. Since 427 \equiv 67 \bmod (8 \times 9 \times 5), hence 67 is the expected value.

Formally, the CRT claims that if m_{1},m_{2},...,m_{k} are pairwise relative prime positive integers and a_{1},a_{2},...,a_{k} are any integers, then the congruences system

x \equiv a_{i} \bmod m_{i},

for 1 \leq i \leq k, has a unique solution modulo M=m_{1} \times m_{2} \times ... \times m_{k}. And the solution of the system is given by

x \equiv \sum_{i=1}^{k} a_{i}M_{i}(M_{i}^{-1} \bmod m_{i}) \bmod M

where M_{i} = \frac{M}{m_{i}}, for 1 \leq i \leq k.

Directly applying the formula, a value that meet the system

  x \equiv 40 \bmod 439
x \equiv 128 \bmod 187
x \equiv 37 \bmod 345
x \equiv 159 \bmod 233
x \equiv 238 \bmod 413

is 736388737.

For a fix system, the formula is powerful. It can be used to obtain solution of  a system of many congruences in one computation. However, when the system is progressive, allowing congruences addition in further, the formula will less useful to update the system’s solution. In this case, a new solution has to be computed every time when a congruence is added to the system. This incremental computation will be efficiently done by meant of the Garner’s algorithm  below.

1. For i from 2 to k do the following:
1.1. c_{i} \leftarrow 1.
1.2. For j from 1 to (i-1) do the following:
1.2.1. u \leftarrow m_{j}^{-1} \bmod m_{i}.
1.2.2. c_{i} \leftarrow u.c_{i} \bmod m_{i}.
2. u \leftarrow a_{1}, x \leftarrow u.
3. For i from 2 to k do the following:
3.1. u \leftarrow (a_{i}-x) c_{i} \bmod m_{i}
3.2. x \leftarrow x + u.\prod_{j=1}^{i-1} m_{j}
4. Return x.

The incremental computation using the Garner’s algorithm can be described follows. Let X_{i} and Y_{i}, are updated solution and sub solution, respectively, of the system of the first i congruences. In this case, X_{1}=Y_{1}=a_{1}. Subsequent computations for each congruence addition are

Y_{i}= ( (a_{i}-X_{i-1})\prod_{j=1}^{i-1}m_{j}^{-1} \bmod m_{i}).\prod_{j=1}^{i-1}m_{j},

and

X_{i}=X_{i-1}+Y_{i},

for 2 \leq i \leq k. It is clear that every time a congruence is added to the system, the updated solution is computed based on the previous last solution.

Townsville, 27 February 2013

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s