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 .$ Then for $a, b \in Z$ the system

\begin{aligned} x & \equiv a (\mod m) \\ x & \equiv b (\mod n) \end{aligned}

has a solution. If $x_{1}$ and $x_{2}$ are two solutions of the system, then $x_{1} \equiv x_{2} (\mod m n) .$

🔗

Proof.

The equation $x \equiv a (\mod m)$ has a solution since $a + k m$ satisfies the equation for all $k \in Z .$ We must show that there exists an integer $k_{1}$ such that

a + k_{1} m \equiv b (\mod n) .

This is equivalent to showing that

k_{1} m \equiv (b - a) (\mod n)

has a solution for $k_{1} .$ Since $m$ and $n$ are relatively prime, there exist integers $s$ and $t$ such that $m s + n t = 1 .$ Consequently,

(b - a) m s = (b - a) - (b - a) n t,

[(b - a) s] m \equiv (b - a) (\mod n) .

Now let $k_{1} = (b - a) s .$

To show that any two solutions are congruent modulo $m n,$ let $c_{1}$ and $c_{2}$ be two solutions of the system. That is,

\begin{aligned} c_{i} & \equiv a (\mod m) \\ c_{i} & \equiv b (\mod n) \end{aligned}

for $i = 1, 2 .$ Then

\begin{aligned} c_{2} & \equiv c_{1} (\mod m) \\ c_{2} & \equiv c_{1} (\mod n) . \end{aligned}

Therefore, both $m$ and $n$ divide $c_{1} - c_{2} .$ Consequently, $c_{2} \equiv c_{1} (\mod m n) .$

🔗

Example 16.42.

Let us solve the system

\begin{aligned} x & \equiv 3 (\mod 4) \\ x & \equiv 4 (\mod 5) . \end{aligned}

Using the Euclidean algorithm, we can find integers $s$ and $t$ such that $4 s + 5 t = 1 .$ Two such integers are $s = 4$ and $t = - 3 .$ Consequently,

x = a + k_{1} m = 3 + 4 k_{1} = 3 + 4 [(5 - 4) 4] = 19 .

🔗

Theorem 16.43. Chinese Remainder Theorem.

Let $n_{1}, n_{2}, \dots, n_{k}$ be positive integers such that $gcd (n_{i}, n_{j}) = 1$ for $i \neq j .$ Then for any integers $a_{1}, \dots, a_{k},$ the system

\begin{aligned} x & \equiv a_{1} (\mod n_{1}) \\ x & \equiv a_{2} (\mod n_{2}) \\ ⋮ \\ x & \equiv a_{k} (\mod n_{k}) \end{aligned}

has a solution. Furthermore, any two solutions of the system are congruent modulo $n_{1} n_{2} \dots n_{k} .$

🔗

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{aligned} x & \equiv a_{1} (\mod n_{1}) \\ x & \equiv a_{2} (\mod n_{2}) \\ ⋮ \\ x & \equiv a_{k + 1} (\mod n_{k + 1}) . \end{aligned}

Considering the first $k$ equations, there exists a solution that is unique modulo $n_{1} \dots n_{k},$ say $a .$ Since $n_{1} \dots n_{k}$ and $n_{k + 1}$ are relatively prime, the system

\begin{aligned} x & \equiv a (\mod n_{1} \dots n_{k}) \\ x & \equiv a_{k + 1} (\mod n_{k + 1}) \end{aligned}

has a solution that is unique modulo $n_{1} \dots n_{k + 1}$ by the lemma.

🔗

Example 16.44.

Let us solve the system

\begin{aligned} x & \equiv 3 (\mod 4) \\ x & \equiv 4 (\mod 5) \\ x & \equiv 1 (\mod 9) \\ x & \equiv 5 (\mod 7) . \end{aligned}

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 (\mod 20) .$ Hence, we can reduce the system to a system of three congruences:

\begin{aligned} x & \equiv 19 (\mod 20) \\ x & \equiv 1 (\mod 9) \\ x & \equiv 5 (\mod 7) . \end{aligned}

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

\begin{aligned} x & \equiv 19 (\mod 180) \\ x & \equiv 5 (\mod 7) . \end{aligned}

Solving this last system, we find that $19$ is a solution for the system that is unique up to modulo $1260 .$

🔗

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

2^{63} - 1 = 9,223,372,036,854,775,807 .

🔗

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,

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 .$ We will use the integers $95,$ $97,$ $98,$ and $99$ because they are relatively prime. We can break down each integer into four parts:

\begin{aligned} 2134 & \equiv 44 (\mod 95) \\ 2134 & \equiv 0 (\mod 97) \\ 2134 & \equiv 76 (\mod 98) \\ 2134 & \equiv 55 (\mod 99) \end{aligned}

and

\begin{aligned} 1531 & \equiv 11 (\mod 95) \\ 1531 & \equiv 76 (\mod 97) \\ 1531 & \equiv 61 (\mod 98) \\ 1531 & \equiv 46 (\mod 99) . \end{aligned}

Multiplying the corresponding equations, we obtain

\begin{aligned} 2134 \cdot 1531 & \equiv 44 \cdot 11 \equiv 9 (\mod 95) \\ 2134 \cdot 1531 & \equiv 0 \cdot 76 \equiv 0 (\mod 97) \\ 2134 \cdot 1531 & \equiv 76 \cdot 61 \equiv 30 (\mod 98) \\ 2134 \cdot 1531 & \equiv 55 \cdot 46 \equiv 55 (\mod 99) . \end{aligned}

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{aligned} x & \equiv 9 (\mod 95) \\ x & \equiv 0 (\mod 97) \\ x & \equiv 30 (\mod 98) \\ x & \equiv 55 (\mod 99) . \end{aligned}

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

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.

Abstract Algebra: Theory and Applications

Search Results:

Section 16.5 An Application to Software Design

Lemma 16.41.

Proof.

Example 16.42.

Theorem 16.43. Chinese Remainder Theorem.

Proof.

Example 16.44.

Example 16.45.