Search

The Chinese remainder theorem (CRT), which appeared in ancient China, is widely used in many modern computer applications. This paper presents the CRT implementation by using the interval-index characteristic and minimum redundancy residue code. The proposed algorithm does not use large modulo addition operations and provides low computational complexity compared to conventional non-redundant RNS. The efficiency factors of using the minimally redundant RNS increase with the number k of non-redundant moduli, asymptotically approaching the threshold k/2. The new approach presented here will have a significant impact on many non-modular operations in RNS arithmetic, which currently use the CRT. [ABSTRACT FROM AUTHOR]