11 Hardware Realization of Arithmetic Operations
249
11.4.2 Computation of the Modular Product
We propose the following two-step procedure to compute the product A · B =
R(mod P ), where A = (A δ , A δ−1 , . . . , A 1 ), B = (B δ , B δ−1 , . . . , B 1 ), and the
δ-subvectors A δ and B δ consist of the most significant bits. For example, if A and B
are 12-bit numbers and δ = 4 , then A 4 = (a 12 , a 11 , a 10 ) and B 4 = (b 12 , b 11 , b 10 ),
where a 12 and b 12 are the most significant bits.
This contribution proposes a modulus function computation for an arbitrary
modulo without limitation on the value of P . The idea of the approach is to use
a large set of small moduli instead than a small set of large moduli, as it is used
traditionally. Hence we consider that A, B, and P vary from 6 to 12 bits.
1. The inputs are split into 2-, 3-, and 4-bit subvectors.
2. The corresponding pairs of subvectors are multiplied applying the following
recursive formula:
R =
δ
i=1
δ
j =1
A i · B j ·
2
m·(i+j −2)·3 (mod P )
= Stemp.
(11.4)
The maximum value of Stemp does not exceed 2 3·δ+2 , 2 3·δ+3 , or 2 3·δ+4 depending
on the value of modulo P .
As an illustration, consider three common cases:
1. δ = 2, then Stemp ≤ 2 8 and Stemp 2 = Stemp[3 : 1] + Stemp[6 : 4] ·
2 3 (mod P ) + Stemp[8 : 7] · 2 6 (mod P );
2. δ = 3, then Stemp ≤ 2 12 and Stemp 2 = Stemp[3 : 1] + Stemp[6 : 4] ·
2 3 (mod P ) + Stemp[9 : 7] · 2 6 (mod P ) + Stemp[12 : 10] · 2 9 (mod P );
3. δ = 4, then Stemp ≤ 2 12 and Stemp 2 = Stemp[3 : 1] + Stemp[6 : 4] ·
2 3 (mod P ) + Stemp[9 : 7] · 2 6 (mod P ) + Stemp[12 : 10] · 2 9 (mod P ) +
Stemp[15 : 13] · 2 12 (mod P ).
Finally, if Stemp 2 > P , then S = Stemp 2 − P , otherwise S = Stemp 2 .
Let us multiply the two 6-bit numbers A and B as A · B = S(mod 47). Splitting
the operands into two (i.e., δ = 2) 3-bit subvectors, Eq. (11.4) becomes: A · B =
S(mod 47) = A 1 · B 1 (mod 47) + A 1 · B 2 · 2 3 (mod 47) + A 2 · B 1 · 2 3 (mod 47) +
A 2 · B 2 · 2 6 (mod 47) = Stemp.
When A = 45 and B = 15, Stemp achieves the maximum value, which is
158 10 = 10011110 2 : A 1 = 101 2 , A 2 = 101 2 , B 1 = 111 2 , B 2 = 1 2 , hence A · B =
5 · 7(mod 47) + 5 · 1 · 2 3 (mod 47) + 5 · 7 · 2 3 (mod 47) + 5 · 1 · 2 6 (mod 47) =
35(mod 47) + 40(mod 47) + 45(mod 47) + 38(mod 47) = 158. Trying another
value for A and B, it is Stemp < 158.
The second iteration reduces Stemp to a value < 47. Assume that Stemp = 158,
then Stemp 2 = 6 + 3 · 2 3 (mod 47) + 2 · 2 6 (mod 47) = 6 + 24 + 34 = 64.
Finally, taking into account that 64 > 47, the result is S = 64 − 47 = 17. Note
that the bit range of Stemp is pre-selected.
249
11.4.2 Computation of the Modular Product
We propose the following two-step procedure to compute the product A · B =
R(mod P ), where A = (A δ , A δ−1 , . . . , A 1 ), B = (B δ , B δ−1 , . . . , B 1 ), and the
δ-subvectors A δ and B δ consist of the most significant bits. For example, if A and B
are 12-bit numbers and δ = 4 , then A 4 = (a 12 , a 11 , a 10 ) and B 4 = (b 12 , b 11 , b 10 ),
where a 12 and b 12 are the most significant bits.
This contribution proposes a modulus function computation for an arbitrary
modulo without limitation on the value of P . The idea of the approach is to use
a large set of small moduli instead than a small set of large moduli, as it is used
traditionally. Hence we consider that A, B, and P vary from 6 to 12 bits.
1. The inputs are split into 2-, 3-, and 4-bit subvectors.
2. The corresponding pairs of subvectors are multiplied applying the following
recursive formula:
R =
δ
i=1
δ
j =1
A i · B j ·
2
m·(i+j −2)·3 (mod P )
= Stemp.
(11.4)
The maximum value of Stemp does not exceed 2 3·δ+2 , 2 3·δ+3 , or 2 3·δ+4 depending
on the value of modulo P .
As an illustration, consider three common cases:
1. δ = 2, then Stemp ≤ 2 8 and Stemp 2 = Stemp[3 : 1] + Stemp[6 : 4] ·
2 3 (mod P ) + Stemp[8 : 7] · 2 6 (mod P );
2. δ = 3, then Stemp ≤ 2 12 and Stemp 2 = Stemp[3 : 1] + Stemp[6 : 4] ·
2 3 (mod P ) + Stemp[9 : 7] · 2 6 (mod P ) + Stemp[12 : 10] · 2 9 (mod P );
3. δ = 4, then Stemp ≤ 2 12 and Stemp 2 = Stemp[3 : 1] + Stemp[6 : 4] ·
2 3 (mod P ) + Stemp[9 : 7] · 2 6 (mod P ) + Stemp[12 : 10] · 2 9 (mod P ) +
Stemp[15 : 13] · 2 12 (mod P ).
Finally, if Stemp 2 > P , then S = Stemp 2 − P , otherwise S = Stemp 2 .
Let us multiply the two 6-bit numbers A and B as A · B = S(mod 47). Splitting
the operands into two (i.e., δ = 2) 3-bit subvectors, Eq. (11.4) becomes: A · B =
S(mod 47) = A 1 · B 1 (mod 47) + A 1 · B 2 · 2 3 (mod 47) + A 2 · B 1 · 2 3 (mod 47) +
A 2 · B 2 · 2 6 (mod 47) = Stemp.
When A = 45 and B = 15, Stemp achieves the maximum value, which is
158 10 = 10011110 2 : A 1 = 101 2 , A 2 = 101 2 , B 1 = 111 2 , B 2 = 1 2 , hence A · B =
5 · 7(mod 47) + 5 · 1 · 2 3 (mod 47) + 5 · 7 · 2 3 (mod 47) + 5 · 1 · 2 6 (mod 47) =
35(mod 47) + 40(mod 47) + 45(mod 47) + 38(mod 47) = 158. Trying another
value for A and B, it is Stemp < 158.
The second iteration reduces Stemp to a value < 47. Assume that Stemp = 158,
then Stemp 2 = 6 + 3 · 2 3 (mod 47) + 2 · 2 6 (mod 47) = 6 + 24 + 34 = 64.
Finally, taking into account that 64 > 47, the result is S = 64 − 47 = 17. Note
that the bit range of Stemp is pre-selected.