Introduction

The origin of the topic RNS [Gar59] is credited to the Chinese scholar Sun Tzu of first Century AD and Greek Mathematician Nichomachus and Hsin-Tai-Wei of the Ming dynasty (1368AD–1643AD). Later, Euler presented a proof for the Chinese Remainder Theorem (CRT) in 1734. In the twentieth Century, Lehmer, Svoboda and Valach built hardware using RNS and much work was done at various laboratories during 1950’s and 1960’s. The text books by Szabo and Tanaka [Sza67] and Watson and Hastings [Wats67] in 1967 are the first documenting the results in this area. Subsequently, in 1977, resurgence of interest in this area was due to the pioneering work of Jenkins and Leon [Jenk77]. By 1980, interesting results were available in all areas of RNS such as residue Number scaling, RNS to Binary conversion, Binary to RNS conversion, scaling and error correction. These are largely due to the research of Soderstrand, Miller, Jullien, Jenkins, Leon among others. These early designs were mostly ROM based. The advent of VLSI technology has stimulated the work in the area of non-ROM based solutions. This led to work on special moduli sets. It is interesting to note that the computational speed has been increasing and excellent solutions have been evolving even as recently as December 2000.The work carried our till 1986 was compiled in an IEEE Press collection of papers [Sode86]. The reader is referred to an excellent historical introduction to this subject in this book.