New Chinese remainder theorems

The residue-to-binary conversion is the crucial step for residue arithmetic. The traditional methods are the Chinese remainder theorem (CRT) and the mixed radix conversion. This paper presents new Chinese remainder theorems I, II, and Ill for the residue-to-binary conversion, with the following detailed results. (1) The big weights in the original CRT are reduced to a matrix of numbers less than the moduli P/sub i/. (2) The new Chinese remainder theorem I is a parallel algorithm in mixed radix format. The delay is reduced from O(n) to O(logn). (3) The new Chinese remainder theorem II reduces the modulo operation from the size M to a size less than /spl radic/M. (4) The new Chinese remainder theorem II can be easily extended to the new Chinese remainder theorem III for non-prime moduli sets. (5) A summary of a long list of references on residue-to-binary conversion is also presented.