The book gives a detailed description of the Chinese remainder theorem (CRT) and its application to computing, coding and cryptography. The basic CRT for modular arithmetic is described, along with generalizations to polynomials and other systems. Many historical comments are included, and the subject is treated from both the algebraic and information theoretic approach.
Modular computations based on the Chinese remainder algorithm (CRA) are considered in chapter 3, which includes a discussion of the Schönhage algorithm for the multiplication of large integers as well as the computation of exact polynomial resultants and homomorphic image computation. It emphasizes the divide-and-conquer aspects of the algorithm. The fourth chapter shows the application of these ideas to such algorithms as polynomial interpolation, shift register synthesis over integer rings, cyclic convolution and the fast Fourier transform, among others. The numbers of solutions of certain types of equations and the computation of fixed points of equations is considered in chapter 5, where the problem of using CRA-type of arguments in structures where they do not apply is considered.
The use of the CRT in coding theory and the construction of codes is treated in chapter 6. Specifically the classes of codes of Reed-Solomon, redundant residue codes, Bassen-Yau codes and generalized redundant residue codes are discussed. The applications of the CRT to cryptography include secret sharing, stream ciphering, knapsack problems and public key systems.
Two appendices on information theory and algebra are included.