238
D. Gorodecky and T. Villa
11.2 Basic Knowledge About RNS
The Chinese reminder theorem [4] states that there is a one-to-one correspondence
between a set of residues X 1 , X 2 , . . . , X n and a number from 0 to p 1 · p 2 · . . . ·
p n − 1 = P − 1. Since the value of the represented number is invariant under any
permutation of the residues, RNS is a non-positional number system.
These features make RNS an alternative system with pros and cons compared
with other systems of representation. For example, on one side it allows to
parallelize computations and hence to speed them up, on the other side it does
not allow to compare two numbers represented by their residues and figure out
which one is greater without additional operations like backward conversion into
the positional system.
RNS is a form of parallel data processing, where computer arithmetic is performed using the residues of the division by a pre-selected base of co-primes moduli
{p 1 , p 2 , . . . , p m }. The residues have a lower number of digits than the original
numbers and arithmetic operations over the residues can be performed separately for
each modulo of the base, resulting in faster processing (e.g., faster addition and multiplication), compared to other forms of parallel data processing. The parallelism is
achieved by computing on the residues. The residues (A 1 , B 1 , A 2 , B 2 , . . . , A n , B n )
are the results of division of the input numbers (A and B) by s pre-selected set of
co-primes (p 1 , p 2 , . . . , p n )—moduli, where p 1 · p 2 · . . . · p n = P . Computing in
RNS is not restricted to arithmetic operations with two operands, and it is suitable
for an arbitrary number of operands.
Data processing in RNS includes the following steps. First, input operands
A 1 , A 2 , . . . , A n are converted from positional to modular representations computing the remainders (or residues) with respect to the moduli {p 1 , p 2 , . . . , p m } (see
left block in Fig. 11.1); then arithmetic operations over the residues of the operands
for each modulo p i , where i = 1, . . . , n, are computed (middle block in Fig. 11.1);
finally, the results S 1 , S 2 , . . . , S m for each modulo are converted back from modular
to positional representations S (see right block in Fig. 11.1).
Conversion into modular representation (direct conversion) is realized by the
modulo X(mod P ) function, whose result is fed into the second step of operations.
The second step of the RNS computation requires performing modular summation,
multiplication, and other arithmetic functions such as A · B + C. The third step in
RNS computes the polynomial form S 1 · C 1 + S 2 · C 2 + . . . + S m · C m − P · r, where
S 1 , S 2 , . . . are outputs of the previous step, C 1 , C 2 , . . . are pre-calculated constants,
r is a constant which is obtained during the computation of the polynomial,
and P = p 1 · p 2 · . . . · p m . In other words the third step in RNS computes
(S 1 · C 1 + S 2 · C 2 + . . . + S m · C m )(mod P ). Therefore, the main arithmetic
operations needed for RNS computations are the modulo function X(mod P ),
modular summation, and modular multiplication.
For instance, A = 37, B = 19, and P = p 1 · p 2 · p 3 = 3 · 5 · 7 = 105. In
this case A 1 = 1, B 1 = 1, A 2 = 2, B 2 = 4, A 3 = 2, B 3 = 5, i.e., A = (1, 2, 2)
and B = (1, 4, 6). In this case, addition is produced by summing residues with
D. Gorodecky and T. Villa
11.2 Basic Knowledge About RNS
The Chinese reminder theorem [4] states that there is a one-to-one correspondence
between a set of residues X 1 , X 2 , . . . , X n and a number from 0 to p 1 · p 2 · . . . ·
p n − 1 = P − 1. Since the value of the represented number is invariant under any
permutation of the residues, RNS is a non-positional number system.
These features make RNS an alternative system with pros and cons compared
with other systems of representation. For example, on one side it allows to
parallelize computations and hence to speed them up, on the other side it does
not allow to compare two numbers represented by their residues and figure out
which one is greater without additional operations like backward conversion into
the positional system.
RNS is a form of parallel data processing, where computer arithmetic is performed using the residues of the division by a pre-selected base of co-primes moduli
{p 1 , p 2 , . . . , p m }. The residues have a lower number of digits than the original
numbers and arithmetic operations over the residues can be performed separately for
each modulo of the base, resulting in faster processing (e.g., faster addition and multiplication), compared to other forms of parallel data processing. The parallelism is
achieved by computing on the residues. The residues (A 1 , B 1 , A 2 , B 2 , . . . , A n , B n )
are the results of division of the input numbers (A and B) by s pre-selected set of
co-primes (p 1 , p 2 , . . . , p n )—moduli, where p 1 · p 2 · . . . · p n = P . Computing in
RNS is not restricted to arithmetic operations with two operands, and it is suitable
for an arbitrary number of operands.
Data processing in RNS includes the following steps. First, input operands
A 1 , A 2 , . . . , A n are converted from positional to modular representations computing the remainders (or residues) with respect to the moduli {p 1 , p 2 , . . . , p m } (see
left block in Fig. 11.1); then arithmetic operations over the residues of the operands
for each modulo p i , where i = 1, . . . , n, are computed (middle block in Fig. 11.1);
finally, the results S 1 , S 2 , . . . , S m for each modulo are converted back from modular
to positional representations S (see right block in Fig. 11.1).
Conversion into modular representation (direct conversion) is realized by the
modulo X(mod P ) function, whose result is fed into the second step of operations.
The second step of the RNS computation requires performing modular summation,
multiplication, and other arithmetic functions such as A · B + C. The third step in
RNS computes the polynomial form S 1 · C 1 + S 2 · C 2 + . . . + S m · C m − P · r, where
S 1 , S 2 , . . . are outputs of the previous step, C 1 , C 2 , . . . are pre-calculated constants,
r is a constant which is obtained during the computation of the polynomial,
and P = p 1 · p 2 · . . . · p m . In other words the third step in RNS computes
(S 1 · C 1 + S 2 · C 2 + . . . + S m · C m )(mod P ). Therefore, the main arithmetic
operations needed for RNS computations are the modulo function X(mod P ),
modular summation, and modular multiplication.
For instance, A = 37, B = 19, and P = p 1 · p 2 · p 3 = 3 · 5 · 7 = 105. In
this case A 1 = 1, B 1 = 1, A 2 = 2, B 2 = 4, A 3 = 2, B 3 = 5, i.e., A = (1, 2, 2)
and B = (1, 4, 6). In this case, addition is produced by summing residues with