AATA An Application to Software Design

Section 16.5 An Application to Software Design

The Chinese Remainder Theorem is a result from elementary number theory about the solution of systems of simultaneous congruences. The Chinese mathematician Sun-tsï wrote about the theorem in the first century A.D. This theorem has some interesting consequences in the design of software for parallel processors.

Lemma 16.41.

Let \(m\) and \(n\) be positive integers such that \(\gcd( m, n) = 1\text{.}\) Then for \(a, b \in {\mathbb Z}\) the system

\begin{align*} x & \equiv a \pmod{m}\\ x & \equiv b \pmod{n} \end{align*}

has a solution. If \(x_1\) and \(x_2\) are two solutions of the system, then \(x_1 \equiv x_2 \pmod{mn}\text{.}\)

Proof.

The equation \(x \equiv a \pmod{m}\) has a solution since \(a + km\) satisfies the equation for all \(k \in {\mathbb Z}\text{.}\) We must show that there exists an integer \(k_1\) such that

\begin{equation*} a + k_1 m \equiv b \pmod{n}\text{.} \end{equation*}

This is equivalent to showing that

\begin{equation*} k_1 m \equiv (b-a) \pmod{n} \end{equation*}

has a solution for \(k_1\text{.}\) Since \(m\) and \(n\) are relatively prime, there exist integers \(s\) and \(t\) such that \(ms + nt = 1\text{.}\) Consequently,

\begin{equation*} (b-a) ms = (b-a) -(b-a) nt\text{,} \end{equation*}

\begin{equation*} [(b-a)s]m \equiv (b-a) \pmod{n}\text{.} \end{equation*}

Now let \(k_1 = (b-a)s\text{.}\)

To show that any two solutions are congruent modulo \(mn\text{,}\) let \(c_1\) and \(c_2\) be two solutions of the system. That is,

\begin{align*} c_i & \equiv a \pmod{m}\\ c_i & \equiv b \pmod{n} \end{align*}

for \(i = 1, 2\text{.}\) Then

\begin{align*} c_2 & \equiv c_1 \pmod{m}\\ c_2 & \equiv c_1 \pmod{n}\text{.} \end{align*}

Therefore, both \(m\) and \(n\) divide \(c_1 - c_2\text{.}\) Consequently, \(c_2 \equiv c_1 \pmod{mn}\text{.}\)

Example 16.42.

Let us solve the system

\begin{align*} x & \equiv 3 \pmod{4}\\ x & \equiv 4 \pmod{5}\text{.} \end{align*}

Using the Euclidean algorithm, we can find integers \(s\) and \(t\) such that \(4s + 5t = 1\text{.}\) Two such integers are \(s = 4\) and \(t = -3\text{.}\) Consequently,

\begin{equation*} x = a + k_1 m = 3 + 4k_1 = 3 + 4[(5 - 4)4] = 19\text{.} \end{equation*}

Theorem 16.43. Chinese Remainder Theorem.

Let \(n_1, n_2, \ldots, n_k\) be positive integers such that \(\gcd(n_i, n_j) = 1\) for \(i \neq j\text{.}\) Then for any integers \(a_1, \ldots, a_k\text{,}\) the system

\begin{align*} x & \equiv a_1 \pmod{n_1}\\ x & \equiv a_2 \pmod{n_2}\\ & \vdots\\ x & \equiv a_k \pmod{n_k} \end{align*}

has a solution. Furthermore, any two solutions of the system are congruent modulo \(n_1 n_2 \cdots n_k\text{.}\)

Proof.

We will use mathematical induction on the number of equations in the system. If there are \(k= 2\) equations, then the theorem is true by Lemma 16.41. Now suppose that the result is true for a system of \(k\) equations or less and that we wish to find a solution of

\begin{align*} x & \equiv a_1 \pmod{n_1}\\ x & \equiv a_2 \pmod{n_2}\\ & \vdots\\ x & \equiv a_{k+1} \pmod{n_{k+1}}\text{.} \end{align*}

Considering the first \(k\) equations, there exists a solution that is unique modulo \(n_1 \cdots n_k\text{,}\) say \(a\text{.}\) Since \(n_1 \cdots n_k\) and \(n_{k+1}\) are relatively prime, the system

\begin{align*} x & \equiv a \pmod{n_1 \cdots n_k }\\ x & \equiv a_{k+1} \pmod{n_{k+1}} \end{align*}

has a solution that is unique modulo \(n_1 \ldots n_{k+1}\) by the lemma.

Example 16.44.

Let us solve the system

