21-09-2012, 03:05 PM
New Chinese Remainder Theorems
1Chinese Remainder.pdf (Size: 583.42 KB / Downloads: 27)
Abstract
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 Theorem I, II, and III for the residue-tobinary
conversion, with the following detailed results.
(1) The big weights in the original CRT is reduced
to a matrix of numbers less than the moduli e.
(2) The New Chinese Remainder Theorem I is a
parallel algorithm in mired radix format. The delay is
reducedfiom O(n) to O(1ogn).
(3 The New Chinese Remainder Theorem II reduces
the modulo operation from the size M to a size less
t h a n a .
(4) The New Chinese Remainder Theorem II can be
easily extended to New Chinese Remainder Theorem
III for non-prime moduli sets.
(5) A summary of a long list of references on residueto-
binary conversion is also presented at this paper
Introduction
There has been interest in Residue Number
Systems (RNS) arithmetic as a basis for
computational hardware since the 1950’s [l] [6], due
to the inherent properties of RNS such as parallelism,
modularity, and carry free operations [lo]. The
conventional weight& number systems such as the
binary number system have a carry chain which often
limits the performance. The RNS reduces N- bit
arithmetic to log N-bit binary arithmetic [7], which
is particularly useful for problems involving long
integer arithmetic such as the RSA algorithm [5].
The RNS with non-prime moduli, i.e., moduli
sharing common factors, can be used to automate
error detection and correction. During the past decade.
Literature Summary
Residue-to-binary conversion has been studied
actively during the past two decades. However, no
recent paper has given a survey of the status of the
research. Almost all papers cite a small number of
research results despite the large amount of work
existing. We provide a large number of references at
the end of this paper [ 14-47]. All of the papers [ 14-
471 are for the prime moduli sets. There is no new
results about the non-prime moduli set conversion
after [6] published in 1967. The results reported in
this paper about the non-prime moduli sets are the
first such new results in recent years.
The list [14-471 is by no means complete.
However, it is the longest list one can find in this
area. It updates the survey results in [lo]. We
apologize for any missing papers. We also appreciate
any information on missing papers so that we can
make it complete in the future version. We include
few papers from conference proceedings.
Conclusions
Residue-to-binary conversion is the crucial step for
residue arithmetic. The traditional methods are the
Chinese Remainder Theorem and the Mixed Radix
Conversion. Both approaches have some well known
long standing difficulties. This paper presents results
which overcome those difficulties. It also provides a
long list of references of research results in this area.
Residue-to-binary conversion method is the key for
any other difficult RNS operations such as magnitude
comparison, sign detection, scaling, and division.
Based on the new conversion methods presented in
this paper, new algorithms for those difficult RNS
operations can be developed as well.