11 Hardware Realization of Arithmetic Operations
243
easily with another stage by applying the periodic property and a final (mod P )
reduction described earlier.
11.3.3 Approach Based on Modular Exponentiation
In this approach the various residues of powers of 2 (i.e., 2 x (mod p i )) are obtained
using logic functions [19, 20]. Consider as an example 2 s 3 s 2 s 1 s 0 (mod 13) from [13].
This expression can be rewritten as:
2
s 3 s 2 s 1 s 0 (mod 13) = 2
8s 3 +4s 2 4
s 1 2
s 0 (mod 13) = 256
s 3 16
s 2 4
s 1 2
s 0 (mod 13) =
(255s 3 + 1)(15s 2 + 1)4
s 1 2
s 0 (mod 13) = (3s 3 s 2 + 8s 3 + 2s 2 + 1)4
s 1 2
s 0 (mod 13).
Then we can evaluate the bracketed term for various values of s 0 , s 1 ,, e.g., for
s 1 = 0, s 0 = 0, we have 2 s 3 s 2 s 1 s 0 (mod 13) = (3s 3 s 2 + 8s 3 + 2s 2 + 1)(mod 13).
Afterwards, given the four assignments 11, 10, 01, 00 for bits s 3 and s 2 , the
expression 2 s 3 s 2 s 1 s 0 (mod 13) assumes the values 1, 9, 3, 1, respectively. Finally, the
logic function g 0 can be used to represent 2 s 3 s 2 s 1 s 1 (mod 13) for s 1 = 0, s 0 = 0,
according to the assignments of s 3 and s 2 , as
g 0 = 8s 3 s 2 + 2s 3 s 2 + 1.
In the same manner, the other functions corresponding to s 1 , s 0 , i.e., 01, 10, 11 can
be obtained as
g 1 = 4(s 2 ⊕ s 3 ) + 2(s 3 ⊕ s 2 ) + s 3 s 2 ,
g 2 = 8(s 2 ⊕ s 3 ) + 4(s 3 ⊕ s 2 ) + 2s 3 s 2 ,
g 3 = 4(s 2 ⊕ s 3 ) + 4s 2 s 3 + 2(s 3 ⊕ s 2 ) + (s 3 ⊕ s 2 ).
The logic gates that are used to generate the functions g 0 , g 1 , g 2 , g 3 can be shared
among the moduli. For instance, 2 11 (mod 13) can be obtained from g 3 (since s 0 =
s 1 ), by substituting s 3 = 1, s 2 = 0 as 7.
11.3.4 Approach Based on Varying Powers of 2
This technique uses the idea that the residues (mod P ) of various powers of 2 from
1 to 63 can assume values only between 0 and (P − 1) [11]. Thus, the number of
“1” bits in the residues corresponding to the 64 bits to be added is less, and it is
not the end of it: they can be further reduced by rewriting the residues which have
large Hamming weight as the sum of a correction term and of a word with a smaller
243
easily with another stage by applying the periodic property and a final (mod P )
reduction described earlier.
11.3.3 Approach Based on Modular Exponentiation
In this approach the various residues of powers of 2 (i.e., 2 x (mod p i )) are obtained
using logic functions [19, 20]. Consider as an example 2 s 3 s 2 s 1 s 0 (mod 13) from [13].
This expression can be rewritten as:
2
s 3 s 2 s 1 s 0 (mod 13) = 2
8s 3 +4s 2 4
s 1 2
s 0 (mod 13) = 256
s 3 16
s 2 4
s 1 2
s 0 (mod 13) =
(255s 3 + 1)(15s 2 + 1)4
s 1 2
s 0 (mod 13) = (3s 3 s 2 + 8s 3 + 2s 2 + 1)4
s 1 2
s 0 (mod 13).
Then we can evaluate the bracketed term for various values of s 0 , s 1 ,, e.g., for
s 1 = 0, s 0 = 0, we have 2 s 3 s 2 s 1 s 0 (mod 13) = (3s 3 s 2 + 8s 3 + 2s 2 + 1)(mod 13).
Afterwards, given the four assignments 11, 10, 01, 00 for bits s 3 and s 2 , the
expression 2 s 3 s 2 s 1 s 0 (mod 13) assumes the values 1, 9, 3, 1, respectively. Finally, the
logic function g 0 can be used to represent 2 s 3 s 2 s 1 s 1 (mod 13) for s 1 = 0, s 0 = 0,
according to the assignments of s 3 and s 2 , as
g 0 = 8s 3 s 2 + 2s 3 s 2 + 1.
In the same manner, the other functions corresponding to s 1 , s 0 , i.e., 01, 10, 11 can
be obtained as
g 1 = 4(s 2 ⊕ s 3 ) + 2(s 3 ⊕ s 2 ) + s 3 s 2 ,
g 2 = 8(s 2 ⊕ s 3 ) + 4(s 3 ⊕ s 2 ) + 2s 3 s 2 ,
g 3 = 4(s 2 ⊕ s 3 ) + 4s 2 s 3 + 2(s 3 ⊕ s 2 ) + (s 3 ⊕ s 2 ).
The logic gates that are used to generate the functions g 0 , g 1 , g 2 , g 3 can be shared
among the moduli. For instance, 2 11 (mod 13) can be obtained from g 3 (since s 0 =
s 1 ), by substituting s 3 = 1, s 2 = 0 as 7.
11.3.4 Approach Based on Varying Powers of 2
This technique uses the idea that the residues (mod P ) of various powers of 2 from
1 to 63 can assume values only between 0 and (P − 1) [11]. Thus, the number of
“1” bits in the residues corresponding to the 64 bits to be added is less, and it is
not the end of it: they can be further reduced by rewriting the residues which have
large Hamming weight as the sum of a correction term and of a word with a smaller