\begin{align*} x & \equiv 3 \pmod{4}\\ x & \equiv 4 \pmod{5}\\ x & \equiv 1 \pmod{9}\\ x & \equiv 5 \pmod{7}\text{.} \end{align*}

From Example 16.42 we know that \(19\) is a solution of the first two congruences and any other solution of the system is congruent to \(19 \pmod{20}\text{.}\) Hence, we can reduce the system to a system of three congruences:

\begin{align*} x & \equiv 19 \pmod{20}\\ x & \equiv 1 \pmod{9}\\ x & \equiv 5 \pmod{7}\text{.} \end{align*}

Solving the next two equations, we can reduce the system to

\begin{align*} x & \equiv 19 \pmod{180}\\ x & \equiv 5 \pmod{7}\text{.} \end{align*}

Solving this last system, we find that \(19\) is a solution for the system that is unique up to modulo \(1260\text{.}\)

One interesting application of the Chinese Remainder Theorem in the design of computer software is that the theorem allows us to break up a calculation involving large integers into several less formidable calculations. A computer will handle integer calculations only up to a certain size due to the size of its processor chip, which is usually a 32 or 64-bit processor chip. For example, the largest integer available on a computer with a 64-bit processor chip is

\begin{equation*} 2^{63} - 1 = 9{,}223{,}372{,}036{,}854{,}775{,}807\text{.} \end{equation*}

Larger processors such as 128 or 256-bit have been proposed or are under development. There is even talk of a 512-bit processor chip. The largest integer that such a chip could store with be \(2^{511} - 1\text{,}\) which would be a 154 digit number. However, we would need to deal with much larger numbers to break sophisticated encryption schemes.

Special software is required for calculations involving larger integers which cannot be added directly by the machine. By using the Chinese Remainder Theorem we can break down large integer additions and multiplications into calculations that the computer can handle directly. This is especially useful on parallel processing computers which have the ability to run several programs concurrently.

Most computers have a single central processing unit (CPU) containing one processor chip and can only add two numbers at a time. To add a list of ten numbers, the CPU must do nine additions in sequence. However, a parallel processing computer has more than one CPU. A computer with 10 CPUs, for example, can perform 10 different additions at the same time. If we can take a large integer and break it down into parts, sending each part to a different CPU, then by performing several additions or multiplications simultaneously on those parts, we can work with an integer that the computer would not be able to handle as a whole.

Example 16.45.

Suppose that we wish to multiply \(2134\) by \(1531\text{.}\) We will use the integers \(95\text{,}\) \(97\text{,}\) \(98\text{,}\) and \(99\) because they are relatively prime. We can break down each integer into four parts:

\begin{align*} 2134 & \equiv 44 \pmod{95}\\ 2134 & \equiv 0 \pmod{97}\\ 2134 & \equiv 76 \pmod{98}\\ 2134 & \equiv 55 \pmod{99} \end{align*}

and

\begin{align*} 1531 & \equiv 11 \pmod{95}\\ 1531 & \equiv 76 \pmod{97}\\ 1531 & \equiv 61 \pmod{98}\\ 1531 & \equiv 46 \pmod{99}\text{.} \end{align*}

Multiplying the corresponding equations, we obtain

\begin{align*} 2134 \cdot 1531 & \equiv 44 \cdot 11 \equiv 9 \pmod{95}\\ 2134 \cdot 1531 & \equiv 0 \cdot 76 \equiv 0 \pmod{97}\\ 2134 \cdot 1531 & \equiv 76 \cdot 61 \equiv 30 \pmod{98}\\ 2134 \cdot 1531 & \equiv 55 \cdot 46 \equiv 55 \pmod{99}\text{.} \end{align*}

Each of these four computations can be sent to a different processor if our computer has several CPUs. By the above calculation, we know that \(2134 \cdot 1531\) is a solution of the system

\begin{align*} x & \equiv 9 \pmod{95}\\ x & \equiv 0 \pmod{97}\\ x & \equiv 30 \pmod{98}\\ x & \equiv 55 \pmod{99}\text{.} \end{align*}

The Chinese Remainder Theorem tells us that solutions are unique up to modulo \(95 \cdot 97 \cdot 98 \cdot 99 = 89{,}403{,}930\text{.}\) Solving this system of congruences for \(x\) tells us that \(2134 \cdot 1531 = 3{,}267{,}154\text{.}\)

The conversion of the computation into the four subcomputations will take some computing time. In addition, solving the system of congruences can also take considerable time. However, if we have many computations to be performed on a particular set of numbers, it makes sense to transform the problem as we have done above and to perform the necessary calculations simultaneously.