Page 66 - Hardware Implementation of Finite-Field Arithmetic

mod m Reduction 49

2.6 Specific Circuits
Throughout this chapter generic reducers based on sequential im-
plementations of five different algorithms have been proposed. For
particular values of n and k other structures could be considered
(completely combinational, partly sequential, and so on), or even
completely specific circuits.

2.6.1 mod 239 Reducer
As a first example, a 16-bit to 8-bit mod 239 reducer can be synthesized
as follows: a 16-bit number
14
15
x = x · 2 + x · 2 + . . . + x
15 14 0
can be decomposed under the form
3
12
2
3
2
x = (x · 2 + x · 2 + x · 2 + x ) 2 + (x · 2 + x · 2 + x · 2 + x )2 8
15 14 13 12 11 10 9 8
7
+ x · 2 + . . . + x
7 0
4
8
12
5
As 2 mod 239 = 33 = 2 + 1, and 2 mod 239 = 17 = 2 + 1,
3
5
2
3

x ≡ x’ = (x · 2 + x · 2 + x · 2 + x )(2 + 1)+ (x · 2
15 14 13 12 11
7
2
4
+ x · 2 + x 2 + x )(2 + 1) + x · 2 + . . . + x
10 9 8 7 0
7
8
3
2
= x · 2 + x · 2 + x · 2 + x · 2 + x · 2 + x · 2 + x · 2
6
5
15 14 13 12 15 14 13
+ x + x · 2 + x · 2 + x · 2 + x · 2 + x · 2 + x · 2
3
4
5
7
2
6
12 11 10 9 8 11 10
+ x 2 + x + x · 2 + . . . + x (2.52)
7
9 8 7 0
An upper bound of x’ is 15 · 33 + 15 · 17 + 255 = 1005, so that x’ is
a 10-bit number, that is,
8
9
x’ = x’ · 2 + x’ · 2 + . . . + x’
9 8 0
A similar decomposition gives
x’ = (x’ · 2 + x’ ) 2 + x’ · 2 + . . . + x’
7
8
9 8 7 0
≡ x’’ = (x’ · 2 + x’ )(2 + 1)+ x’ · 2 + . . . + x’
7
4

9 8 7 0
= x’ · 2 + x’ · 2 + x’ · 2 + x’ + x’ · 2 + . . . + x’ (2.53)
5
7
4
9 8 9 8 7 0
An upper bound of x’’ is 3.17 + 255 = 306, so that x mod 239 is
either x’’ or x’’ − 239.
The corresponding specific circuit, implementing Eqs. (2.52) and
(2.53), as well as the eventual subtraction, is shown in Fig. 2.10.
A VHDL file mod_239_reducer.vhd is available at www.
arithmetic-circuits.org. The corresponding entity declaration is
entity mod_239_reducer is
port (
x: in std_logic_vector(15 downto 0);
z: out std_logic_vector(7 downto 0)
);
end mod_239_reducer;