Systems of Linear Congruences—Multiple Moduli - Introduction to Cryptography with Java Applets - page 165

FIGURE 8.1

//Answer must be returned as a two dimensional array.
BigInteger[] result=new BigInteger[2];
result[0]=solution;
result[1]=M;
return result;

}

I have written an applet called TestCRTApplet which allows you to solve these types of
systems using the Chinese Remainder Theorem. It can be run from the topic's website, and
a screen shot follows (see Figure 8.1). The Chinese Remainder Theorem has many impor-
tant applications in cryptography, and it is equally useful to both the cryptographer and the
cryptanalyst. We will investigate many of these applications in upcoming chapters.

EXERCISES

1. Solve the following systems of linear congruences using the Chinese Remainder The-

orem (CRT).
a. x 23 (mod 26)

x 2 (mod 31)

x 5 (mod 17)

b. x 1 (mod 26)

x 1 (mod 33)

x 1 (mod 35)

c. 5 x 3 (mod 18)

3 x 4 (mod 7)

2 x 5 (mod 25)

6 x 10 (mod 11)