3. Chinese Reminder Theory

3.1. Knowledge required

• Galois Field

• Multiplicative Inverse In GF

3.2. Question

For a number x, if

\[\begin{split}x~mod~3 = 2\\ x~mod~5 = 3\\ x~mod~7 = 2.\end{split}\]

what is x?

In order to use CRT, the module number 3, 5 and 7 should be relatively prime.

Let Mi be the multiplication of the module number except number i. Say:

\[\begin{split}&M1 = 5 * 7 = 35~(except~3)\\ &M2 = 3 * 7 = 21~(except~5)\\ &M3 = 3 * 5 = 15~(except~7)\end{split}\]

The multiplicative inverse of M1, M2 and M3 in GF(3), GF(5) and GF(7) repectively can be computed by Extended Euclidean algorithm.

\[\begin{split}M1^{-1} = 2\\ M2^{-1} = 1\\ M3^{-1} = 1\end{split}\]

We can easily check that \(2*35 ~mod~ 3 = 1\).

Then we have

\[\begin{split}M1^{-1}M1 = 2 * 35 = 70\\ M2^{-1}M2 = 1 * 21 = 21\\ M3^{-1}M3 = 1 * 15 = 15\end{split}\]

\[\begin{split}x &= (70 * (x ~mod~ 3)) + (21 * (x ~mod~ 5)) + (15 * (x ~mod~ 7)) ~mod~ (3 * 5 * 7)\\ &= 233 ~mod~ 105 = 23\end{split}\]

3.3. A simple Proof

Let’s restate the problem and the solution again.

Find \(x\) such that

\[\begin{split}x~mod~a = a'\\ x~mod~b = b'\\ x~mod~c = c'.\end{split}\]

Then

\[\begin{split} & Ma = bc\\ & Mb = ac\\ & Mc = ab\\\end{split}\]

\[x = bc [(bc)^{-1}~mod~a] a' + ac[(ac)^{-1}~mod~b] b' + ab[(ab)^{-1}~mod~c]c' ~mod~abc\]

The final \(mod~abc\) is only to make \(x\) as small as possible.

Now, let’s compute \(x~mod~a\)

\[x~mod~a = \{bc [(bc)^{-1}~mod~a] a'\} ~mod~a + \{ac[(ac)^{-1}~mod~b] b'\}~mod~a + \{ab[(ab)^{-1}~mod~c]c'\}~mod~a\]

Split the computation to three parts:

\[\begin{split}& \{bc [(bc)^{-1}~mod~a] a'\} ~mod~a = [bc (bc)^{-1}~mod~a] a' ~mod~a = 1a' ~mod~a = a'\\ & \{ac[(ac)^{-1}~mod~b] b'\}~mod~a = a \{c[(ac)^{-1}~mod~b] b'\} ~mod~a = 0\\ & \{ab[(ab)^{-1}~mod~c] c'\}~mod~a = a \{b[(ab)^{-1}~mod~c] c'\} ~mod~a = 0\end{split}\]

So

\[x~mod~a=a'\]

3.4. Applications of CRT

3.4.1. Example 1

Suppose we have two calculators which can do operations smaller than 5 and 3 respectively. How to deal with operations with numbers smaller than 15?

Create a table as follows:

	0	1	2	3	4
0	0	6	12	3	9
1	10	1	7	13	4
2	5	11	2	8	14

Arrange numbers from 0-14 to the table above Row 0 means the number mod 3 is 0. Column 3 means then number mod 5 is 3.

\[12*13~mod~15=?\]

\(12\) is row 0, column 2 \(13\) is row 1, column 3 So the result’s row is \(0 * 1 ~mod~3 = 0\), column is \(2 * 3~mod~5=1\). The number in row 0, column 1 is 6.

We have

\[12*13~mod~15=6\]

3.4.2. Example 2

\(973 \times 73~mod~1813 = ?\)

\(1813 = 49*37\). We can split the modulo 1813 into modulo 49 and modulo 37.

\[\begin{split} &973~mod~37 = 11\\ &973~mod~49 = 42\\ & 73~mod~37 = 36\\ & 73~mod~49 = 24\\\end{split}\]

We use \(937 = (11, 42)\) and \(73 = (36, 24)\) to denote the two numbers under modulo 37 and 39.

Then \(973x73 = (11*36~mod~37, 42*24~mod~49) = (26, 28)\). We now have a classic CRT problem.

What is \(x\) if \(x~mod~37=26\) and \(x~mod~49=28\)?

\[\begin{split} x =& 49 * (49^{-1}~mod~37)*26 + 37 * (37^{-1}~mod~49)*28 ~mod~(37*49)\\ =& 49 * 34 * 26 + 37 * 4 * 28\\ =& 322\end{split}\]

Honestly, if we can compute it directly, no bother to do the split. This method here is the fundamental for parallel computing. Example 1 may be a better example.