11 Hardware Realization of Arithmetic Operations
245
For instance, when P = 2 4 + 1 and X = 149, we have
149(mod (2
4
+ 1)) = (10010101) 2 (mod 17)
= ((0101) 2 + (−1)
2−1 (1001) 2 )(mod 17)
= (5 − 9)(mod 17)) = −4(mod 17) = 13(mod 17).
Given that in the RNS representation the moduli must be co-prime numbers,
multiplication of two 1000-bit numbers using the moduli {2 s −1, 2 2·s , 2 s +1, 2 s−1 −
1, 2 s+1 − 1} requires s ≈ 400 bits, which decreases the computational efficiency of
the transformation. The same multiplication can be realized using a set of smaller
moduli, since there are more than 400 12-bit numbers that are co-prime. Note that,
in order to represent uniquely numbers in RNS, the result of the calculation must not
exceed P = p 1 ·p 2 ·. . .·p m . If P = (2 s −1)·(2 2·s )·(2 s +1)·(2 s−1 −1)·(2 s+1 −1),
then s requires approximately a 400-bit number.
11.4 Hardware Design of Functions by Modulo
The approach that we propose is characterized as follows:
1. It is valid for an arbitrary modulo and bit range of the inputs.
2. It can be applied to modular multiplication, modular addition, and modulo
function.
3. It is based on combinational logic.
In the proposed procedures, there are some common tasks:
1. Inputs (input factors A · B in multiplication or input X in X(mod P )) are split
into subvectors.
2. All subvectors are combined to define a polynomial.
3. This procedure is iterated as long as the result > 2 · P .
11.4.1 Modulo Function Computation
We propose the following two-step procedure to compute X(mod P ):
1. X is split into k subvectors with ≤ δ bits in every subvector, where δ =
log 2 P − 1.
2. The resulting subvectors are combined according to Eq. (11.3):
X(mod P ) =
k
i=1
X i ·
2
δ·(i−1) (mod P )
.
(11.3)
245
For instance, when P = 2 4 + 1 and X = 149, we have
149(mod (2
4
+ 1)) = (10010101) 2 (mod 17)
= ((0101) 2 + (−1)
2−1 (1001) 2 )(mod 17)
= (5 − 9)(mod 17)) = −4(mod 17) = 13(mod 17).
Given that in the RNS representation the moduli must be co-prime numbers,
multiplication of two 1000-bit numbers using the moduli {2 s −1, 2 2·s , 2 s +1, 2 s−1 −
1, 2 s+1 − 1} requires s ≈ 400 bits, which decreases the computational efficiency of
the transformation. The same multiplication can be realized using a set of smaller
moduli, since there are more than 400 12-bit numbers that are co-prime. Note that,
in order to represent uniquely numbers in RNS, the result of the calculation must not
exceed P = p 1 ·p 2 ·. . .·p m . If P = (2 s −1)·(2 2·s )·(2 s +1)·(2 s−1 −1)·(2 s+1 −1),
then s requires approximately a 400-bit number.
11.4 Hardware Design of Functions by Modulo
The approach that we propose is characterized as follows:
1. It is valid for an arbitrary modulo and bit range of the inputs.
2. It can be applied to modular multiplication, modular addition, and modulo
function.
3. It is based on combinational logic.
In the proposed procedures, there are some common tasks:
1. Inputs (input factors A · B in multiplication or input X in X(mod P )) are split
into subvectors.
2. All subvectors are combined to define a polynomial.
3. This procedure is iterated as long as the result > 2 · P .
11.4.1 Modulo Function Computation
We propose the following two-step procedure to compute X(mod P ):
1. X is split into k subvectors with ≤ δ bits in every subvector, where δ =
log 2 P − 1.
2. The resulting subvectors are combined according to Eq. (11.3):
X(mod P ) =
k
i=1
X i ·
2
δ·(i−1) (mod P )
.
(11.3)